Algorithms Analysis And Design Lecture 3 PDF

Faculty of Computers and Information Technology CS341 ALGORITHMS ANALYSIS AND DESIGN Lecture 3 Dr. Ahmed Hamza Problem Solving Process Problem Algorithm Input Output Steps Analysis Correctness Time & Space Optimality I...

Faculty of Computers and Information Technology CS341 ALGORITHMS ANALYSIS AND DESIGN Lecture 3 Dr. Ahmed Hamza Problem Solving Process Problem Algorithm Input Output Steps Analysis Correctness Time & Space Optimality Implementation Verification 2 Why do we Analyze about Algorithms? Several possible algorithms exist that can solve a particular problem each algorithm has a given efficiency compare efficiencies of different algorithms for the same problem By analyzing several candidate algorithms, the most efficient one(s) can be identified 3 Efficiency of Algorithms The efficiency of an algorithm is a measure of the amount of resources consumed in solving a problem of size n Running time (number of primitive steps that are executed) Memory/Space Analysis in the context of algorithms is concerned with predicting the required resources There are always tradeoffs between these two efficiencies allow one to decrease the running time of an algorithm solution by increasing space to store and vice-versa Time is the resource of most interest 4 Analysis of Algorithms (AofA) Many criteria affect the running time of an algorithm, including speed of CPU, bus and peripheral hardware design time, programming time and debugging time language used and coding efficiency of the programmer quality of input (good, bad or average) But Programs derived from two algorithms for solving the same problem should both be Machine independent Language independent 5 Amenable to mathematical study Realistic What do we Analyze about Algorithms? Algorithms are analyzed to understand their behavior and to improve them if possible Correctness Does the input/output relation match algorithm requirement? Amount of Work Done Basic operations to do task Amount of Space Used Memory used Simplicity & Clarity Verification and implementation. Optimality 6 Is it impossible to do better? Computation Model for Analysis To analyze an algorithm is to determine the amount of resources necessary to execute it. These resources include computational time, memory and communication bandwidth. Analysis of the algorithm is performed with respect to a computational model called RAM (Random Access Machine) A RAM is an idealized uni-processor machine with an infinite large random-access memory Instruction are executed one by one All memory equally expensive to access No concurrent operations Constant word size 7 All reasonable instructions (basic operations) take unit time Complexity of Algorithms The complexity of an algorithm is the amount of work the algorithm performs to complete its task. It is the level of difficulty in solving mathematically posed problems as measured by: Time (time complexity) No. of steps or arithmetic operations (computational complexity) Memory space required (space complexity) Complexity is a function T(n) which yields the time (or space) required to execute the algorithm of a problem of size ‘n’. 8 Algorithm Analysis (1) Two essential approaches to measuring algorithm efficiency: Empirical analysis: Program the algorithm and measure its running time on example instances Theoretical analysis Employ mathematical techniques to derive a function which relates the running time to the size of instance 9 Algorithm Analysis (2) The following three cases are investigated in algorithm analysis: A) Worst case: The worst outcome for any possible input We often concentrate on this for our analysis as it provides a clear upper bound of resources an absolute guarantee B) Average case: Measures performance over the entire set of possible instances Very useful, but treat with care: what is “average”? Random (equally likely) inputs vs. real-life inputs C) Best Case: The best outcome for any possible input provides lower bound of resources 10 Algorithm Analysis (3) An algorithm may perform very differently on different example instances. e.g: bubble sort algorithm might be presented with data: already in order in random order in the exact reverse order of what is required Average case analysis can be difficult in practice to do a realistic analysis we need to know the likely distribution of instances However, it is often very useful and more relevant than worst case; for example quicksort has a catastrophic (extremly harmful) worst case, but in practice it is one of the best sorting algorithms known The average case uses the following concept in probability theory. Suppose the numbers n1, n2 , …, nk occur with respective probabilities p1, p2,…..pk. Then the expectation or average value E 11 is given by E = n1p1 + n2p2 +...+ nk.рk Empirical Analysis (1) Write a program implementing the algorithm Run the program with inputs of varying size and compositions Use timing routines to get an accurate measure of the actual running time e.g. System.currentTimeMillis() Plot the results 12 Empirical Analysis (2) Most algorithms transform input objects into output objects The running time of an algorithm typically grows with the input size Average case time is often difficult to determine We focus on the worst case running time Easier to analyze 13 Crucial to applications such as games, finance and robotics Empirical Analysis (3) 14 Empirical Analysis (4) 15 Empirical Analysis (5) 16 Empirical Analysis (6) 17 Empirical Analysis (7) 18 Empirical Analysis (8) 19 Empirical Analysis (9) 20 Empirical Analysis (10) 21 Empirical Analysis (11) 22 Empirical Analysis (12) 23 Empirical Analysis (13) 24 Limitations of Empirical Analysis Implementation dependent Execution time differ for different implementations of same program Platform dependent Execution time differ on different architectures Data dependent Execution time is sensitive to amount and type of data minipulated. Language dependent Execution time differ for same code, coded in different 25 languages ∴ absolute measure for an algorithm is not appropriate Theorerical Analysis Data independent Takes into account all possible inputs Platform independent Language independent Implementatiton independent not dependent on skill of programmer can save time of programming an inefficient solution Characterizes running time as a function of input size, n. Easy to extrapolate without risk 26 Pseudocode (1) High-level description of an algorithm More structured than English prose but Less detailed than a program Preferred notation for describing algorithms Hides program design issues ArrayMax(A, n) Input: Array A of n integers Output: maximum element of A 1. currentMax  A; 2. for i = 1 to n-1 do 3. if A[i] > currentMax then 27 4. currentMax  A[i] 5. return currentMax; Pseudocode (2) Indentation indicates block structure. e.g body of loop Looping Constructs while, for and the conditional if-then-else The symbol // indicates that the reminder of the line is a comment. Arithmetic & logical expressions: (+, -,*,/, ) (and, or and not) Assignment & swap statements: a b , ab c, a → b Return/Exit/End: termination of an algorithm or block ArrayMax(A, n) Input: Array A of n integers Output: maximum element of A 1. currentMax  A; 2. for i = 1 to n-1 do 3. if A[i] > currentMax then 28 4. currentMax  A[i] 5. return currentMax; Pseudocode (3) Local variables mostly used unless global variable explicitly defined If A is a structure then |A| is size of structure. If A is an Array then n =length[A], upper bound of array. All Array elements are accessed by name followed by index in square brackets A[i]. Parameters are passed to a procedure by values Semicolons used for multiple short statement written on one line ArrayMax(A, n) Input: Array A of n integers Output: maximum element of A 1. currentMax  A 2. for i = 1 to n-1 do 3. if A[i] > currentMax then 29 4. currentMax  A[i] 5. return currentMax Elementary Operations An elementary operation is an operation which takes constant time regardless of problem size. The running time of an algorithm on a particular input is determined by the number of “Elementary Operations” executed. Theoretical analysis on paper from a description of an algorithm Defining elementary operations is a little trickier than it appears We want elementary operations to be relatively machine and language independent, but still as informative and easy to define as possible Example of elementary operations include variable assignment arithmetic operations (+, -, x, /) on integers comparison operations (a < b) boolean operations accessing an element of an array 30 We will measure number of steps taken in term of size of input Components of Algorithm Variables and values Instructions Selections Repetitions 31 Instruction A linear sequence of elementary operations is also performed in constant time. More generally, given two program fragments P1 and P2 which run sequentially in times t1 and t2 use the maximum rule which states that the larger time dominates complexity will be max(t1,t2) e.g. Assignment Statements x=a.....................1 x= a+b*c/h-u......1 T(n) = 1+1+1 a>b......................1 T(n) = 3 32 Selection If then P1 else P2 structures are a little harder; conditional loops. The maximum rule can be applied here too: max(t1, t2), assuming t1, t2 are times of P1, P2 However, the maximum rule may prove too conservative if is always true the time is t1 if is always false the time is t2 e.g. if (a>b) then...........1 a=2......................1 b=b+3*t.............1 else x=x+2*3................1 Block #1 t1 Block #2 t2 Max(t1,t2) 33 T(n)= 1+max(2,1) = 3 Repetition (Loops) - 1 Analyzing loops: Any loop has two parts: How many iterations are performed? How many steps per iteration? for i = 1 to n do P(i); Assume that P(i) takes time t, where t is independent of i Running time of a for-loop is at most the running time of the statements inside the for-loop times number of iterations T(n) = nt 34 This approach is reasonable, provided n is positive If n is zero or negative the relationship T(n) = nt is not valid Repetition (Loops) - 2 Analysing Nested Loops for i = 0 to n do for j = 0 to m do P(j); Assume that P(j) takes time t, where t is independent of i and j Start with outer loop: How many iterations? n How much time per iteration? Need to evaluate inner loop Analyze inside-out. Total running time is running time of the statement multiplied by product of the sizes of all the for-loops 35 T(n) = nmt Repetition (Loops) - 3 Analysing Nested Loops for i = 0 to n do for j = 0 to i do P(j); Assume that P(j) takes time t, where t is independent of i and j How do we analyze the running time of an algorithm that has complex nested loop? The answer is we write out the loops as summations and then solve the summations. To convert loops into summations, we work from inside-out. i =0 ri + t  n n T(n) = n + i =0 i r 36 = n + n(n+1)/2 + tn(n+1)/2  Analysis Example Algorithm: Number of times executed 1. n = read input from user 1 2. sum = 0 1 3. i = 0 1 4. while i < n n n or i =01 n −1 5. number = read input from user n or i =01 n −1 6. sum = sum + number 7. i=i+1 8. mean = sum / n  n or n−11 1 i =0 The computing time for this algorithm in terms on input size n is: T(n) = 1 + 1 + 1 + n + n + n + n + 1 37 T(n) = 4n + 4 Another Analysis Example i=1...............................1 while (i < n)................n-1 a=2+g...............n-1 i=i+1................n-1 if (i