Module 12 Limitations of Algorithm Power PDF

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Design and Analysis of Algorithms Design and Analysis of Algorithms Module 12 Limitations of Algorithm Power  Week Learning Outcomes Describe Lower-Bou...

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Design and Analysis of Algorithms Design and Analysis of Algorithms Module 12 Limitations of Algorithm Power  Week Learning Outcomes Describe Lower-Bound Arguments and decision trees Recognize P, NP, and NP-Complete Problems 4 Topic Outline  Lower-Bound Arguments  Decision Trees  P, NP, and NP-Complete Problems 5 Lower Bounds Lower bound: an estimate on a minimum amount of work needed to solve a given problem Examples: number of comparisons needed to find the largest element in a set of n numbers number of comparisons needed to sort an array of size n number of comparisons necessary for searching in a sorted array number of multiplications needed to multiply two n-by-n matrices Lower Bounds Lower bound can be an exact count an efficiency class () Tight lower bound: there exists an algorithm with the same efficiency as the lower bound Problem Lower bound Tightness sorting (nlog n) yes searching in a sorted array (log n) yes element uniqueness (nlog n) yes n-digit integer multiplication (n) unknown multiplication of n-by-n (n2) unknown matrices Methods for Establishing Lower Bounds trivial lower bounds information-theoretic arguments (decision trees) adversary arguments problem reduction Trivial Lower Bounds Trivial lower bounds: based on counting the number of items that must be processed in input and generated as output Examples finding max element polynomial evaluation sorting element uniqueness Hamiltonian circuit existence Conclusions may and may not be useful be careful in deciding how many elements must be processed (min-max) Decision Trees Decision tree —model algorithms that use comparisons: internal nodes represent comparisons leaves represent outcomes How many orderings of 2 elements? Of 3? Of n? Tree for 3-element insertion sort [insert b in a, then c into ab] Decision Trees abc yes no a