Differences

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

--- courses:cs211:winter2011:journals:wendy:chapter5 [2011/03/09 13:35] – [Section 4: Finding the Closest Pair of Points] shangw
+++ courses:cs211:winter2011:journals:wendy:chapter5 [2011/03/14 00:52] (current) – shangw
@@ Line 37: / Line 37: @@
 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.