CS 3103 Design & Analysis of Algorithms Chapter 1 PDF

CS 3103 Design & Analysis of Algorithms Chapter 1 Basic concepts Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Ro...

CS 3103 Design & Analysis of Algorithms Chapter 1 Basic concepts Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  Preface Many problems in our life: – Given a sequence of integers, find the largest one; – Given a set of integers, put them in increasing or decreasing order; – Given a network, find the shortest path between two vertices. How do you solve these problems? – Informally (Normal way), – Formally (Systematically). 3  Solving problem systematically Problem definition: – Type, constraints, input, output, etc. Problem analysis: – Starting point, ending point: Data needed, data available, data place, etc. Problem formulation: – Mathematical models, formal description, etc. 4  Solving problem systematically Algorithm design (planning for solution): Algorithm analysis (complexity): estimate – Size of problem – Time and space needed to find solution Implementation: Evaluation: 5 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  Problem formulation Problem can be defined formally by 5 components: – Initial input of problem: from where we start? – Operators: what are operators available? – Transition model: how operators change the value? – Solution test: if the current value is the result (goal)? – Solution cost: what is the cost of obtaining result? 7  Problem formulation Example: how you can obtain 120 from 5? – Initial input of problem: the value 5. – Operators: ++, ! – Transition model: result(5, ++) = 6 And result(5, !) = 120 – Solution test: is 6 = 120? – Solution cost: c(5, ++, 120) = 115 steps where c(5, !, 120) = 5 step 8 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  What is the algorithm? An algorithm is a: – Finite sequence of precise instructions for performing a computation or for solving a problem. – Sequence of computational steps that transform the input into the output. Algorithm can be viewed as a tool for solving a well-specified computational problem. 10  Example Input sequence: , Output sequence:. Which algorithm is best? depends on: – The number of items to be sorted, – Which the items are already somewhat sorted, – Possible restrictions on the item values, – The architecture of the computer, – The kind of storage devices to be used: main memory, disks, or tapes. 11 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  Algorithm representations An algorithm can be described using: – Natural language: such as Arabic, English, etc. Because people cannot understand all natural languages, it is undesirable to choose one natural language. – Programming language: such as C++, Java, Pascal, etc. Because many programming languages are in common use, it is undesirable to choose one particular language. – Pseudocode: Provides intermediate step between natural language and programming language. 13 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms Common properties of algorithms Input: Has input values from specified set. Output: For each input produce output (solution of problem). Definiteness: Steps of algorithm must be defined precisely. Correctness: For each input produce correct output. Finiteness: For each input produce desired output after finite number of steps. Effectiveness: Perform each step exactly in a finite amount of time. Generality: Should be applicable for all problems of the desired form. 15 Common properties of algorithms Example: Describe an algorithm for finding the maximum value in a finite sequence of integers. – Show that this algorithm has all the properties of algorithms. Solution: 16 Common properties of algorithms Input: sequence of integer. Output: largest integer. Definiteness: only assignments, finite loop, conditional statements occur. Correctness: When all the terms have been examined, max equals the value of the largest term. Finiteness: uses a finite number of steps. Effectiveness: perform each step in fixed time. Generality: work effectively with any sequence of integers 17 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  Characteristics of algorithmic problems Two characteristics are common to many interesting algorithmic problems: – Multiple solutions: have many candidate solutions. Finding one that is “best” is a challenge. – Importance: have practical applications. For example, finding the shortest path problems exists in: – A transportation. – A routing node on the Internet. – Driving between cities. 19 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  Reason to study algorithms Computers may be fast, – But they are not infinitely fast. Memory may be inexpensive, – But it is not free. Computing time and space in memory are important. – So, algorithms that are efficient in terms of time or space are desired. 21  Efficiency of algorithm Different algorithms designed to solve the same problem often differ in their efficiency. – Insertion sort: takes time roughly equal to c1n2 to sort n items (n is input size). – Merge sort: takes time roughly equal to c2n log2 n to sort n items. Insertion faster than merge for small n, While merge faster than insertion for large n. 22  Efficiency of algorithm: Example Assume that: – Computer A executes 10 billion (1010) instructions per second – Computer B executes only 10 million (107) instructions per second – Faster computer A running insertion sort against a slower computer B running merge sort. Each must sort an array of 10 million numbers (n = 107). Insertion sort on A requires 2n2 instructions to sort n numbers. Merge sort on B requires 50n log2n instructions to sort n numbers 23  Efficiency of algorithm: Example To sort 10 million numbers: Computer A takes: 2  (10 ) instructio ns 7 2 10  20,000 sec ond 10 instructio n / sec ond More than 5.5 hours While Computer B takes: 50  10 log 2 10 instructio ns 7 7 7  1163 sec ond 10 instructio n / sec ond Less than 20 minutes 24 Chapter Topics 1-1 Basic steps for solving problem 1-2 Problem formulation 1-3 What is the algorithm 1-4 Representation of algorithms 1-5 Properties of algorithms 1-6 Characteristics of algorithmic problems 1-7 Role of algorithms in computing 1-8 Performance measures of algorithms  Metrics of algorithms evaluation Completeness: Is the algorithm guaranteed to find a solution if there exist one? Optimality: Does the algorithm find the optimal solution? Time complexity: How long does it take for the algorithm to find a solution? Space complexity: How much memory is consumed in finding the solution? 26  Assignment 1 Write two different algorithms to find the minimum value in the sequence: A = – Check each algorithm with the properties of algorithms. – Evaluate each algorithm with the four metrics of performance evaluation. 27