Divide Divide and and Conquer Conquer Merge Merge Sort Sort Comp 122 Spring 2004 Divide and Conquer Recursive in structure Divide the problem into sub problems that are similar to the original but smaller in size Conquer the sub problems by solving them recursively If they are small enough just solve them in a straightforward manner Combine the solutions to create a solution to the original problem 2 Comp 122 An Example Merge Sort Sorting Problem Sort a sequence of n elements into non decreasing order Divide Divide the n element sequence to be sorted into two subsequences of n 2 elements each Conquer Sort the two subsequences recursively using merge sort Combine Merge the two sorted subsequences to produce the sorted answer 3 Comp 122 Merge Sort Example Original Sequence Sorted Sequence 18 26 32 6 43 15 9 1 1 18 26 32 6 43 15 9 1 6 18 26 32 1 18 26 32 6 43 15 9 1 18 26 15 43 1 9 18 26 32 6 43 15 9 1 18 26 32 43 15 9 1 18 26 32 6 43 15 9 1 5 Comp 122 6 9 15 18 26 32 43 6 32 6 9 15 43 43 Merge Sort A p r INPUT a sequence of n numbers stored in array A OUTPUT an ordered sequence of n numbers MergeSort A p r sort A p r by divide conquer 1 if p r 2 then q p r 2 3 MergeSort A p q 4 MergeSort A q 1 r 5 Merge A p q r merges A p q with A q 1 r Initial Call MergeSort A 1 n 6 Comp 122 Procedure Merge Merge A p q r 1 n1 q p 1 2 n2 r q 3 for i 1 to n1 4 do L i A p i 1 5 for j 1 to n2 6 do R j A q j 7 L n1 1 8 R n2 1 9 i 1 10 j 1 11 for k p to r 12 do if L i R j 13 then A k L i 14 i i 1 15 else A k R j 16 j j 1 7 Input Array containing sorted subarrays A p q and A q 1 r Output Merged sorted subarray in A p r Sentinels to avoid having to check if either subarray is fully copied at each step Comp 122 Merge Example A L 6 i 8 61 86 26 1 32 9 42 43 8 32 9 26 k k k 8 26 32 i i i k k R i Comp 122 k k k k 1 9 42 43 j j j j j Correctness of Merge Merge A p q r 1 n1 q p 1 2 n2 r q 3 for i 1 to n1 4 do L i A p i 1 5 for j 1 to n2 6 do R j A q j 7 L n1 1 8 R n2 1 9 i 1 10 j 1 11 for k p to r 12 do if L i R j 13 then A k L i 14 i i 1 15 else A k R j 16 j j 1 9 Loop Invariant for the for loop At the start of each iteration of the for loop Subarray A p k 1 contains the k p smallest elements of L and R in sorted order L i and R j are the smallest elements of L and R that have not been copied back into A Initialization Before the first iteration A p k 1 is empty i j 1 L 1 and R 1 are the smallest elements of L and R not copied to A Comp 122 Correctness of Merge Merge A p q r 1 n1 q p 1 2 n2 r q 3 for i 1 to n1 4 do L i A p i 1 5 for j 1 to n2 6 do R j A q j 7 L n1 1 8 R n2 1 9 i 1 10 j 1 11 for k p to r 12 do if L i R j 13 then A k L i 14 i i 1 15 else A k R j 16 j j 1 10 Maintenance Case 1 L i R j By LI A contains p k smallest elements of L and R in sorted order By LI L i and R j are the smallest elements of L and R not yet copied into A Line 13 results in A containing p k 1 smallest elements again in sorted order Incrementing i and k reestablishes the LI for the next iteration Similarly for L i R j Termination On termination k r 1 By LI A contains r p 1 smallest elements of L and R in sorted order L and R together contain r p 3 elements All but the two sentinels have been copied back into A Comp 122 Analysis of Merge Sort Running time T n of Merge Sort Divide computing the middle takes 1 Conquer solving 2 subproblems takes 2T n 2 Combine merging n elements takes n Total T n 1 if n 1 T n 2T n 2 n if n 1 T n n lg n CLRS Chapter 4 11 Comp 122 Recurrences Recurrences II Comp 122 Spring 2004 Recurrence Relations Equation or an inequality that characterizes a function by its values on smaller inputs Solution Methods Chapter 4 Substitution Method Recursion tree Method Master Method Recurrence relations arise when we analyze the running time of iterative or recursive algorithms Ex Divide and Conquer T n 1 T n a T n b D n C n 13 Comp 122 if n c otherwise Substitution Method Guess the form of the solution then use mathematical induction to show it correct Substitute guessed answer for the function when the inductive hypothesis is applied to smaller values hence the name Works well when the solution is easy to guess No general way to guess the correct solution 14 Comp 122 Example Exact Function Recurrence T n 1 T n 2T n 2 n Guess T n n lg n n Induction if n 1 if n 1 Basis n 1 n lgn n 1 T n Hypothesis T k k lg k k for all k n Inductive Step T n 2 T n 2 n 2 n 2 lg n 2 n 2 n n lg n 2 2n n lg n n 2n n lg n n 15 Comp 122 Recursion tree Method Making a good guess is sometimes difficult with the substitution method Use recursion trees to devise good guesses Recursion Trees Show successive expansions of recurrences using trees Keep track of the time spent on the subproblems of a divide and conquer algorithm Help organize the algebraic bookkeeping necessary to solve a recurrence 16 Comp 122 Recursion Tree Example Running time of Merge Sort T n 1 T n 2T n 2 n if n 1 if n 1 …