Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2011:journals:wendy:chapter5 [2011/03/09 06:20] – shangw
+++ courses:cs211:winter2011:journals:wendy:chapter5 [2011/03/14 00:52] (current) – shangw
@@ Line 34: / Line 34: @@
 ===== Section 4: Finding the Closest Pair of Points =====
 Here is another application of the divide conquer algorithm.
-The general idea is to divide the plane into two parts, find out the minimum distance of each part, compare both with the distances between points beside the boundary of the two planes and hence get a minimum distanced pair of the combined plane.
+The general idea is to divide the plane into two parts, find out the minimum distance of each part, compare both with the distances between points beside the boundary of the two planes and hence get a minimum distanced pair of the combined plane. The most difficult part to implement is the combining part. First it is not hard to conceive that let x be the smaller distance from the two planes to be combined, if the new minimum distance comes from between points from the two planes, then the points have to locate from the strip centered at the splitting vertical line with wideth 2x. Sort the points inside the strip according to their y coordinate in ascending order. Another smart observation is if si, sj are two points in the strip and |i-j|>=15 (or 12, or 7, the key is it to be a constant), then they must be apart more than x--I think it is very clever. This enables us to for each point only scan the 7 neighborhood above instead the entire collection of points in the strip, which only takes linear time instead of quadratic time. Hence the recursive relation is:
+T(n)<=2T(n/2)+O(nlogn) (for sorting the points in the strip). =O(logn^2n)
+Readability is 8.
+===== Section 5: Integer Multiplication =====
+This section introduces another problem that uses the divide conquer algorithm--integer multiplication.
+This seemingly straight forward problem actually takes O(n^2) if using brute-force algorithm. But we can improve the running time using divide and conquer method.
+The first try is to divide the original problem into 4 subproblems:
+xy=x1y1+(x1y0)2^n/2+(x0y1)2^n/2+x0y0.
+However, the recurrence relationship T(n)<=4T(n/2)+cn is still only bounded by O(n^2). But notice that if we only use 3 subproblems instead of 4, the running time can be reduced. We need to look at the problem slightly differently:
+xy=x1y1+(x1y1+x0y0+x1y0+x0y1-x1y1+x0y0)2^n/2+x0y0.
+=x1y1+(p-x1y1-x0y0)2^n/2+x0y0
+where p=(x0+x1)(y0+y1).
+Now the recurrence relationship is T(n)<=3T(n/2)+cn<=O(n^1.59)
+Readability is 7.