Administrivia Lecture 4 Divide and Conquer for Sorting 2 3 1 3 HW 2 assigned this weekend due Thurs Week 4 HWs will be due Thurs of Weeks 2 4 6 7 9 10 HW 1 solutions should be posted tonight TA s have compiled them Reading for next week Chapter 9 2 3 linear time selection Chapter 33 3 4 convex hull closestpair Chapter 23 minimum spanning trees Merging Two Subsequences Divide into two equal parts Conquer solve for each part separately Combine separate solutions Mergesort Divide into two equal parts Sort each part using Mergesort recursion Merge two sorted subsequences Merge Sort Execution Example x 1 x 2 x K y 1 y 2 y L if y i x j y i 1 x j 179 310 254 179 285 285 310 179 310 310 351 652 351 351 351 423 652 423 450 861 861 520 254 652 450 450 861 520 520 285 310 285 310 179 179 179 351 652 652 351 423 254 861 423 450 254 520 450 520 520 861 285 310 310 310 285 285 179 351 652 652 351 423 351 652 652 861 254 351 450 520 450 520 K L 1 edges comparisons linear time Recursion Tree Master Method 4 3 Recurrence T n a T n b f n 1 If f n O nlog b a 12345678 1 358 15 5 2467 38 1 3 log n 47 8 7 for some 0 then T n nlog b a 26 4 6 log a 2 If f n n b then T n n logb a log n log a 3 If f n n b for some 0 and 2 a f n b c f n for some c 1 then T n f n n comparisons per level log n levels total runtime n log n 1 Master Method Examples Quicksort 7 1 7 2 8 1 8 2 Mergesort T n 2T n 2 n Sorts in place like insertion sort unlike merge sort Divide into two parts such that n log 2 2 n n Case 2 elements of left part elements of right part T n n log n Conquer recursively solve for each part separately Combine trivial do not do anything Strassen 28 2 T n 7T n 2 n2 n log 2 7 n 2 81 0 81 O n 2 Case1 Quicksort A p r if p r then q Partition A p r T n n log 2 7 n 2 807 Quicksort A p q Quicksort A q 1 r Divide Partition divide conquer left conquer right How It Works PARTITION A p r left Partition array from A p to A r with pivot A p Result All elements original A p have index i x A p i p 1 j r 1 repeat forever repeat j j 1 until A j x repeat i i 1 until A i x if i j then exchange A i A j else return j ii 5 59 67 76 11 15 11 9 10 16 9 11 959 15 10 15 16 11 15 15 16 ji ji j i Runtime of Quicksort right ijji ij j jji j j i Runtime of Quicksort Worst case every time nothing to move pivot left right end of subarray O n2 Best case every time partition in almost equal parts no worse than in given proportion O n log n 0123456789 0 Average case 123456789 n 89 Recursion Tree of QSort 8 9 2 What is the DQ Recurrence for QSort t n n 1 n j 1 to n t j 1 t n j pivots pivots equiprobable lengths of subproblems n 2 n k 0 to n 1 t k Guess t n O n log n Bound k logk 4 3 n 1 T n 1 nT n 2n 2T n T n 1 n 2 n 1 T n 2n n 1 k 0 n i log i x log xdx e i n 0 1 1 T n n 1 2 n j 1 to n 1 T i n 2 T 1 0 2 T n 1 n 1 1 2 n 1 j 1 to n T i 1 3 nT n n n 1 2 j 1 to n 1T i 2 4 n 1 T n 1 n 1 n 2 j 1 to nT i n 1 n 1 Another QSort Analysis Shift Cancel e n0 1 x 2 logee log x x 2 2 4 T n 1 n 2 n 1 T n 2 n 2 n 2 log n 2 4 t n n 2 n i 2 to n 1 c i log i c n log n cn 2 Shift Cancel cont n 1 n n 1 4 2 2 Unroll T n 2 n n 1 n 2 3 n 1 n 1 n n 1 n n 1 n 1 4 2 1 n n n 1 n n 1 n 2 n 3 n 1 n 1 n 1 n 1 2 1 n n 1 n 2 3 1 1 1 1 2 n 1 n 1 n n 1 3 3 2 n 1 Hn 1 2 H n 1 1 3 1 n ln n O 1 n Euler s constant 0 577 T n 2 n 1 ln n 3 2 O 1 T n O n log n Randomized Analysis of QSort cont At each level we compare each element to the splitter in its partition Def A successful pivot p satisfies n 8 p 7n 8 Three facts 1 E Xi E Xi linearity of expectation 2 If Pr Heads is q expected tosses up to and including first Head is 1 q family size puzzle Randomized Analysis of QSort Probability space Set of elementary events experiment outcomes Family F of subsets of called events Probability measure Pr real valued function on members of F where A A F Ac F F closed under union intersection For all A F 0 Pr A 1 Pr 1 For disjoint events A1 A2 Pr U Ai Pr Ai Random variable is a function from elements of into e g event X x set of elements of for which X assumes the fixed value x For integer valued r v X expectation E X i Pr X i Randomized Analysis of QSort cont What is number of partition steps expected between kth k 1 st successful pivots 2 4 3 steps 1 4 3 log8 7 n Each element expects to participate in O log n pivots comparisons 3 Pr U i Ai Define r v s which give comparisons for each element Ans log8 7 n So we have another analysis that gives us the O n log n expected complexity of QSort i Pr Ai prob of union sum of probs Given that Pr successful pivot 3 4 a single element ei participates in at most how many successful partitioning steps 1 get O n log n expected comparisons 3 How Badly …