===========================================================================
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).