### Create a StudySoup account

#### Be part of our community, it's free to join!

Already have a StudySoup account? Login here

# ANALYSIS OF ALGORITHMS CPSC 311

Texas A&M

GPA 3.75

### View Full Document

## 42

## 0

## Popular in Course

## Popular in ComputerScienence

This 19 page Class Notes was uploaded by Ms. Jerad Bernhard on Wednesday October 21, 2015. The Class Notes belongs to CPSC 311 at Texas A&M University taught by Staff in Fall. Since its upload, it has received 42 views. For similar materials see /class/226085/cpsc-311-texas-a-m-university in ComputerScienence at Texas A&M University.

## Reviews for ANALYSIS OF ALGORITHMS

### What is Karma?

#### Karma is the currency of StudySoup.

#### You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/21/15

CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 1 CPSC 311 Lecture Notes Mathematical Foundations Chapters 3 and 4 Acknowledgement Parts of these course notes are based on notes from courses given by Jennifer Welch at Texas AampM University CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 2 Mathematical Foundations The initial part of this course focuses on giving us the mathematical foundations we need to use in the rest of the course These are covered by Chapters 3 5 in the text 0 Chap 3 Growth of Functions Asymptotic Analysis 7 we will review in Class Math 302 material 0 Chap 4 Recurrences we will reView in Class Math 302 material 0 Chap 5 Probabilistic Analysis and Randomized Algorithms this should also be largely reView but we will cover parts of it as they are needed CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 3 Asymptotic Analysis Main Idea We are interested in the work running time m the limit as the input size grows to in nity 0 focus on calculating running time in terms of its rate of growth with increasing problem size disregard multiplicative constants identify leading terms of highest order Example an algorithm with running time of order n2 will eventually ie for su iciently large n run slower than one with running time of order n which in turn will eventually run slower than one with running time of order lg n o asymptotic analysis in terms of Big Oh Theta and Omega are the tools we will use to make these notions precise Note Our conclusions will only be valid in the limit or asymptotically That is they may not hold true for small values of H You will explore this issue in the programming assignments CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 4 Big Oh Upper Bounding Running Time De nition gn E if Elc gt 0 and no gt 0 such that 9W S Cfln for all n 2 no often written as gn 0f Intuition 0 9n E 0f means gn is less than or equal to f when we ignore small values of n and constant multiples o gn is eventually trapped below some constant multiple of f 0 some constant multiple of f is an upper bound for gn for large enough n Useful Way to Show Big 0h Relationships 9n 0fn ggc for some constant e Z 0 and L Hopitals Rule is useful for doing this If limH00 f limH00 gn 00 then assuming f and g exist lim im M W M WWW CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 5 Examples Big Oh The complexities for insertion sort are 0 worstcase wn n2 n o averagecase an in2 in 1 1nn 1 1112 o bestcase bn n 1 1 1 11m gquot 1 n naoo naoo n naoo so the answer is yes 2 is wn On 3 is wn 0n2 4 is an 0n2 CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 6 Omega Lower Bounding Running Time De nition 9a E if Ele gt 0 and no gt 0 such that 9W 2 Cfln for all n 2 no often written as 9a Qf Intuition o 9n E Qf means gn is greater than or equal to f when we ignore small values of n and constant multiples o 9a is eventually trapped above some constant multiple of f 0 some constant multiple of f is a lower bound for 9a for large enough n Useful Way to Show Omega Relationships wec 9n69fn 11 Jeremy for some constant e Z 0 and again L Hopitals Rule is useful for doing this CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 7 Examples Omega The complexities for insertion sort are 0 worstcase wn n2 n o averagecase an in2 in 1 1nn 1 1112 o bestcase bn n 1 1 18 Wt QM n n 9W 5W iim1 1 iim im naoo naoo n 1 naoo n 1 so the answer is yes 2 is wn 3 is wn 9n2 4 is an DMZ CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 8 Theta Tightly Bounding Running Time De nition 9a E if 30102 gt 0 and no gt 0 such that Cifm S 9W S 021 for all n 2 no often written as 9a f Intuition o 9a E f means gn is equal to f when we ignore small values of n and constant multiples o 9a is eventually trapped between two constant multiples of f Useful Way to Show Theta Relationships 0 The easiest way is to show both a Big Oh and an Omega relationship 0 Can also use limits as before 9W gnEan itf lim e M lt lt gtgt mom for some constant e gt 0 note strictly greater than zero CPSC 311 7 Nancy Arnato 7 Spring 03 Mathematical Foundations 9 Examples Theta The complexities for insertion sort are 0 worstcase wn n2 n o averagecase an in2 in 1 lnn 1 ln2 o bestcase bn n 1 1 is bn n n g n We have already seen that bn OM and bn QM so the answer is yes We can also do it from scratch gn n 1 1 1 naoo n i naoo since 1 gt 0 the answer is yes 2 is wn n 3 is wn nz 4 is an n2 CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 10 Useful Properties for Asymptotic Analysis We will use asymptotic analysis to make statements like 0 An algorithm has worst case running time Ogn which means there is a constant 6 st for every it big enough every execution on an input of size it takes at most cgn time 0 An algorithm has worst case running time Qgn which means there is a constant 6 st for every it big enough at least one execution on an input of size it takes at least cgn time Some useful properties 0 If Ogn and gn Ohn then Ohn transitive intuition if fn S gnand 9a S hm then fn 3 Mn 7 also holds for Q and 9 0 09n iff 9W 90 intuition fn S 9a iffgn Z fn 0 GM iff 9W 90 VV intuition fn 9a iff 9a fn 0W 9 0maxfnagna es 0W n 0W 9W 900 QmaXUWL 900 9W 900 9maxfna 9WD CPSC 311 7 Nancy Arnato 7 Spring 03 Mathematical Foundations 11 Little Oh and Little Omega Little Oh and Little Omega are used to denote strict upperbounds and lowerbounds respectively 0 and Q bounds are not necessarily strict De nition gn E if for every 6 gt 0 there exists some no gt 0 such that for all n 2 no gn lt cfn Intuition o gn E 0f rneans gn is less than any contant rnultiple of f when we ignore srnall values of n o gn is eventually trapped below any constant rnultiple of f De nition gn E if for every 6 gt 0 there exists some no gt 0 such that for all n 2 no gn gt cfn Intuition o gn E wf rneans gn is greater than any contant rnultiple of f when we ignore srnall values of n o gn is eventually trapped above any constant rnultiple of f Showing Little Oh and Little Omega Relationships gm e 0am 11 largo m e o new 900 E wfn HT gage n CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 12 DivideandConquer Algorithms The divideandconquer paradigm Ch 2 o divide the problem into a number of subproblems o conquer the subproblems solve them 0 combine the subproblem solutions to get the solution to the original problem Note often the conquer step is done recursively Recursive algorithm to solve a given problem they call themselves recur sively one or more times to deal with closely related subproblems 0 usually the subproblems are smaller in size than the parent problem 0 divide and conquer algorithms are often recursive Example Merge Sort o divide the n element sequence to be sorted into two g element sequences 0 conquer sort the subproblems recursively using merge sort Tl o combine merge the resulting two sorted g element sequences CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 13 Analyzing DivideandConquer Algorithms When an algorithm contains a recursive call to itself its running time can often be described by a recurrence equation which describes the overall running time on a problem of size n in terms of the running time on smaller inputs For diVide and conquer algorithms we get recurrences that look like i 91 if n g c Tn aTnb Dn Cn otherwise where o a the number of subproblems we break the problem into 0 n b the size of the subproblems in terms of n o Dn is the time to diVide the problem of size n into the subproblems o C is the time to combine the subproblem solutions to get the answer for the problem of size n Example Merge Sort i 91 if n g 0 TM 2Tn2 n otherwise 0 a 2 two subproblems o nb n2 each subproblem has size approx n2 o Dn 91 just compute midpoint of array 0 C n merging can be done by scanning sorted subarrays CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 14 Solving Recurrences There are 3 general methods for solving recurrences Ch 4 Iteration Convert to Summation convert the recurrence into a summa tion by expanding some terms and then bound the summation H D Substitution Guess 55 Verify guess a solution and verify it is correct with an inductive proof OJ Apply Master Theorem if the recurrence has the form Tn aTnb fn then there is a formula that can often be applied Simpli cations there are two simpli cations we apply that won t affect asymptotic analysis 0 ignore floors and ceilings justi cation in text 0 assume base cases are constant ie Tn 91 for n small enough CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 15 Solving Recurrences Iteration convert to summation Example TM Tn 4T n 4T n 4 4T n expand 16T 2n n simplify 16 4T 2n n expand 64T 4n 2n n simplify 410g T1 4n 2n n gtIltgtIlt levels logn gtIltgtIlt 6410372 n 2203614 2k gtIltgtIlt convert to summation gtIltgtIlt logni cnlog4 n 2 1 gtIltgtIlt logbi loga gtIltgtIlt 271 a 7b formula CH2 nnlog2 1 gtIltgtIlt 210g n10g2 algebra m2 nn 1 m2 n2 n n2 Intuitive Help Can represent this as a recursion tree and identify compu tation with each node level in the tree 0 root represents computation C at top level of recursion 0 node at level i represents subproblem at level i in the recursion 0 height of tree is number of levels in the recursion 0 TM sum of all nodes in the tree CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 16 Solving Recurrences Substitution guess and verify This method involves o guessing form of solution 0 use mathematical induction to nd the constants and verify solution 0 use to nd an upper or a lower bound do both to obtain a tight bound Example Tn 4Tn 2 n upper bound guess Tn 0n3 and try to show Tn 3 CH3 for some 6 gt 0 we ll have to nd 6 basis assume Tk 3 GM for k lt n and prove Tn g cn3 Tn 4T n 4c3 n by inductive hypothesis n3 n m3 5n3 n H H H 3 3 where the last step holds if c 2 2 and n 2 1 We nd values of c and no by determining when n3 n 2 0 Useful Tricks are in text eg subtract lower order term change of vari ables CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 17 Practice Substitution guess and verify Problem 1 Give an upper bound for Tn 2Tn2 n guess TM OM and try to show TM 3 en for some 6 gt 0 you have to nd 6 basis assume Tk S ck for k lt n and prove Tn g on Tn 2T n 3 26 n by inductive hypothesis en n Om WRONG Question What is wrong with the above proof Problem 2 Show Tn 2Tn2 n is 9m log n using the substitution method CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 18 Solving Recurrences The Master Method The master method provides a cookbook method for solving recurrences of a certain form Master Theorem Let a Z 1 and b gt 1 be constants let be a function and let Tn be de ned on nonnegative integers as Tim an n Then Tn can be bounded asymptotically as follows 1 TM nbgba if f 0nlogba g for some constant e gt 0 2 Tn nbgbalog n if nlogb l 3 TM if 9n10gb for some constant e gt 0 and if af 3 for some constant e lt 1 and all su iciently large n Intuition compare f with nlogba 0 case 1 is W smaller than nlogba Case 21 f n is M equal to 9mm 0 case 3 f is polynomially larger than nlogba What is log a The number of times we diVide a by b to reach 01 CPSC 311 7 Nancy Amato 7 Spring 03 Mathematical Foundations 19 Solving Recurrences Master Method Example Tn 9T n o a 9 b 3 fn n nlogba n10g39 n2 0 compare f n with nlogba n2 i n 0n276 f is polynomially smaller than nlogb l 0 case 1 applies Tn nbgba nz Example Tn 1 o a 1 b fn 1 nlogba n10g321 n0 1 0 compare f 1 with nlogba 1 i 1 91 f is asymptotically equal to nlogb l 0 case 2 applies Tn nlogba log n log n Example Tn 3T nlogn o a 3 b 4 fn nlognn10gb n10g43 n039793 0 compare nlogn with nlogba n039793 7 n logn 9n03979316 is polynomially larger than nlogb l 0 case 3 might apply need to Check regularity of f i nd 6 lt 1 st af 3 for large enough n ie 3 log 3 cnlogn which is true for c i 0 case 3 applies Tn n log n Problem 1 Tn T 2393 3 N3

### BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.

### You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

## Why people love StudySoup

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

#### "I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

#### "It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

### Refund Policy

#### STUDYSOUP CANCELLATION POLICY

All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email support@studysoup.com

#### STUDYSOUP REFUND POLICY

StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here: support@studysoup.com

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to support@studysoup.com

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.