Chapter 1.pdf

Design and Analysis of Algorithms (DAA)  Motivation Design - Design algorithms for different problems Analysis – Why not just measure processing time? – Time vs. space complexity analysis – Upper and lower limits 2 ...

Design and Analysis of Algorithms (DAA)  Motivation Design - Design algorithms for different problems Analysis – Why not just measure processing time? – Time vs. space complexity analysis – Upper and lower limits 2  What we’ll study General Design Techniques Divide and Conquer, Dynamic Programming, Greedy Algorithms, etc. Specific Problems Shortest paths, max flow, Various Paradigms Alternate models of computation NP Completeness 3  Key concepts Problem - Can the problem be solved? - How difficult is the problem? - Real-life problems to algorithmic problems Algorithm – How to find suitable algorithm? – How to make it efficient? 4  What is algorithm? We need a well-specified problem that tells what needs to be achieved Algorithm solves the problem It consists of a sequence of commands that takes an input and gives output Input Algorithm Output 5  Study of Algorithms Devise algorithms Validate algorithms Analyze algorithms Test a program  Non-solvable problems Give list of all rational numbers in [0..1] Longest sequence of  without the 0 digit Stopping problem 7  Algorithm principles Sequence - One command at a time - Parallel and distributed computing Condition - IF - CASE Loops - FOR - WHILE - REPEAT  Performance Analysis: Complexity Time complexity: – How much time it takes to compute – Measured by a function T(N) Space complexity: – How much memory it takes to compute – Measured by a function S(N) 9  Time complexity N = Size of the input T(N) = Time complexity function Order of magnitude: – How rapidly T(N) grows when N grows – For example: O(N) O(logN) O(N²) O(2N) 10  Asymptotic analysis 2N --- exponential N3 --- cubic N² --- quadratic N --- linear log N --- sub-linear Examples: Bubble sort (N²), Quicksort (N∙logN) 11 Problem size vs. processing time Processing time increases → f(N) T(N) = 1,000 T(N)=10,000 Growth rate 100N N = 10 N=100 10 x 5N² 14 44 3.1 x ½N³ 12 27 2.3 x 2N 9 13 1.4 x logN 21,000 210,000 Very high!! 12  Upper and lower limits Upper limit For example: f(n) = 3n+7 = O(n) Suppose that c= 4 then 3n+7 ≤ 4n 7≤ n which is true for all when n0=7 13