=========================================================================== CSC 236 Lecture Summary for Week 6 Winter 2012 =========================================================================== ------------------ Divide and Conquer ------------------ General divide-and-conquer recurrences: - "Master Theorem": If T(n) satisfies recurrence { K if n <= B T(n) = { { a_1 T(ceil(n/b)) + a_2 T(floor(n/b)) + f(n) if n > B for constants K > 0, a_1 >= 0, a_2 >= 0, b > 1, B > 0, and f(n) in Theta(n^d) for constant d >= 0, then { Theta(n^d) if a < b^d, T(n) = { Theta(n^d log n) if a = b^d, { Theta(n^{log_b a}) if a > b^d. - Same technique can be used to prove upper/lower bounds: f(n) in O(n^d) or Omega(n^d) implies T(n) in O(...) or Omega(...) (same expressions as in Master Theorem), respectively. - Example: MergeSort worst-case time { 1 if n <= 1, T(n) = { { T(ceil(n/2)) + T(floor(n/2)) + 2n + 1 if n > 1, has the right form, with K = 1, a = 2, b = 2, d = 1, so a = b^d and Master Theorem states T(n) in Theta(n^d log n) = Theta(n log n). - Master Theorem also applies to RecBinSearch runtime, with K = 2, a = 1, b = 2, d = 0; so a = b^d and T(n) in Theta(n^d log n) = Theta(log n). Integer multiplication. - Problem: Multiply two large integers x, y, given as sequences of bits x_0,x_1,...,x_{n-1}; y_0,y_1,...,y_{n-1} (low-order bit first, i.e., x = x_{n-1} ... x_1 x_0 in binary, and similarly for y). - Iterative algorithm: Multiply x by each bit of y, shifted appropriately, then add the n results to each other. Runtime = Theta(n^2) (n additions of up to 2n bits each). - Idea: Let X_0 = x_{n/2-1} ... x_1 x_0 and X_1 = x_{n-1} ... x_{n/2}, in binary (if necessary, make n even by adding an additional 0 to the left of x); define Y_0 and Y_1 similarly. Then, x = 2^{n/2} X_1 + X_0 and y = 2^{n/2} Y_1 + Y_0, and we can write x y = 2^n X_1 Y_1 + 2^{n/2} X_1 Y_0 + 2^{n/2} X_0 Y_1 + X_0 Y_0 How does this help? Original problem (compute x y) reduced to four subproblems of half size (compute X_1 Y_1, X_1 Y_0, X_0 Y_1, X_0 Y_0), together with some "shift" operations (multiplication by power of 2) and binary additions-- linear time operations. This yields recursive algorithm directly. Multiply(x, y, n): # x, y are lists of size n if n = 1: return x * y # multiplication of 1-bit numbers else: set lists X1, X0, Y1, Y0 as explained above p1 = Multiply(X1, Y1, n/2) p2 = Multiply(X1, Y0, n/2) p3 = Multiply(X0, Y1, n/2) p4 = Multiply(X0, Y0, n/2) return 2^n p1 + 2^{n/2} p2 + 2^{n/2} p3 + p4 Runtime? Recursive algorithm yields recurrence relation for worst-case runtime T(n): T(1) = Theta(1), T(n) = 4 T(n/2) + Theta(n) for n > 1, where 4 T(n/2) comes from the time spent executing the four recursive calls, and Theta(n) comes from the time spent performing shifts and binary additions (in addition to initial splitting of input into sublists). Master Theorem applies to T(n), with a = 4, b = 2, d = 1. Since a = 4 > 2 = b^d, we have T(n) = Theta(n^{log_2 4}) = Theta(n^2). No better than simple iterative algorithm! - Trick: using same notation as before, notice that (X_1 + X_0) (Y_1 + Y_0) = X_1 Y_1 + X_1 Y_0 + X_0 Y_1 + X_0 Y_0. This is almost correct expression, except for shifts, and it involves only 1 multiplication instead of 4. Because terms X_1 Y_0 and X_0 Y_1 shift by same amount, we can use this to save one recursive call: x y = 2^n X_1 Y_1 + X_0 Y_0 + 2^{n/2} ( (X_1 + X_0) (Y_1 + Y_0) - X_1 Y_1 - X_0 Y_0 ) - This yields following recursive algorithm: Multiply2(x, y, n): if n = 1: return x * y else: set lists X1, X0, Y1, Y0 as explained above p1 = Multiply2(X1, Y1, n/2) p2 = Multiply2(X1 + X_0, Y_1 + Y0, n/2 + 1) p3 = Multiply2(X0, Y0, n/2) return 2^n p1 + 2^{n/2} (p2 - p1 - p3) + p_3 with runtime T'(n) that satisfies: T'(n) = 1, T'(n) = 3 T'(n/2) + n (This is not exactly right because one of the recursive calls is for input size n/2 + 1. But just like floors and ceilings, this does not affect the final answer.) The constant hidden by the term Theta(n) is larger than for the first recursive algorithm (we perform more binary additions), but the Master Theorem still applies with a = 3, b = 2, d = 1, which yields T'(n) = Theta(n^{log_2 3}) = Theta(n^{1.58...}). Strictly better than previous Theta(n^2)! - Picture of savings from 4 T(n/2) to 3 T'(n/2). - In practice, best known algorithm for integer multiplication is "Fast Fourier Transform" (FFT) algorithm-- a more complicated divide-and-conquer algorithm-- with runtime Theta(n log n log log n). Closest points. - Given points p_1 = (x_1,y_1), ..., p_n = (x_n,y_n), find a pair i,j such that d(p_i,p_j) is minimal (d(p,q) = distance from p to q). - Assumption: No two points with same x or y coordinate. (Can be eliminated but makes presentation simpler.) - Brute force: compare all distances. There are (n choose 2) = Theta(n^2) pairs so takes time Theta(n^2). - Idea: Divide points into two halves, find closest pairs in each half, find closest pair across the two halves, and return closest overall. Issue: How to find closest pair across two halve faster than trying all Theta(n^2) pairs with one point in each half? Divide-and-conquer strategy has runtime T(n) = 2 T(n/2) + Theta(n^d), which works out to be less than Theta(n^2) iff d < 2, i.e., need to find closest pair across halves in time o(n^2). - Details: Input consists of . P = set of points, . P_x = list of points sorted by x-coordinate, . P_y = list of points sorted by y-coordinate, with cross-references between the lists, i.e., element at index i in P_x stores its index in list P_y and vice-versa, for quick lookup. - Divide: Split P horizontally (along x axis) into . Q = leftmost n/2 points, . R = rightmost n/2 points, . (lists Q_x, Q_y, R_x, R_y can be computed from P_x, P_y in linear time). - Recurse: Recursively find . q_0, q_1: closest points in Q, . r_0, r_1: closest points in R. - Combine: Let \delta = min( d(q_0,q_1), d(r_0,r_1) ). Want to find points q (- Q, r (- R with d(q,r) < \delta, if any. Consider any vertical line L that "splits" Q and R (i.e., with x-coordinate between rightmost point in Q and leftmost point in R). If there are points q (- Q, r (- R with d(q,r) < \delta, then q,r both lie within distance \delta of L (because d(q,r) < \delta means horizontal q-r distance also < \delta and so is distance to L). Fix line L and let S = { all points in P within distance \delta of L }. S_x and S_y can be constructed in linear time from P_x, P_y. Fact: If points q (- Q, r (- R have d(q,r) < \delta, then q, r appear within 15 positions of each other in S_y! Proof: Imagine a square grid with side length \delta/2 on either side of L. No two points in P can belong to the same square (because then they would be on the same side of L and distance < \delta apart). This means every square of the grid contains at most one point, and even if every square did contain a point (something that cannot actually happen), any two points 15 squares away from each other are further apart than \delta. [This is a lot easier to see with a picture, but I won't try to draw it in ASCII!] - Final algorithm: . construct P_x, P_y (time Theta(n log n)) . (p_0,p_1) = ClosestPairRec(P_x, P_y) ClosestPairRec(P_x, P_y): if |P| <= 3: find closest points by brute force else: construct Q_x, Q_y, R_x, R_y (time Theta(n)) (q_0,q_1) = ClosestPairRec(Q_x, Q_y) (time T(n/2)) (r_0,r_1) = ClosestPairRec(R_x, R_y) (time T(n/2)) \delta = min{ d(q_0,q_1), d(r_0,r_1) } m = average of rightmost x-coordinate in Q and leftmost x-coordinate in R construct S_x, S_y as defined above (time Theta(n)) for each s (- S_y, compute distance to next 15 points in S_y and let (s_0,s_1) be closest pair found return closest of (q_0,q_1) or (r_0,r_1) or (s_0,s_1) - Runtime: T(n) = 2 T(n/2) + Theta(n) => T(n) = Theta(n log n).