Exam One Review
Exam One Review 4050
Popular in Design and Analysis of Algorithms 1
verified elite notetaker
Popular in ComputerScienence
verified elite notetaker
This 26 page Study Guide was uploaded by Courtney Walker on Thursday September 24, 2015. The Study Guide belongs to 4050 at University of Missouri - Columbia taught by Youssef Saab in Summer 2015. Since its upload, it has received 112 views. For similar materials see Design and Analysis of Algorithms 1 in ComputerScienence at University of Missouri - Columbia.
Reviews for Exam One Review
Report this Material
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: 09/24/15
22 Chapter 2 Getting Started a pointer to the array is passed rather than the entire array and changes tn individual array elements are visible to the calling procedure 39 A return statement immediately transfers control back to the point of call in the calling procedure Most return statements also take a value to pass back to the caller Our pseudocode differs from many programming languages in that we allow multiple values to be returned in a single return statement 39 The boolean operators and and or are short circuiting That is when we evaluate the expression J and y we rst evaluate x If x evaluates to FALSE then the entire expression cannot evaluate to TRUE and so we do not evaluate 3 If on the other hand A evaluates to TRUE we must evaluate y to determine the value of the entire expression Similarly in the expression at or y we eval uate the expression y only if x evaluates to FALSE Short circuiting operators allow us to write boolean expressions such as x a NIL and xf y without worrying about what happens when we try to evaluate xf when x is NIL 39 The keyword error indicates that an error occurred because conditions were wrong for the procedure to have been called The calling procedure is respon sible for handling the error and so we do not specify what action to take Exercises Figure 22 as a model illustrate the operation of 1N SERTION SORT on the array A 314159264l58 212 Rewrite the IN SERTIONSORT procedure to sort into nonincreasing instead of non decreasing order Consider the searching problem Input A sequence ofn numbers A a1a2 an and a value 1 Output An index i such that v 2 Ali or the special value NIL if 12 does not appear in A Write pseudocode for linear search which scans through the sequence looking for v Using a loop invariant prove that your algorithm is correct Make sure that your 100p invariant ful lls the three necessary properties 214 Consider the problem of adding two rt bit binary integers stored in two nelement arrays A and B The sum of the two integers should be stored in binary form in 39 quotquot39Hammad unwin quotl 2 3 Designing algorithms 29 order of growth But for large enough inputs a 012 algorithm for example will v run more quickly in the worst case than a 023 algorithm Exercises max warm 4 a 22 1 quot xpress the function n3 1000 10012 100n 3 in terms of notation 222 Consider sorting n numbers stored in array A by rst nding the smallest element of A and exchanging it with the element in Al Then nd the second smallest element of A and exchange it with A2 Continue in this manner for the rst n 1 elements of A Write pseudocode for this algorithm which is known as selection sort What loop invariant does this algorithm maintain Why does it need to run for only the rst it 1 elements rather than for all n elements Give the best case and worstcase running times of selection sort in notation JIM K fa fagagrji Consider linear search again see Exercise 21 3 How many elements of the in put sequence need to be checked on the average assuming that the element being searched for is equally likely to be any element in the array How about in the worst case What are the averagecase and worstcase running times of linear search in notation Justify your answers 224 How can we modify almost any algorithm to have a good bestcase running time 23 7 Designing algorithms We can choose from a wide range of algorithm design techniques For insertion sort we used an incremental approach having sorted the subarray Al j l we inserted the single element AU into its proper place yielding the sorted subarray Al j In this section we examine an alternative design approachknown as divide and conquer which we shall explore in more detail in Chapter 4 We ll use divide andaconquer to design a sorting algorithm whose worstcase running time is much less than that of insertion sort One advantage of divide andconquer algorithms is that their running times are often easily determined using techniques that we will see in Chapter 4 Problems for Chapter 2 39 233 Use mathematical induction to Show that when n is an exact power of 2 the solua tion of the recurrence if n 2 Tin 2Tn2n ifn2kforkgtl is T01 n lgn la I We can express insertion sort as a recursive procedure as follows in order to sort A1 rt we recursively sort A1 rt l and then insert An into the sorted array Al 11 1 Write a recurrence for the worstcase running time of this recursive version of insertion sort I 2135f Referring back to the searching problem see Exercise 213 observe that if the sequence A is sorted we can check the midpoint of the sequence against it and eliminate half of the sequence from further consideration The binary search al gorithm repeats this procedure halving the size of the remaining portion of the sequence each time Write pseudocode either iterative or recursive for binary search Argue that the worstcase running time of binary search is lg n Kant Observe that the while loop of lines 5 7 of the IN SERTIONSORT procedure in Section 21 uses a linear search to scan backward through the sorted subarray Al j a 1 Can we use a binary search see Exercise 23 5 instead to improve the overall worstcase running time of insertion sort to n lg n 237 Describe a n lg ntime algorithm that given a set S of n integers and another integer x determines whether or not there exist two elements in S whose sum is exactly x Problems at 21 Insertion sort on small arrays in merge sort Although merge sort runs in n lg n worstcase time and insertion sort runs in n worstcase time the constant factors in insertion sort can make it faster in practice for small problem sizes on many machines Thus it makes sense to coarsen the leaves of the recursion by using insertion sort within merge sort when 52 Chapter 3 Growth of Functions Symmetry l f0 gn ifand only if so 90 71 Transpose symmetry f0 00301 ifand O lyif 30 90 5 fa 0gn ifand only if gn afn Because these properties hold for asymptotic notations we can draw an analogy l between the asymptotic comparison of two functions f and g and the comparison r39 of two real numbers a and b 3 foe 0gn is like a g b 5quot foe S2gn is like a 3 b fn gn is like a b fn 0gn is like a lt b fn wgn is like a gt b We say that f n is asymptotically smaller than 3a if fn 0g 11 and f n is asymptotically larger than gn if f n wgn One property of real numbers however does not carry over to asymptotic nota tlon Trichotomy For any two real numbers a and b exactly one of the following must hold a lt ba bora gt b Although any two real numbers can be compared not all functions are asymptot ically comparable That is for two mctions f n and gn it may be the case that neither fn 0gn nor fn Qgn holds For example we cannot l compare the functions a and n1sinn using asymptotic notation since the value of the exponent in n13inn oscillates between 0 and 2 taking on all values in between Exercises 5 613 1 Let f n and got be asymptotically nonnegative functions Using the basic de quot 39 nition of notation prove that max f n gn9 fn ga F Show that for any real constants a and b where b gt 0 l l ab 015 1 il quotIll 32 Standard notations and common functions 53 313 Explain why the statement The running time of algorithm A is at least 0 112 is meaningless 314 ls 2quot1 02quot Is 22quot 02quot Prove Theorem 31 316 Prove that the running time of an algorithm is g n if and only if its worstcase running time is 0g 71 and its bestcase running time is 9g 11 31 7 Prove that 0gn wgn is the empty set 318 We can extend our notation to the case of two parameters n and m that can go to in nity independently at different rates For a given function gn m we denote by 0gn m the set of functions 0gnm f n m there exist positive constants c no and mo such thatO E fnm 5 cgnm for alln 2 n0 orm 2 m0 Give corresponding de nitions for Qgn m and g n m 32 Standard notations and common functions This section reviews some standard mathematical functions and notations and ex plores the relationships among them It also illustrates the use of the asymptotic notations Monotonicity A function f n is monotonically increasing if m 5 n implies f m 5 f n Similarly it is monotonically decreasing if m E it implies f m 3 f n A function f n is strictly increasing if m lt n implies f m lt fn and strictlv decreasing if m lt n implies f m gt fn Urquot nil r if M 60 Chapter 3 Growth of F motions l Q51 1J F 325 I l 2 which is to say that the ith Fibonacci number E is equal to W J3 rounded to the i nearest integer Thus Fibonacci numbers grow exponentially Exercises 32 Show that if fn and got are monotonically increasing functions then so are the functions f It gm and f gn and if fn and gn are in addition nonnegatiye then fn gn is monotonically increasing 3292 Prove equation 3 16 323 Prove equation 319 Also prove that n 002 and n 0n 324 Is the function l lgi l I polynomially bounded Is the function lg lg n polynomi ally bounded Which is asymptotically larger lglg n or lglgn l 326 A Show that the golden ratio 4 and its conjugate gt both satisfy the equation x2 x l 327 Prove by induction that the i th Fibonacci number satis es the equality i E 7 3 where 5 is the golden ratio and E5 is its conjugate A 39 I 328 Show that k lnk n implies k n In rt 43 The substitution methodfor solving recurrences 87 which is very much like recurrence 419 Indeed this new recurrence has the same solution S m 0m lg m Changing back from S m to T01 we obtain Tn T2m Sm 0mlgm 0lgnlglgn Exercises 43 Show that the solution of Tn Tn 1 n is 0n2 432 Show that the solution of Tn Tan2 1 is 0lg n 433 We saw that the solution of Tn 2TLn 2 n is 0n lg 21 Show that the so lution of this recurrence is also S2n lg n Conclude that the solution is n lg n 434 Show that by making a different inductive hypothesis we can overcome the di i culty with the boundary condition Tl l for recurrence 419 without adjusting the boundary conditions for the inductive proof 135 Show that n lg n is the solution to the exact recurrence 43 for merge sort Show that the solution to Tn 39 2Tn2j 17 n is 0n lg n 437 Using the master method in Section 45 you can show that the solution to the recurrence Tn 4Tn 3 n is Tn n10g3 4 Show that a substitution proof with the assumption Tn f cn1 g34 fails Then show how to subtract off a lower order term to make a substitution proof Work 43 8 Using the master method in Section 45 you can show that the solution to the recurrence Tn 4Tn 2 n is T n nz Show that a substitution proof with the assumption Tn 5 on2 fails Then show how to subtract off a lowerorder term to make a substitution proof work luau 44 The recursiontree method for solving recurrences 89 Tn en2 712 e Te Te Te reg Tun 6 He He Tun 6 Te reg res a b c 1 Cn2 CH2 0 92 c Q2 c 52 II 13 6 cm2 1084 r I l t l l V Til T61 Tin Tin 39Til T61 Til m m T61 m Tl1 Til l nlog4 3 n10g4 3 2 d Total 0n d Figurer45 Constructing a recursion tree for the recurrence Tn 3Tn 4 cnz Part a shows Tn which progressively expands in b d to form the recursion tree The fully expanded tree in part d has height log n it has log4 n 1 levels 45 The master method for solving recurrences 39 93 443 Use a recursion tree to determine a good asymptotic upper bound on the recurrence Tn 4Tn 2 2 11 Use the substitution method to verify your answer 4 44 Use a recursion tree to determine a good asymptotic upper bound on the recurrence f Tn 2Tn 1 l 1 Use the substitution method to verify your answer 4 45 Use a recursion tree to determine a good asymptotic upper bound on the recurrence T n Tn l Tn 2 11 Use the substitution method to verify your answer r that the solution to the recurrence Tn Tn 3 T2n 3 cn where c is a constant is 201 lg n by appealing to a recursion tree 4457 Draw the recursion tree for Tn 4TLn2 CH where c is a constant and provide a tight asymptotic bound on its solution Verify your bound by the substi tution method 448 Use a recursion tree to give an asymptotically tight solution to the recurrence Tn Tn a Ta en where a Z 1 and c gt 0 are constants 449 Use a recursion tree to give an asymptotically tight solution to the recurrence Tn Tom T1 orn era where or is a constant in the range 0 lt or lt l and c gt 0 is also a constant 45 The master method for solving recurrences The master method provides a cookbook method for solving recurrences of the form 39 Tn aTnb fn 420 where a Z l and b gt 1 are constants and f n is an asymptotically positive function To use the master method you will need to memorize three cases but then you will be able to solve many recurrences quite easily often without pencil and paper 94 Chapter4 Divide and Conquer The recurrence 420 describes the running time of an algorithm that divides a problem of size 11 into a subproblems each of size n b where a and b are positive constants The a subproblems are solved recursively each in time T0 b The rnction f 01 encompasses the cost of dividing the problem and combining the results of the subproblems For example the recurrence arising from Strassen s algorithm has a 7 b 2 and f 01 012 As a matter of technical correctness the recurrence is not actually well de ned because 72 might not be an integer Replacing each of the or terms T01 b with either TQn bJ or TQMbl will not affect the asymptotic behavior of the recur rence however We will prove this assertion in the next section We normally nd it convenient therefOre to omit the oor and ceiling functions when writing divideandconquer recurrences of this form The master theorem The master method depends on the following theorem J x Master theorem Leta 3 1 and b gt 1 be constants let f 01 be a function and let T01 be de ned on the nonnegative integers by the recurrence T0 aTO Ib for where we interpret it b to mean either Lnbj or Irbl Then T01 has the follow ing asymptotic bounds 1 If f 02 00210gba 6 for some constant e gt 0 then T02 nlogb a 2 lffn nmgb a then T01 2 nlogba lgn 3 If f01 52021039 for some constant e gt 0 and ifaf0 zb E cf0r for some constant c lt l and all suf ciently large n then T01 f n I Before applying the master theorem to some examples let s Spend a moment trying to understand what it says In each of the three cases we compare the function fn with the function nlogb Intuitively the larger of the two functions determines the solution to the recurrence If as in case 1 the function nlogb 1 is the larger then the solution is T01 90110993 If as in case 3 the anction f 01 is the larger then the solution is T01 2 f 01 If as in case 2 the two func tions are the same size we multiply by a logarithmic factor and the solution is T01 nmgba lgn f0 z lgn Beyond this intuition you need to be aware of some technicalities In the rst case not only must f 01 be smaller than nk gb quot it must be polynomially smaller N 96 Chapter 4 DivideandConquer f n n lgn is asymptotically larger than nl39ogb n The problem is that it is not polynomially larger The ratio fnrt1 gb rt lg nn lgn is asymp totically less than rtE for any positive constant 6 Consequently the recurrence falls into the gap between case 2 and case 3 See Exercise 46 2 for a solution Let s use the master method to solve the recurrences we saw in Sections 41 and 42 Recurrence 47 rm 2Tn2 n characterizes the running times of the divideandconquer algorithm for both the maximum subarray problem and merge sort As is our practice we omit stating the base case in the recurrence Here we have a 2 b 2 fn n and thus we have that 111 a 121 2 1 Case 2 applies since f n n and so we have the solution Tn n lg n Recurrence 417 T02 8Tn2 022 describes the running time of the rst divide andconquer algorithm that we saw for matrix multiplication Now we have a 8 b 2 and fn rzz and so 121 72105 3 2 113 Since n3 is polynomially larger than fn that is for 0n3 6 for e 1 case 1 applies and Tn 013 1 Finally consider recurrence 418 l T02 7Tn2 nz which describes the running time of Strassen s algorithm Here we have a 7 b 2 f n 2 nz and thus nlogb n10g27 Rewriting log2 7 as lg7 and recalling that 280 lt lg lt 281 we see that f rt 2 00115 5 for e 08 3 Again case 1 applies and we have the solution Tn 911lg 7 lai l 39339 Exercises 39939 l I j Li Casi Use the master method to give tight asymptotic bounds for the following recur rences f 61 rm 2 2Tn4 1 f b Tm 2Tn4 5 quot c Tel 2 2Tn4 n d Trz 2Tn4 112 Problems for Chapter 4 107 Problems 1 Recurrence examples Give asymptotic upper and lower bounds for Tn in each of the following recur rences Assume that Tn is constant for n g 2 Make your bounds as tight as possible and justify your answers a T011 2Tn2 n4 b Tn T7n10 n c Tn l6Tn4 712 d rm 7Tn3 n2 e rm 7Tn2 n2 f T01 2Tn4 g T01 Tn 2 n2 42 Parameterpassing costs Throughout this book we assume that parameter passing during procedure calls takes constant time even if an N e1ement array is being passed This assumption is valid in most systems because a pointer to the array is passed not the array itself This problem examines the implications of three parameterpassing strategies 1 An array is passed by pointer Time l 2 An array is passed by copying Time CN where N is the size of the array 3 An array is passed by copying only the subrange that might be accessed by the called procedure Time q p 1 if the subarray A p q is passed a Consider the recursive binary search algorithm for nding anumber in a sorted array see Exercise 235 Give recurrences for the worstcase running times of binary search when arrays are passed using each of the three methods above and give good upper bounds on the solutions of the recurrences Let N be the size of the original problem and n be the size of a subproblem b Redo part a for the MERGE SORT algorithm from Section 231 Chawrcr V 1 n 084050 HW 1 Exercise 211 First 26 is inserted before 31 and 41 then the second 41 is inserted between the rst 41 and 59 and nally 58 is placed between 41 and 59 Exercise 213 Found 2 false 239 1 while 239 g n and Found 2 false do if u then Found true else i i 1 if Found true then return 239 else return NIL Consider the following loop invariant which is true at the beginning of each new iteration of the while loop if Found 2 false then u is not equal to any of the values in A1i 1 and if Found 2 true then 0 Initially before the rst iteration Found 2 false and i z 1 and the statement is true because A1i 1 is empty Each iteration of the loop either increment i in case 75 u or sets Found true if 1 Therefore the statement remains true at the beginning of the next iteration At termination if Found true then we know that v as set in the last iteration of the loop loop does not execute if Found true However if Found 2 false then the loop terminated at 39339 n 1 and the above loop invariant implies that none of the values in A1n is equal to 1 Exercise 22 1 n3 Exercise 223 M It takes 73 steps to locate the element at index i in the array Therefore on average we to check 2329 1 elements The worst case occurs when searching for the last element and this case all the n elements need to be checked Both the average case and the worst case time are n because n gl Exercise 234 The pseudo code for the recursive version of insertion sort is given below RECURSIVE INSERTION SORTAn if n gt 1 then 39 RECURSIVE lNSERTION SORTAn 1 key A171 i n 1 while i gt 0 and gt key do Ai 1 Ai iziwl Ai1key In the above code the while loop iterates 0n times Therefore at most 01 time is spent besides the recursive call Therefore the recurrence relation is T Tn 1 1 Exercise 235 An iterative code of binary search for a query g in a sorted array A between index 1 and n is as follows low 2 1 high it while low 3 high mid 2 low highdiv2 if Amid q then report g found at index mid and stop else if Amid lt q then low 2 mid 1 else high 2 mid 1 report q is not in array A The worst case for this algorithm is when the query number g is not in the array in this case the while loop iterates the most number of time However each new iteration is roughly over half the range of indices of the preceding iteration Initially the range consists of n indices after i iterations the range is reduced to roughly nZi For i lgn 7222 1 Therefore the running time of binary search is l since each iteration of the loop requires 81 computations Exercise 236 Binary search enables us to quickly nd the location of the j th array element However in the worst case we still have to shift as many as j 1 elements in j time Therefore the worst case of INSERT IONSORT cannot be improved by gusing binary search do sQ3cClt 3 f2 boo 084050 HW 2 Exercise 311 Functions f and gn are asymptotically nonnegative This means that there ex ists positive no such that both functions are nonnegative for n 2 no Consequently maxf g n gn for n 2 no For any n we have n g max ngn and gn g Add the two inequalities and divide by 2 to get ngn2 g max n So max n n 9W Exercise 312 First note that n 2 g n a g 2n for n 2 maxa 2a Raising to a power I gt 0 maintains the directions of the inequalities Therefore 2b g n anb g 2nb Take c1 125 co 2 25 and no 2 maxa 2a to get clnb g n 15 g cgnb for all n 2 no Consequently n 0quot nb Exercise 315 For any two functions n and gn n if and only if n and n new Proof gtz If f 9gn then there exist positive constants cl co and no such that 0 s 0197 3 f g cogn for all n 2 no Therefore a There exist positive constants co and no such that 0 g f g cogn for all n 2 no This implies that b There exist positive constants cl and no such that 0 g clgn g f for all n 2 no This implies that n z ltz f Ogn implies that there exist positive constants co and n1 such that 0 g f S cogn for all n 2 n1 and f implies that there exist positive constants cl and no such that 0 g clgn g f for all n 2 no Therefore if we let no maxn1n2 then we have 0 g clgn g n g cogn for all n 2 no This means that 2 Exercise 325 lglgn is asymptotically larger than lglgn If i 2 lgn then 239 is the small est integer such that lgm S 1 Therefore i 1 is the smallest integer such that lgi 1lgn S 1 Therefore lglgn 2 IL 1 2 lgn 1 Since 53 1 is asymptotically larger than lg3 we conclude that lglgn lgn 1 is asymptotically larger than lglgn OnsQw L Scc sms 4395le 084050 HW 3 o5 Exercise 435 We need to show that Onlgn and Below 1 use inequality 316 of the text which is c 1 3 g ln1 t g 3 for 1 gt 1 which imply that zit1 x g ln2lg1 3quot g 3 for 1 gt 1 Ta Oman We need to show that there exist two positive constants c and no such that Tn ltZ cnlgn for n 2 no Assuming that this is true for and 712 we have Tn g bn g anZjlgLn2j cfnQWg nQl bn where b is some constant Using the fact that lgLn2j g gait2 and that n the above inequality implies that Tn g c bn S cnlgn 12 bit 2 cnlgn 1 b cn Therefore it suffices to show that c can be chosen so that cnlgn 1 b cn g cnlg This is equivalent to cnlg1 1n bCTL g 0 Since lg11n g 1nln2 for in gt 0 it suf ces to nd 3 such that cln2b cn g 0 Any 3 gt b guarantee that cln2bacn S 0 for n 2 no cln2c b Ta new We need to show that there exist two positive constants c and no such that Tn 2 3771 for n 3 no Assuming that this is true for and we have Tn Z Em Z anleanZj cfnleg nQl Em where b is some constant Using the fact that ngnZj g lgn2 and that n the above inequality implies that Tn Z CLnZJ 671 2 cnlgn w 12 bn cnlgn 1 b cn Therefore it suf ces to show that c can be chosen so that cnlgn 1 b cn 2 cnlgn This is equivalent to cnlg1 1nb cn Z 0 Since lg1 Z elnln21 1n 1ln21wn for n gt 0 it suf ces to nd 3 such that cnln21 n be cm 2 0 Note that limooo cnln21 cln2 and limonooa 377 2 oo if c lt b Therefore for any 0 lt c lt b there exists no such that tenln21 b cn 2 0 for n 2 no Exercise 436 Use the substitution method to show that T g cnlgn for some constant c and suf ciently large 72 Taking into account that nlgn is an increasing function and that g n we can write Tn S 20n2 17lgn2 17 n 2 001 34lgn 342 it Note that n 342 g 3n4 for n 2 68 so that lgn 342 g lg3n4 lgm 934 for n 2 68 Consequently Tn g 01 34lgn lg34 n for n 2 68 So T07 ltlt cnlgn if 34clgn 34d 93 4 ncl 93 4 1 g 0 The dominant term in that last inequality is nclg34 1 which is negative if c gt 1lg34 1lg43 Therefore 34clgn 34clg34 nclg34 1 S 0 is negative for suf ciently large n if c gt 1lg4 This shows that Tn 2 Onlgn You have to be careful when you use the substitution method that the induction hypothesis carry on to the next 71 For this exercise this means that the same constant c should appear after all the mathematical manipulations For example if instead of showing T g cnlgn we showed that Tn g c 1nlgn then the proof is incorrect since the39 constant is changed from c to C 1 Exercise 44 6 This is the same as the example in Figure 46 in the text Each FULL level of the tree adds up to on Non full levels add up to at most an The shortest possible path from a root to a leaf is n gt n3 gt 7132 gt gt 723 Since 713quot 2 1 when k l093 we conclude that there are at least full levels in the tree Therefore T 1 1 Exercise 451 In all four cases nlogbw crib942 7112 21 f z 1 is 07112 14 therefore by case 1 of the master theorem Tn nlz b f 2 1112 is 90112 therefore by case 2 of the master theorem Tn 81 2mm c n n is Owl21 and afnb 2014 722 3 cfn for c 2 12 Therefore by case 3 of the master theorem T n I d fn n2 is 9n121 and afnb 2 20142 2 7128 3 cfn for c 2 18 Therefore by case 3 of the master theorem Tn 2 ng Exercise 41 Parts a f can be solved using the master theorem You just need to verify which case of the master theorem applies a By case 3 of the master theorem Tn 9074 b By case 3 of the master theorem Tn c By case 2 of the master theorem Tn n2lgn 1 By case 3 of the master theorem Tn 012 e By case 1 of the master theorem T nlgm f By case 2 of the master theorem Tn z lgm g Using the substitution method you can show that Tn n3 Iteration also can be used but you need to know how to evaluate the resulting sum Quiz 1 CS4050 083115 1 Express the function n5 7n4 13113 2n9 2511 12 in Gnotation 3 A 9 n9 3 Show that lg 2111 1 0 lg n k 7 A Based on the de nition of the Big Oh notation we need to show that 0 5 lg 2n 1 S 0 lg n for positive 0 and a value of n 2 no where no gt 0 We know that for all positive n 2n 1 lt 411 Hence 1g 2n 1 3 lg 4n Now 1g 4n lg n lg 4 lt lg n lg n for no gt 4 lg n lg n lg n n lg n2 2 lg n We thus have a value for c ie c 2 Hence for c 2 and no 2 4 1g 2n l 0 lg 11 holds true Quiz 2 CS4050 091415 1 Show that for any real constants a and b where b gt 0 that n a b E nb 3 A The answer to this is given in HW 2 as the solution to Exercise 31 2 2 Rank the following functions in increasing order of growth 112 lg n 11 43 11 2 e 4 lg n 11 lg 11 35 A 12 1 nlg 11 41g 43 11 2 e 11 3 Solve T 11 T n2 2T n4 8 n using either the Substitution method OR the Recursion Tree method 35 A We shall use the Recursion Tree method to generate a good guess which we shall then use in the Substitution Method to solve the given recurrence N B You need not do both to solve a problem of this type It is good practice but will take more time n 9n l l l an 1122 1124 1124 1142 1142 1142 1142 1142 114 gt 11 114i 1121 I Looking at the tree above we see that it will be incomplete rstly the term at the rightmost side grows smaller at a faster rate than the term at the leftmost side Let us look at the rightmost term 1114 This term will be l at the level i log n of the tree Looking at the different terms we can see that this will also be the last level of the tree upto which it is full Since each level has a total cost of n the total cost at the level i log n will be n log n This is the lower bound on the total cost of the tree 1 Let us now look at the leftmost term ie n2i This term will be 1 at the level i log n of the tree IF the tree were full upto this level which it isn t the total cost would be n log n Stated differently the total cost of the tree is strictly less than n log 11 So we have that Cost of I the tree lt n log 11 Hence the solution to the given recurrence by the Recursion Tree method is O 11 lg 11 Let us now use this as the guess in the Substitution Method The recurrence is T n T n2 2T n4 G n We need to show that en lg n 2 cn2 lg nZ 2c n4 lg n4 9t on Let us simplify this inequality on lg n 3 cn12 lg nZ c n2 lg n4 on on lg n 2 Cn2 1g n12 1g n4 cn cnlgnzcn2 1gn lg2lgn 1g4cn cnlgn2cnf221gn lg2 21g2 cn cn lg n 2 on lg n 32cn 1g 2 en en lg n 2 cu lg n 32cn en en lg n gt en lg n l2cn This inequality will be true if l2cn were positive We see that this is indeed the case for all positive values of n and c Hence the solution to the recurrence is O n lg n Quiz 3 CS4050 092115 1 Solve the following recurrences using the Master Method GIVE ALL STEPS 6 a T n 3T n4 n2 log n A We see that n A log a n A log 3 This is asymptotically smaller than f n which in this case is n2 log 11 Hence this falls into case 3 of the Master Method So the solution is 8 f n or 399 n2 log n b T n 216T 116 113 A We see that n A log a n A 10g 216 n A 3 log 6 n3 This is asymptotically equivalent to f n which in this case is also n Hence this falls into case 2 of the Master Method So the solution is o f 11 lg n or o n3 lg n c T n 3T n9 1 A We see that n A legs a n A logg 3 We have the rule that log a log a logc b So taking c 3 we get logo 3 log 3 log 9 12 Thus 11 A logo 3 n A 12 This is asymptotically larger than f n which is 1 or no Hence this falls into case 1 of the Master Method So the solution is o n A 12 or o Vn s 2 Show that the solution to T n 2T n2 17 n is O 11 lg n 4 A Let us guess that the solution is O n log 11 Now we need to prove it is correct The recurrence now becomes T n E 2 c Ii2 17 log n2 17 9 n This becomes T n 5 en 34 log 112 17 9 11 Substituting n2 17 for n for all n 2 68 1 T n S on 34 log 34 n 9 n T n 5011 34 log n on 34 log 34 39 6 n T n S on log n on log 34 34 log n 34 log 34 8 n Ignoring the lower order terms log n and lower on log n on log 34 G n S on log n39if cn log 34 0 n S 0 The last inequality can be rearranged to nd the value of c for which this is true Hence our guess at the solution T n 0 11 log n is proven correct 18 Om quot4 A quotBax agave Pvmiao 103 on Grad SOCX39 SOCAV 902603366 quot 9 O Gad JL 390 Vrc rw 63gt G 3 quot WQATOX C olra t g Wop I ark 16 a x V 39 0336106 6 exemm js Ke I 90q0m23 f x 06 Pok oo Cam warm 6460ij quot39w 5amp0 SAVRAV U kixg I i39 mm p w w e 5 f I 8 30 AVCCC h oCem awCEIK d i me 35an mam 0 amp39 ZzgtC3 I I 0 WW i fr 0 gtltfb gongo a 407 n 0 5 5 Um 2 6 I 39 OgtOo 04 0 Q 39 b7 e nb 0900 p75 33 3 W an Ex 39 mrcm 1 0 Ar BC 0 7 lt lt TC 3 Eff r725 Jr 8C0 TC 03 3 Z1 ng Z 3 860339 W Cn quot 0 n i e302 3 was o New i Wed 6 m 67 8ka am C at W 3 Ca 365 S E 539 Squot i f I 391 L39 quot E Z k g as l r y ILL 215 E k 75 a n F ww c uCSSn 395 I 0 lt CoomQaCC Am CI 0 a w Pol noma quotas bzqcfa 46mm 1 a 01 m XL bECHCf quot h qLXJA 0 UC 50 50mg 1 105 06 obSA ARrVKOQ ix I I C 39 TUVZ l7190 610635 nak TO 3 C Clt Tam 2c QM lac1 5 WW 90 LL 1 4 lt Z Iquot a D 2 3 L0 39 ccn3q3 C3 2 H7 Wm It 0 3H7 3 i lCSCaL03 zk 7 5 34 my 397 g 04 L98 5 7 E 084510 34 n 2 6 CM Cm Jraknacm 4 Ic Hacm T imam Jr Cab 34 3 0 34 9 W 31 bCWCCA z i CWOOltgtW 39 cm ACWU q 0 haw wac h and 01 fwwyg m lt maxquot 05 g g 2 3 mm W63 0 n m 52 nZ WMC 2W0 Cn33 2 0 V2 gt 6 r S 2 n ksyoo Z QO LHJVS3WO 1 00 gt wow 0603855V lagd b w 96 A 520 1 lt5 QM Qn cmrl om T086 6275me Tcm 393 TC 5 T2 33 3 Co 39 39 0 Ln 03 CZB m t C0 Z r z L 252 3 Zia Oqquots n 32 3951 52 Foot W5 ampW aa o l ACV WK oa a Cm Cnloqg f TCn gammq s
Are you sure you want to buy this material for
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'