1CMSC 132: Object-Oriented Programming IIAlgorithmic Complexity IIDepartment of Computer ScienceUniversity of Maryland, College Park2OverviewCritical sections Comparing complexityTypes of complexity analysis3Analyzing AlgorithmsGoalFind asymptotic complexity of algorithmApproachIgnore less frequently executed parts of algorithmFind critical section of algorithmDetermine how many times critical section is executed as function of problem size4Critical Section of AlgorithmHeart of algorithmDominates overall execution timeCharacteristicsOperation central to functioning of programContained inside deeply nested loopsExecuted as often as any other part of algorithmSourcesLoopsRecursion5Critical Section Example 1Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. B4. CCode executionA onceB n timesC onceTime 1 + n + 1 = O(n)critical section6Critical Section Example 2Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. B4. for (int j = 0; j < n; j++)5. C6. DCode executionA onceB n timesTime 1 + n + n2+ 1 = O(n2)critical sectionC n2timesD once7Critical Section Example 3Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. for (int j = i+1; j < n; j++)4. BCode executionA onceB ½ n (n-1) timesTime 1 + ½ n2= O(n2)critical section8Critical Section Example 4Code (for input size n)1. A2. for (int i = 0; i < n; i++)3. for (int j = 0; j < 10000; j++)4. BCode executionA onceB 10000 n timesTime 1 + 10000 n = O(n)critical section9Critical Section Example 5Code (for input size n)1. for (int i = 0; i < n; i++)2. for (int j = 0; j < n; j++)3. A4. for (int i = 0; i < n; i++)5. for (int j = 0; j < n; j++)6. BCode executionA n2 timesB n2 timesTime n2 + n2= O(n2)critical sections10Critical Section Example 6Code (for input size n)1. i = 12. while (i < n)3. A4. i = 2 i5. BCode executionA log(n) timesB 1 timesTime log(n) + 1 = O( log(n) )critical section11Critical Section Example 7Code (for input size n)1. DoWork (int n)2. if (n == 1)3. A4. else5. DoWork(n/2)6. DoWork(n/2)Code executionA 1 timesDoWork(n/2) 2 timesTime(1) 1 Time(n) = 2 Time(n/2) + 1critical sections12Recursive Algorithms DefinitionAn algorithm that calls itselfComponents of a recursive algorithm1. Base casesComputation with no recursion2. Recursive casesRecursive callsCombining recursive results13Recursive Algorithm ExampleCode (for input size n)1. DoWork (int n)2. if (n == 1)3. A4. else5. DoWork(n/2)6. DoWork(n/2)recursive casesbase case14Asymptotic Complexity Categories Complexity Name ExampleO(1) Constant Array accessO(log(n)) Logarithmic Binary searchO(n) Linear Largest elementO(n log(n)) N log N Optimal sortO(n2) Quadratic 2D Matrix additionO(n3) Cubic 2D Matrix multiplyO(nk) Polynomial Linear programmingO(kn) Exponential Integer programmingFrom smallest to largest For size n, constant k > 115Comparing ComplexityCompare two algorithmsf(n), g(n)Determine which increases at faster rateAs problem size n increasesCan compare ratioIf , f() is largerIf 0, g() is largerIf constant, then same complexitylimnf(n)g(n)16Complexity Comparison Exampleslog(n) vs. n½1.001nvs. n1000limnf(n)g(n)limnlog(n)n½0limnf(n)g(n)limn1.001nn1000??Not clear, use L’Hopital’s Rule17Additional Complexity MeasuresUpper boundBig-O (…)Represents upper bound on # stepsLower boundBig-Omega (…)Represents lower bound on # stepsCombined boundBig-Theta (…)Represents combined upper/lower bound on # stepsBest possible asymptotic solution182D Matrix Multiplication ExampleProblemC = A * BLower bound(n2) Required to examine 2D matrixUpper boundsO(n3) Basic algorithmO(n2.807) Strassen’s algorithm (1969)O(n2.376) Coppersmith & Winograd (1987)Improvements still possible (open problem)Since upper & lower bounds do not match=19Additional Complexity Categories Name DescriptionP Deterministic polynomial timeNP Nondeterministic polynomial timePSPACE Polynomial spaceEXPSPACE Exponential spaceDecidable Can be solved by finite algorithmUndecidable Not solvable by finite algorithmIf a problem has a algorithm that solves it in time X, then the problem is said to be in Xe.g., matrix multiplication is in PWhy do we care?If a problem can’t be solved with in P time, then no algorithm can solve all cases exactly in a reasonable amount of timeBut there might be an algorithm that always quickly gives close approximationsOr an algorithm that gives quick exact answers for the cases we care aboutIssues such as PSPACE vs. EXPSPACE are interesting theoretical issues, and sometime provide practice insight 20NP Time AlgorithmsTwo ways of thinking about itFirst way:Given a problem, and a potential answer, can we verify that the answer is correct in polynomial time?Second way:Whenever the algorithm wants, it can clone itself in twoIf either clone finds an answer, the entire system produces an answer21Graph 3-coloringGiven a graph (vertices and undirected edges)Can you find a way to color each vertex either blue, red, or greenSuch that no two vertices connected by an edge have the same color?2223Some graphs are hard3 coloring a graph is in NPThere exist NP algorithms to 3 color a graphGuess a 3 coloringVerify that the coloring is validEasy to do in O(n) timeNo one knows if there exists a polynomial time algorithm to find a 3 coloring for an arbitrary graphIf you come up with one, even one that runs in time O(n100), you win one million dollarsSeriously2425NP Time AlgorithmMany interesting problems are solvable with an NP algorithm, but not known to be solvable with a P algorithmBoolean satisfiability Traveling salesman problem (TLP)Bin packingKey to solving many optimization problemsMost efficient trip routesMost efficient schedule for employeesMost efficient usage of resources26NP Complete problemsSome problems are NP-completeThey are in NPAnd if a polynomial time algorithm existed for the programThen every single last problem in NP could be solved in polynomial timeAlmost all problems that are in NP but are not known to be in P are NP-completeBut not all27P = NP?Are NP problems solvable in polynomial time?Prove P=NPShow polynomial time solution exists for any NP-complete problemProve PNPShow no polynomial-time solution possible for some problem in NP The expected answerThe most important open problem in CS$1 million prize offered by Clay Math InstitutePlus front page, NY Times, job offers galore, instant
View Full Document
Unlocking...