Administrivia Lecture 4 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 Divide and Conquer for Sorting 2 3 1 3 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 Merging Two Subsequences x 1 x 2 x K y 1 y 2 y L if y i x j y i 1 x j K L 1 edges comparisons linear time Merge Sort Execution Example 179 310 254 285 310 285 179 310 351 652 351 652 423 450 861 520 254 652 450 861 520 520 310 285 310 179 179 351 652 652 351 423 254 861 423 254 450 450 520 861 310 285 310 310 285 285 351 423 652 179 351 652 652 351 652 351 861 254 450 520 450 520 Recursion Tree 12345678 1 358 15 5 2467 38 1 3 log n 47 8 7 26 4 n comparisons per level log n levels total runtime n log n 6 2 Master Method 4 3 Recurrence T n a T n b f n log a 1 If f n O n b for some 0 then T n n logb a logb a f n n 2 If logb a T n n log n then logb a f n n for some 0 and 3 If a f n b c f n for some c 1 then T n f n Master Method Examples Mergesort T n 2T n 2 n n log 2 2 n n Case 2 T n n log n Strassen 28 2 T n 7T n 2 n2 n log 2 7 n 2 81 0 81 O n 2 Case 1 T n n log 2 7 n 2 807 Quicksort 7 1 7 2 8 1 8 2 Sorts in place like insertion sort unlike merge sort Divide into two parts such that elements of left part elements of right part Conquer recursively solve for each part separately Combine trivial do not do anything Quicksort A p r if p r then q Partition A p r Quicksort A p q Quicksort A q 1 r divide conquer left conquer right Divide Partition PARTITION A p r 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 How It Works left ii right 5 59 67 76 11 15 11 9 10 16 9 11 95 15 10 15 16 11 15 16 iij j i ji i ijji ij jj jji j j Runtime of Quicksort Worst case every time nothing to move pivot left right end of subarray O n2 0123456789 0 123456789 n 89 Recursion Tree of QSort 8 9 Runtime of Quicksort Best case every time partition in almost equal parts no worse than in given proportion O n log n Average case What is the DQ Recurrence for QSort t n n pivots 1 n j 1 to n t j 1 t n j pivots equiprobable lengths of subproblems n 2 n k 0 to n 1 t k Guess t n O n log n n 1 Bound k log k k 0 n 1 n x 2 log ee i log ei x log exdx log x x 2 2 4 i n 0 1 n 0 1 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 Another QSort Analysis Shift Cancel 1 T n n 1 2 n j 1 to n 1T i n 2 T 1 0 2 T n 1 n 1 1 2 n 1 j 1 to nT 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 4 3 n 1 T n 1 nT n 2n 2T n T n 1 n 2 n 1 T n 2n n 1 T n 1 n 2 n 1 T n 2 Shift Cancel cont n 1 n n 1 4 2 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 Hn 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 Unroll T n 2 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 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 3 Pr Ui Ai 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 Ans log8 7 n 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 Define r v s which give comparisons for each element 1 get O n log n expected comparisons So we have another analysis that gives us the O n log n expected complexity of QSort How Badly Can We Deviate From Expectation E g what is Pr ith element sees 20 log n pivots How …