Lecture 2: Divide and Conquer

Lecture 2 6.046J Spring 2015 Divide and Conquer Lecture 2: Divide and Conquer • Paradigm • Convex Hull • Median finding Paradigm Given a problem of size n divide it into subproblems of size nb , a ≥ 1, b > 1. Solve each subproblem recursively. Combine solutions of subproblems to get overall solution. n T (n) = aT ( ) + [work for merge] b Convex Hull Given n points in plane S = {(xi , yi )|i = 1, 2, . . . , n} assume no two have same x coordinate, no two have same y coordinate, and no three in a line for convenience. Convex Hull ( CH(S) ): smallest polygon containing all points in S. q p r v u s t CH(S) represented by the sequence of points on the boundary in order clockwise as doubly linked list. 1 Lecture 2 6.046J Spring 2015 Divide and Conquer p q r s t Brute force for Convex Hull Test each line segment to see if it makes up an edge of the convex hull • If the rest of the points are on one side of the segment, the segment is on the convex hull. • else the segment is not. O(n2 ) edges, O(n) tests ⇒ O(n3 ) complexity Can we do better? Divide and Conquer Convex Hull Sort points by x coord (once and for all, O(n log n)) For input set S of points: • Divide into left half A and right half B by x coords • Compute CH(A) and CH(B) • Combine CH’s of two halves (merge step) How to Merge? a4 A B b2 a5 a1 b1 a2 b3 a3 L • Find upper tangent (ai , bj ). In example, (a4 , b2 ) is U.T. • Find lower tangent (ak , bm ). In example, (a3 , b3 ) is L.T. 2 Lecture 2 6.046J Spring 2015 Divide and Conquer • Cut and paste in time Θ(n). First link ai to bj , go down b ilst till you see bm and link bm to ak , continue along the a list until you return to ai . In the example, this gives (a4 , b2 , b3 , a3 ). Finding Tangents Assume ai maximizes x within CH(A) (a1 , a2 , . . . , ap ). b1 minimizes x within CH(B) (b1 , b2 , . . . , bq ) L is the vertical line separating A and B. Define y(i, j) as y-coordinate of inter­ section between L and segment (ai , bj ). Claim: (ai , bj ) is uppertangent iff it maximizes y(i, j). If y(i, j) is not maximum, there will be points on both sides of (ai , bj ) and it cannot be a tangent. Algorithm: Obvious O(n2 ) algorithm looks at all ai , bj pairs. T (n) = 2T (n/2) + Θ(n2 ) = Θ(n2 ). 1 i=1 2 j=1 3 while (y(i, j + 1) > y(i, j) or y(i − 1, j) > y(i, j)) 4 if (y(i, j + 1) > y(i, j)) [ move right finger clockwise 5 j = j + 1( mod q) 6 else 7 i = i − 1( mod p) [ move left finger anti-clockwise 8 return (ai , bj ) as upper tangent Similarly for lower tangent. n T (n) = 2T ( ) + Θ(n) = Θ(n log n) 2 Intuition for why Merge works ap-1 b4 bq bq-1 b2 ap a2 b3 a1 b1 3 Lecture 2 Divide and Conquer 6.046J Spring 2015 a1 , b1 are right most and left most points. We move anti clockwise from a1 , clockwise from b1 . a1 , a2 , . . . , aq is a convex hull, as is b1 , b2 , . . . , bq . If ai , bj is such that moving from either ai or bj decreases y(i, j) there are no points above the (ai , bj ) line. The formal proof is quite involved and won’t be covered. Median Finding Given set of n numbers, define rank(x) as number of numbers in the set that are ≤ x. Find element of rank l n+1 J (lower median) and I n+1 l (upper median). 2 2 Clearly, sorting works in time Θ(n log n). Can we do better? B x C k - 1 elements h - k elements Select(S, i) 1 2 3 4 5 6 7 8 9 10 Pick x ∈ S [ cleverly Compute k = rank(x) B = {y ∈ S|y < x} C = {y ∈ S|y > x} if k = i return x else if k > i return Select(B, i) else if k < i return Select(C, i − k) Picking x Cleverly Need to pick x so rank(x) is not extreme. • Arrange S into columns of size 5 (I n5 l cols) • Sort each column (bigger elements on top) (linear time) • Find “median of medians” as x 4 Lecture 2 6.046J Spring 2015 Divide and Conquer >x larger medians x smaller x? Half of the I n5 l groups contribute at least 3 elements > x except for 1 group with less than 5 elements and 1 group that contains x. n n At lease 3(I 10 l − 2) elements are > x, and at least 3(I 10 l − 2) elements are < x Recurrence: O(1), T (n) = for n ≤ 140 T (I n5 l) + T ( 710n + 6), Θ(n), for n > 140 (1) Solving the Recurrence Master theorem does not apply. Intuition n5 + 710n < n. Prove T (n) ≤ cn by induction, for some large enough c. True for n ≤ 140 by choosing large c n 7n T (n) ≤ cI l + c( + 6) + an 5 10 cn 7nc ≤ +c+ + 6c + an 5 10 cn = cn + (− + 7c + an) 10 If c ≥ 70c n + 10a, we are done. This is true for n ≥ 140 and c ≥ 20a. 5 (2) (3) (4) Lecture 2 6.046J Spring 2015 Divide and Conquer Appendix 1 Example b2 b1 b4 a4 b3 a3 a2 L a1 a3 , b1 is upper tangent. a4 > a3 , b2 > b1 in terms of Y coordinates. a1 , b3 is lower tangent, a2 < a1 , b4 < b3 in terms of Y coordinates. ai , bj is an upper tangent. Does not mean that ai or bj is the highest point. Similarly, for lower tangent. 6