Differences

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

--- courses:cs211:winter2011:journals:anna:chapter_5 [2011/03/08 22:22] – poblettsa
+++ courses:cs211:winter2011:journals:anna:chapter_5 [2011/03/15 14:22] (current) – poblettsa
@@ Line 28: / Line 28: @@
 === 5.4 Finding the Closest Pair of Points ===
+This problem is simply to find the closest two points in a plane with n points.  The brute force solution is to look at all pairs of points, which takes O(n^2) time.  Assuming no two points have the same x-coordinate, you can order the points by their x-coordinate and draw a line to divide the points in half.  Then you can find the smallest distance between two points on the same side.  The tricky part is looking at the distances between points on opposite sides.  If d is the minimum of the shortest distances on either side, then you only need to look at points within d of the center line when looking at distances between the two sides.
+In this step, it turns out we can bound the number of comparisons to 12 (to start with).  If we divide the 2d area into boxes of 1/2d we can first of all guarantee that there will only be one point per box.  Then we only need to look at boxes that are within 2 of the point.  This limits us to 12.  We can do even better by eliminating the boxes on the same side of the dividing line, which brings us down to a max of 7 comparisons.  Thus, our algorithm, on page 230, will run in O(n logn) time.
+=== 5.5 Integer Multiplication ===
+The problem in this section is that of basic integer multiplication.  However, when you look at the details of what you do when you multiply 2 n digit integers, you see that you take a lot of small partial products which result in a running time of O(n^2).  The main objective of this section is to determine if we actually need all these partial products, because if we don't, we would be able to reduce the running time.  If we break up each integer(so we would have 4 n/2 digit numbers), we could do four partial products to determine x*y, as on page 232.  Unfortunately, it turns out this still runs in quadratic time like normal integer multiplication.
+Therefore, we want to only do three partial products if we want to reduce the running time of our algorithm.  This would mean we would have a recurrence relation with q = 3, which would give a running time of O(n^1.59).  The key to this algorithm is to look at (x1 + x0)(y1 + y0), where x is the first integer, y is the second integer, 0 refers to the high-end of the number, and 1 refers to the low-end of the number.  The solution to this multiplication is four partial products added together with only one recursive call, making it easier to get the partial products we need.  This algorithm is on page 233.