Differences

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

--- courses:cs211:winter2014:journals:haley:chapter5 [2014/03/12 02:21] – archermcclellanh
+++ courses:cs211:winter2014:journals:haley:chapter5 [2014/03/12 02:35] (current) – archermcclellanh
@@ Line 27: / Line 27: @@
     * In ranking systems, we want to be able to count the inversions between two different rankings of the same objects. That is, if we take one list of rankings, we want to tell how many inversions are required to get to the other one.
-    *
+    * We recursively sort the list to be counted and the n find its inversions by merging back up.
+    * We sort the lists recursively, counting the number of inversions, then add the inversions for merging.
+    * We merge by maintaining a pointer into each list, initialized to the front. We keep count of the inversions. While neither list is empty, we add the smaller item being pointed to to the output list, and if the item in the rightmost list is smaller, we increment the number of inversions.
+    * This runs in O(nlogn) time for an n-element list.
+===== 5.4: Finding Closest Points =====
+    * Consider a collection of n points in (x,y) space. We want to find the pair of points that are closest.
+    * We start by sorting those points in increasing x order.
+    * We then find the two points in the middle of the list of points and imagine a vertical line between them.
+    * We find the closest points on each side of the line
+    * We then find the closest points across the line, that is, the points closer together than the closest points on either side of the line.
+        * Let d be the minimum distance between two points on either side.
+        * Then we only have to look within d on each side of the line.
+        * We divide this into d/2 by d/2 boxes, and for each box check the next 7 closest boxes.
+    * This only takes O(nlogn) time? DANG.