Administrivia Lecture 5 HW 2 was assigned on Sunday January 20 It is due on Thursday January 31 Please use the correct edition of the textbook We have a quiz this Thursday 20 minutes at the beginning of lecture The DQMaxMin problem is treated in CLRS 9 1 Grading will drop the single worst HW or quiz Selection Recall best pivot in QSort is the median It is too expensive to find the median we use a random element as the pivot instead This leads to SELECTION Given a list L and a number k Select L k returns the kth smallest element of L e g when k L 2 Select L k returns the median What is an efficient algorithm Sorting finding kth smallest O n log n can do better D Q Recursion use the pivot from QSort Randomized Select CLRS 9 2 page 186 if i k look in right part for k i th smallest if i k look in left part for kth smallest Analysis of Randomized Select 9 2 Average case time complexity 1 n 1 T n T max k n k O n n k 1 2 n 1 T k O n n k n 2 Inductive hypothesis T n c n 2 n 1 2c n 1 T n ck O n k n k n 2 n k 1 Want n 2 1 k O n cn k 1 Need for induction step Analysis of Randomized Select 9 2 p 188 Want 2 n 1 2c n 1 T n ck O n k n k n 2 n k 1 n 2 1 k an k 1 2c n 1 n n 2 2 n 2 1 an n 2 2 2c n 2 n n 2 4 3n 2 2 an n 2 2 c 3n 2 n n 4 2 3n 1 2 2 an c an 4 2 n 3cn c cn c an cn an 4 2 average case 4 2 cn cn 4 c 2 an 0 n c 4 a c 2 Choose c s t c 4 a 0 c 4a T n O n Randomized Selection Worst case n2 as in QSort analysis But Suppose we can guarantee a good pivot e g such that n 4 i 3n 4 subproblem size 3n 4 Let s n time to find good pivot t n s n cn t 3n 4 s n find pivot cn pivot make subproblem t 3n 4 solve subproblem Randomized Selection Suppose further S n dn for some d t n c d n t 3n 4 Claim t n kn for some k would follow Again we use Constructive Induction Substitution Induction Hypothesis t m km for m n 1 Induction Step t n c d n k 3n 4 c d 3k 4 n which we want to be equivalent to t n kn But this is true if k 4 c d Worst Case Linear Time Selection 9 3 Of mostly theoretical interest How to find a good median in linear time divide into groups of 5 c1n find the median of each group c2n 5 find the median of medians recursively T n 5 Pivoting around this element gives at worst 3 7 split Worst Case Linear Time Selection Blum Floyd Pratt Rivest Tarjan 1973 divide L into groups of 5 c1n find the median of each group c2n 5 Let S array of medians of each group c3n find median of medians i e median of S recursively use as pivot t n 5 Total work t n kn t n 5 t 7n 10 d In general a n kn a 1n a 2n a 3n with k 1 2 3 constants s t 1 2 3 1 then a n c n for some c t n O n More Careful Exposition Recursive call has size 7n 10 6 CLRS p 191 T n 1 n M M 140 T n T n 5 T 7n 10 6 O n n M Prove linearity by substitution Assume T n cn for some constant c and for all n M T n cn 5 c 7n 10 6 an cn 5 c 7cn 10 6c an 9cn 10 7c an cn cn 10 7c an The induction step goes through if cn 10 7c an 0 pick c large enough so that c n 10 7 an n M D Q for Arithmetic Multiplying Large Integers Karatsuba Ofman A a0 r1a1 rn 1an 1 r radix classic approach n2 work Can we apply D Q Let n 2s r 10 radix AB xz 10s wz xy 102swy T n 4T n 2 n a 4 b 2 in Master Method T n n2 Need to reduce subproblems i e want a 4 Observation r w x y z wy wz xy xz r w x y z p wy q xz return 102sp 10s r p q q T n O n log23 O n1 59 Matrix Multiplication A B are n x n matrices a11 a12 etc are n 2 x n 2 submatrices M AB where m11 a11b11 a12b21 etc Evaluation requires 8 multiplies 4 adds T n 8T n 2 O n n3 Strassen s Matrix Multiplication p1 a21 a22 a11 b22 b12 b11 p2 a11b11 p3 a12b21 p4 a11 a21 b22 b12 p5 a21 a22 b12 b11 p6 a12 a21 a11 a22 b22 p7 a22 b11 b22 b12 b21 AB11 p2 p3 AB12 p1 p2 p5 p6 AB21 p1 p2 p4 p7 AB22 p1 p2 p4 p5 T n n2 81 7 multiplies 24 adds Can get to 15 adds Break Question Given the adjacency matrix of an undirected graph describe a fast algorithm that finds all triangles in the graph Why am I asking this now A Computational Geometry Excursion Given simple polygon P is x in P n Given n points in the plane draw a simple n gon through them n log n Given n points in the plane return their convex hull n log n Does it matter whether we must return vertices or return the polygon Given n points in the plane return the closest pair n log n Given n h v segments return all intersections O f n g k where k output size plane sweep inductive paradigm DQ Closest Pair Na ve n2 D Q Approach n log n 1 Split into two pointsets S1 S2 by x coord natural order 2 Find closest pair distances d1 d2 in S1 S2 respectively without loss of generality can assume d1 d2 3 Merge the solutions Do we have to check all s1 s2 pairs s1 S1 s2 S2 What if there are lots of points in middle strip Key Step 3 Observation There are at most O 1 points in middle strip with y d1 DQ Closest Pair 1 sort by x coord tool one time sort O n log n 2 solve subproblems of size n 2 2T n 2 3 eliminate points outside strips O n 4 sort by y coord within strips O n log …