c Balaji Raghavachari 23 Algorithm Design and Analysis c Balaji Raghavachari 24 Algorithm Design and Analysis Application of the master method Master method Exercise 4 3 1 page 75 Method for solving most recurrences that occur when using divide and conquer proved using iteration method T n aT n b f n where a 1 b 1 are constants 1 T n 4T n 2 n a 4 b 2 n logb a n2 f n n O n2 for 0 1 From Case 1 T n n2 1 If f n O n logb a for some constant 0 then T n n logb a 2 T n 4T n 2 n2 a 4 b 2 n logb a n2 f n n2 From Case 2 T n n2 lg n 2 If f n n logb a then T n n logb a lg n 3 If f n n logb a for some constant 0 and if af n b cf n for some constant c 1 and all sufficiently large n then T n f n c Balaji Raghavachari 25 Algorithm Design and Analysis 3 T n 4T n 2 n3 a 4 b 2 n logb a n2 f n n3 n2 for 0 1 Also af n b 4 n 2 3 n3 2 cf n for any 12 c 1 From Case 3 T n n3 c Balaji Raghavachari 26 Algorithm Design and Analysis When Master method fails Recurrences for which the Master method does not apply k Simpler Master Method when f n cn Tower of Hanoi T n 2T n 1 1 not the right form Use substitution method T n O 2n Consider the special case when the recurrence is T n aT n b cnk Median problem T n T n 5 T 7n 10 n not the right form problem sizes are nonuniform Substitution method can be used to prove that T n O n 1 Case 1 If k logb a then T n nlogb a 2 Case 2 If k logb a then T n nlogb a log n nk log n Sorting network design T n 2T n 2 n log n in this case a 2 b 2 f n n log n nlogb a n Here n is smaller than n log n but not polynomially smaller Use substitution method T n O n log2 n 3 Case 3 If k logb a then T n nk c Balaji Raghavachari 32 Algorithm Design and Analysis Merge algorithm 1 3 4 5 6 7 8 9 Copy A p q into L 1 q p 1 Copy A q 1 r into R 1 r q Set sentinels L q p R r q 1 i 1 j 1 for k p to r do if L i R j then A k L i i i 1 else A k R j j j 1 1 If L i R j then L i is the k p 1th smallest element of L and R because i L i L i for i i ii L i R j R j for j j The algorithm copies L i to A k line 7 So now A p k contain the k p 1 smallest elements of L and R in sorted order first part of L I for next iteration of loop Then i is incremented by 1 line 7 L i n1 and R j n2 are still unprocessed and since they are sorted L i and R j are the smallest elements of L and R that have not been copied back to A rest of L I c Balaji Raghavachari 34 Algorithm Design and Analysis 33 Algorithm Design and Analysis Correctness of Merge Initialization When entering for the first time i 1 j 1 k p lines 4 5 So A p k 1 is an empty array satisfying the first part of the L I Also L 1 and R 1 have the smallest elements of L and R repectively because L and R are sorted Maintenance when the loop is entered for k by the L I A p k 1 contains the k p smallest elements in sorted order On entering the loop we compare L i and R j line 6 c Balaji Raghavachari 35 Algorithm Design and Analysis Correctness of Merge Sort Proof by induction on the problem size n r p 1 When n 1 no work is needed to sort A p r since it is already sorted Let the algorithm sort correctly on arrays with fewer than n elements Consider n By the property of floors q r p 2 r Therefore A p q has fewer than n elements because A r is not in it and A q 1 r has fewer than n elements because A q is not in it By the I H the algorithm correctly sorts A p q and A q 1 r We just showed that given sorted arrays Merge A p q r correctly outputs a sorted array A p r Therefore the Merge sort algorithm works correctly 2 Otherwise L i R j This case is symmetric to Case 1 with roles of L i and R j reversed Termination When loop finishes k r 1 By L I A p k 1 A p r contains the r p 1 elements of L and R in sorted order Since L and R had r p 1 elements that are not none of these is the sentinel element So Merge is correct c Balaji Raghavachari Loop Invariant When loop k is entered A p k 1 contains the k p smallest elements of L and R in sorted order Moreover L i and R j are the smallest elements of L R that have not been copied into A Algorithm M erge A p q r 2
View Full Document
Unlocking...