Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision |
| courses:cs211:winter2011:journals:david:chapter5 [2011/03/02 06:07] – [5.3 - Counting Inversions] margoliesd | courses:cs211:winter2011:journals:david:chapter5 [2011/03/09 04:18] (current) – [5.5 - Integer Multiplication] margoliesd |
|---|
| |
| Readability: 7/10 The algorithm became more clear after doing this writeup. | Readability: 7/10 The algorithm became more clear after doing this writeup. |
| | |
| | ====5.4 - Finding the Closest Pair of Points==== |
| | |
| | Our problem is how to find the closest pair of points on a plane, which can be solved using brute force in O(n<sup>2</sup>) time. If we consider the one-dimensional version of this problem, we can see that sorting the points and calculating a distance for each set of consecutive points will give us the closest pair in O(nlogn) time. We use a divide and conquer approach to find the closest pair of points in the right and left halves of the set. We keep two orderings of points for each half, one using the x-coordinate and the other using the y-coordinate. Once we have the shortest distance of the left and right sides, we must consider pairs of points that straddle the center line. We only need to consider points within the our smallest distance measurement on each side of the center line, and we order them by increasing y-value. We only need to calculate distances for points that are within 15 positions of each other in this y-ordering, because any more and they would be more than the previously established smallest distance (delta) apart. The algorithm runs in O(nlogn) time. |
| | |
| | Readability: 6/10. Rereading this section a few times helped my understanding, so I'd rate my understanding at an 8/10 now. |
| | |
| | ====5.5 - Integer Multiplication==== |
| | |
| | When considering the standard elementary way of multiplying two numbers, we get an efficiency of O(n<sup>2</sup>). Our first attempt at a solution is to break up each number into its higher order half and its lower order half. We then compute the products of each set of bits and add them together, which means we have broken our problem into 4 recursive calls. Unfortunately, this still gives O(n<sup>2</sup>) efficiency. To find a more efficient solution, we need to break the problem up into less than 4 recursive calls. The trick is to subtract the sum of the product of the first two halves and the last two halves from the total product. This gives us only 3 recursive calls, and an efficiency of O(N<sup>1.59</sup>). |
| | |
| | Readability: 7/10 |
