Differences

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

--- courses:cs211:winter2011:journals:camille:chapter5 [2011/03/09 00:22] – [Section 3: Counting Inversions] cobbc
+++ courses:cs211:winter2011:journals:camille:chapter5 [2011/03/13 22:18] (current) – [Section 5: Integer Multiplication] cobbc
@@ Line 35: / Line 35: @@
     * **Summary:**
+This problem also uses the same techniques. Given a set of n points in a plane, find the pair that's the closest together. They talk about the history of the problem and get into notation, but I'm going to assume I'll remember that or that I'll find the notation intuitive. The 1-D problem is useful to think about. If all of the points are along a line, then you just need to sort them on the line (O(nlogn) time) and then you can go through and just look at the next point along the line and keep track of the minimum distance and which points it was between. The 2-D problem can be solved by sorting according to one coordinate, splitting the points into two halves, finding the closest two points in each half recursively, and then combining. The combining step is tricky, though, because the two closest points might have gotten split up between the two halves. Whichever of the pair of points that was closest in each half is closer, we take the distance that they are from each other, call it d, and only look at points within d of the "center" line we drew down the middle to split the points into two halves. Then there's more trickiness that goes into this that shows that we have to look at only 7 or less other points for every point in that strip (which makes that step linear). If there are two points that are closer than d in the strip, then they're the closest pair of points, otherwise we stick with the one we found before. The book goes into more formal algorithms for this and explains the trickiness of proving that you have to look at at most 7 other points for each point (remember the boxes of side length d/2). They also analyze the algorithm to prove that it actually finds the closest pair of points, and they bound the running time with O(nlogn).
     * **Insights and Questions:**
+They say that you can get the running time down to O(n) with randomization. This isn't necessarily directly in reference to this particular problem, but in general I just don't understand how randomization can help solve problems more quickly. Hmm.
     * **Readability:**
+Great! They've gotten away from the end-of-section proof that it works and analysis of running time. I'm not sure if it helps or if it would be just as good to do it as they give the algorithm, but it was interesting that it came back.
+===== Section 5: Integer Multiplication =====
+    * **Summary:**
+This problem will reduce running time by having more than two recursive calls at each level. The elementary school way of multiplying two numbers takes O(n^2) time, which is good, but it could be better. Instead of doing it that way, though, you can separate n-bit binary numbers (they say it works for other number systems, too) into two n/2-bit binary numbers (the first n/2 digits, "high-order" digits, x1 and y1 and the last n/2 digit, "low order" digits, x0 and y0). Then xy = x1y1*2^n + (x1y0+x0y1)*2^n/2 + x0y0 ... anyway, the equation's not the point. The point is that you trade multiplication for addition (which takes O(n) time). So the recurrence relation is T(n) <= 4*T(n/2) + cn, but that just gives us O(n^2) time back ... so there was no advantage to doing this. So instead, you can modify it a little so that you do determine x1y1 and x0y0 by recursion and get the outermost terms explicitly and the middle term by subtracting x1y1 and x0y0 from (x1+x0)(y1+y0). They show that algorithm. So now the recursive relation is T(n)<= 3*T(n/2)+cn, which results in an O(n^logbase2(3)) or O(n^1.59) running time, which is a significant improvement!
+    * **Insights and Questions:**
+This is a really interesting example of how differently computers and people think. There's no way it would be easier or more efficient for a human to solve this problem this way. It's also an interesting example of a tradeoff between efficiency and intuitiveness ... hmm.
+    * **Readability:**
+I thought that, once again, this section was very readable!