DOC PREVIEW
UMD CMSC 132 - Algorithmic Complexity 3

This preview shows page 1-2-3-26-27-28 out of 28 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 28 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Algorithmic Complexity 3OverviewCritical Section Example 7Recursive AlgorithmsRecursive Algorithm ExampleRecurrence RelationsSlide 7Solving Recurrence EquationsExample Recurrence SolutionsAsymptotic Complexity CategoriesComplexity Category ExampleSlide 12Calculating Asymptotic ComplexityComplexity ExamplesSlide 15Slide 16Slide 17Comparing ComplexityComplexity Comparison ExamplesL’Hopital’s RuleUsing L’Hopital’s RuleAdditional Complexity Measures2D Matrix Multiplication ExampleAdditional Complexity CategoriesNP Time AlgorithmSlide 26P = NP?Algorithmic Complexity SummaryAlgorithmic Complexity 3Fawzi EmadChau-Wen TsengDepartment of Computer ScienceUniversity of Maryland, College ParkOverviewRecurrence relationsComplexity categoriesComparing complexityTypes of complexity analysisCritical 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 sectionsRecursive Algorithms DefinitionAn algorithm that calls itselfComponents of a recursive algorithm1. Base casesComputation with no recursion2. Recursive casesRecursive callsCombining recursive resultsRecursive 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 caseRecurrence RelationsDefinitionValue of a function at a point is given in terms of its value at other pointsExamplesT(n) = T(n-1) + k T(n) = T(n-1) + nT(n) = T(n-1) + T(n-2)T(n) = T(n/2) + kT(n) = 2  T(n/2) + kRecurrence RelationsBase caseValue of function at some specified pointsAlso called boundary values / boundary conditionsBase case exampleT(1) = 0T(1) = 1T(2) = 1T(2) = kSolving Recurrence EquationsBack substitution (iteration method)Iteratively substitute recurrence into formulaExampleT(1) = 5T(n) = T(n-1) + 1 = ( T(n-2) + 1 ) + 1= ( ( T(n-3) + 1 ) + 1 ) + 1= ( ( ( T(n-4) + 1 ) + 1 ) + 1 ) + 1= …= (…( T(1) + 1 ) + … ) + 1= (…( 5 + 1 ) + … ) + 1= n + 4Example Recurrence SolutionsExamplesT(n) = T(n-1) + k  O(n)T(n) = T(n-1) + n  O(n2)T(n) = T(n-1) + T(n-2)  O(n!)T(n) = T(n/2) + k  O(log(n))T(n) = 2  T(n/2) + k  O(n)T(n) = 2  T(n-1) + k  O(2n)Many additional issues, solution methodsTake CMSC 351 – Introduction to AlgorithmsAsymptotic 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 > 1Complexity Category Example0501001502002503001 2 3 4 5 6 7Problem Size# of Solution Steps2^nn^2nlog(n)nlog(n)Complexity Category Example11010010001 2 3 4 5 6 7Problem Size# of Solution Steps2^nn^2nlog(n)nlog(n)Calculating Asymptotic ComplexityAs n increasesHighest complexity term dominatesCan ignore lower complexity termsExamples2 n + 100  O(n)n log(n) + 10 n  O(nlog(n))½ n2 + 100 n  O(n2)n3 + 100 n2 O(n3)1/100 2n + 100 n4 O(2n)Complexity Examples 2n + 100  O(n)0100000200000300000400000500000600000700000800000134912026053310682118417582081611131602n nlog(n) 2 n + 100Complexity Examples ½ n log(n) + 10 n  O(nlog(n))010000020000030000040000050000060000070000080000022879178373756150629755855115012256544252n nlog(n) 1/2 n log(n) + 10 nComplexity Examples ½ n2 + 100 n  O(n2)010000020000030000040000050000060000070000080000022879178373756150629755855115012256544252nlog(n) n^2 1/2 n^2 + 100 nComplexity Examples 1/100 2n + 100 n4  O(2n)11E+151E+301E+451E+601E+751E+901E+1051E+1201E+1351E+1502 13 28 49 79 120 178 260 373 533 756n^2 n^4 2^n 1 / 100 2^n + 100 n^4Comparing 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 complexitylim nf(n) g(n)Complexity Comparison Exampleslog(n) vs. n½1.001n vs. n1000lim nf(n) g(n)lim nlog(n) n½0lim nf(n) g(n)lim n1.001n n1000??Not clear, use L’Hopital’s RuleL’Hopital’s RuleIf ratio is indeterminate0 / 0 or  / Ratio of derivatives computes same valueCan simplify ratio by repeatedly taking derivatives of numerator & denominatorlim nf(n) g(n)lim nf'(n) g'(n)=Using L’Hopital’s Rule1.001n vs. n1000lim nf(n) g(n)lim n1.001n n1000lim nn 1.001n-1 1000 n999lim nn (n-1) 1.001n-2 1000999 n998…Additional Complexity MeasuresUpper bound Big-O  (…)Represents upper bound on # stepsLower bound Big-Omega  (…)Represents lower bound on # stepsCombined boundBig-Theta  (…)Represents combined upper/lower bound on # stepsBest possible asymptotic solution2D Matrix Multiplication ExampleProblem C = 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=Additional Complexity Categories Name DescriptionNP Nondeterministic polynomial time (NP)PSPACE Polynomial spaceEXPSPACE Exponential spaceDecidable Can be solved by finite algorithmUndecidable Not solvable by finite algorithmMostly of academic interest onlyQuadratic algorithms usually too slow for large dataUse fast heuristics to provide non-optimal solutionsNP Time AlgorithmPolynomial solution possibleIf make correct guesses on how to proceedRequired for many fundamental problemsBoolean satisfiability Traveling salesman problem (TLP)Bin packingKey to solving many optimization problemsMost efficient trip routesMost efficient schedule for employeesMost efficient usage of resourcesNP Time AlgorithmProperties of NPCan be solved with exponential timeNot proven to require exponential timeCurrently solve using heuristicsNP-complete problemsRepresentative of all NP problemsSolution can be used to solve any NP problemExamplesBoolean satisfiabilityTraveling salesmanP = NP?Are NP problems solvable in polynomial time?Prove P=NPShow polynomial time solution exists for any NP-complete problemProve PNPShow no polynomial-time solution possible The expected answerImportant open problem in computer science$1 million prize offered by Clay Math InstituteAlgorithmic Complexity SummaryAsymptotic


View Full Document

UMD CMSC 132 - Algorithmic Complexity 3

Documents in this Course
Notes

Notes

8 pages

Recursion

Recursion

12 pages

Sorting

Sorting

31 pages

HTML

HTML

7 pages

Trees

Trees

19 pages

HTML

HTML

18 pages

Trees

Trees

19 pages

Honors

Honors

19 pages

Lecture 1

Lecture 1

11 pages

Quiz #3

Quiz #3

2 pages

Hashing

Hashing

21 pages

Load more
Download Algorithmic Complexity 3
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Algorithmic Complexity 3 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Algorithmic Complexity 3 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?