Slide2COMP2080.pdf.pdf

Md Momin Al Aziz [email protected] Computer Science University of Manitoba Analysis of Algorithms Slide 2: Mathematics Preliminaries 2 COMP 2080  Mathematics Preliminaries 2 Outlin...

Md Momin Al Aziz [email protected] Computer Science University of Manitoba Analysis of Algorithms Slide 2: Mathematics Preliminaries 2 COMP 2080  Mathematics Preliminaries 2 Outline 1. Binomial Theorem Pascal’s Triangle Some Long Proofs! 2. Introduction to algorithms Run times Growth Rate Momin ([email protected]) Analysis of Algorithms June 4, 2020 2 / 19  Binomial Theorem Binomial Theorem Theorem Given n, i is a positive number, prove n   n X n (x + y ) = x n−i y i i i=0 Momin ([email protected]) Analysis of Algorithms June 4, 2020 3 / 19  Binomial Theorem Pascal’s Triangle Pascal’s triangle is a triangular array consisting binomial coefficients:       n n−1 n−1 = + k k k −1       10 9 9 = + 4 4 3 9! 9! 9! 9! = + = + 4!5! 3!6! 4!5! 3!6! 6+4 10! = 9! = 6!4! 6!4! Formal proof of Pascal’s Triangle available in the Scribes, please take a look. Momin ([email protected]) Analysis of Algorithms June 4, 2020 4 / 19  Binomial Theorem Pascal’s Triangle https://en.wikipedia.org/wiki/Pascal%27s_triangle Momin ([email protected]) Analysis of Algorithms June 4, 2020 5 / 19  Binomial Theorem Proof of Binomial Theorem Before going into proving the Binomial Theorem we need to understand this simple relation of summation: Pn−1 (i + 1) = ni=1 i. P Prove i=0 Proof. n−1 X L.H.S. = (i + 1) i=0 = 1 + 2 + 3 +... + n n(n + 1) = 2 Xn = i = R.H.S. i=1 Momin ([email protected]) P P Analysis of Algorithms June 4, 2020 6 / 19  Binomial Theorem Proof of Binomial Theorem Proof. (Basis) For n = 1,     1 1 1−0 0 1 1−1 1 (x + y ) = x + y = x y + x y 0 1 (Induction) Assume, (x + y )n = ni=0 ni x n−i y i is true. P
Thus, we will prove that, n+1   X n + 1 n+1−i i (x + y )n+1 = x y i i=0 is true. Now, its time to check the class notes/Scribes! Momin ([email protected]) Analysis of Algorithms June 4, 2020 7 / 19  Analysis of Algorithms: Introduction What are Algorithms?... is a finite sequence of well-defined, computer-implementable instructions, typically to solve a class of problems or to perform a computation 1. 1 https://en.wikipedia.org/wiki/Algorithm Momin ([email protected]) Analysis of Algorithms June 4, 2020 8 / 19  Analysis of Algorithms: Introduction What are Problems In CS, Problems are defined as getting specific outputs to specific inputs Each of these specific inputs are called Instances Algorithms provide an easy-to-follow step-by-step clear instructions that guarantees the correct output for a specific instance (Heuristics does not guarantee) Make sure you are clear with the relation between Problem, Instance and Algorithm Momin ([email protected]) Analysis of Algorithms June 4, 2020 9 / 19  Analysis of Algorithms: Introduction Algorithms Algorithm 1: ArrayMin Input: Array A with n numbers Output: Minimum number (currentMin) from array A 1 currentMin ← A 2 for i ← 1 to n − 1 do 3 if currentMin > A[i] then 4 currentMin ← A[i] Momin ([email protected]) Analysis of Algorithms June 4, 2020 10 / 19  Analysis of Algorithms: Introduction Pseudocode Control Flow if...then...[else...] while...do repeat...until for...do Return statement: return variable Method Declaration: Algorithm method(arg, [arg...]) Assignments ← Equality testing = (not ==!) Momin ([email protected]) Analysis of Algorithms June 4, 2020 11 / 19  Analysis of Algorithms: Introduction Types of Analysis 1. Correctness: Does the algorithm guarantee the right answer for all instances? 2. Costs: Time Complexity: How much time does it take to run/complete the algorithm (aka Run Time)? Space Complexity: How much memory does the algorithm need to finish? Momin ([email protected]) Analysis of Algorithms June 4, 2020 12 / 19  Analysis of Algorithms: Introduction Time Complexity of Algorithms The run time of an algorithm depends on the input size (except constant time) Run times can be analyzed for best, average and worst case scenario Figure: Growth of Algorithm run times w.r.t. Input Size Momin ([email protected]) Analysis of Algorithms June 4, 2020 13 / 19  Analysis of Algorithms: Introduction Worst/Average/Best-case analysis Worst case analysis is the absolute worst performance of an algorithm for a specific input to the problem Worst case is often considered the best way to understand how an algorithm performs Best case is just the opposite, where we get the best performance of the algorithm Average case considers all possible inputs and takes the average For any algorithm analysis, always do the worst case analysis, not the best case (even if nothing mentioned) We will see this more formally (mathematically) in future classes Momin ([email protected]) Analysis of Algorithms June 4, 2020 14 / 19  Analysis of Algorithms: Introduction Random Access Memory (RAM) Model............... 1 2 3... 232 RAM contains a CPU and (virtually) unlimited memory Each memory cells are numerically ordered These memory cell can only contain a number or a singular value Accessing a memory costs unit time Assigning a specific value to a memory costs unit time Momin ([email protected]) Analysis of Algorithms June 4, 2020 15 / 19  Analysis of Algorithms: Introduction Basic computing steps These steps or operations are considered to have unit time In real life, the required time varies depending on H/W, operations etc. Examples: 1. Assignment of a variable (x = y ) 2. Accessing an array (A[i]) 3. Evaluating mathematical expressions ‘+,-,*,/,%’ (x + y ) 4. Comparison of numbers (x > y ) 5. Calling a method (method(arg 1,...)) 6. Returning from a method (return) 7. Read and write Importance: Building block for algorithms Momin ([email protected]) Analysis of Algorithms June 4, 2020 16 / 19  Analysis of Algorithms: Introduction Analyzing using computing steps Think if one step is equal to 1ms So now if you see two algorithms one with 1000 and 1200 steps then you know which one is faster Calculating these steps are however not that easy for large programs/algorithms Quite hard for Recursion/Multiple Nested Loop (examples coming up) Also, these steps depend on the input size as well Momin ([email protected]) Analysis of Algorithms June 4, 2020 17 / 19  Analysis of Algorithms: Introduction Example with While loop Algorithm 2: ArrayMax # operations Input: Array A with n numbers Output: Maximum number, currentMax from array A 1 i ←1 1 2 currentMax ← A 2 3 while i < n do n 4 if A[i] > currentMax then 2(n-1) 5 currentMax ← A[i] 2(n-1) 6 i ←i +1 2(n-1) 7 return currentMax 1 7n-2 Momin ([email protected]) Analysis of Algorithms June 4, 2020 18 / 19  Analysis of Algorithms: Introduction Next class More on Exact analysis using RAM Model Asymptotic Theory Run time Analysis Momin ([email protected]) Analysis of Algorithms June 4, 2020 19 / 19