Differences

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

--- courses:cs211:winter2014:journals:colin:chapter5 [2014/03/05 20:26] – mohnacsc
+++ courses:cs211:winter2014:journals:colin:chapter5 [2014/03/12 05:56] (current) – [5.4 - Finding the Closest Pair of Points] mohnacsc
@@ Line 13: / Line 13: @@
+==== 5.2 - Further Recurrence Relations ====
+In the case of a tree where q > 2 (q being number of children), the work increases with every level of recursion.  This gives q^j instances at level j.  A function with q > 2 is bounded by O(n^log2(q)).  For example, when q=2, running time is O(n^4).
+Consider the case where q=1.  The work per level decreases with recursion.  At an arbitrary level j, it contributes cn/2^j to the run time.  A function with q=1 is bounded by O(n) run time.
+q = 1: O(n) - linear
+q = 2: O(n log n)
+q > 2: polynomial with exponent > 1
+==== 5.3 - Counting Inversions ====
+An inversion occurs when an ordering of numbers has numbers out of order.  There may be a quadratic number of inversions for each set of numbers.  The algorithm is similar to Mergesort except we count inversions along with sorting the list.  Recursively divide the list and sort separate halves.  Compare the sorted halves against each other for inversions.
+When merging the list, we compare elements in subsets A and B.  If the element in A is smaller, it is appended to the new list and no inversions occur.  If B is smaller, it is appended to the list and the number of remaining elements in A is the number of inversions because they come before elements in B.  This is the Sort-and-Count algorithm runs in O(n log n) time.
+==== 5.4 - Finding the Closest Pair of Points ====
+Given n points in the plane, find the pair that is closest together.  This is done by dividing and comparing the closest points in each half.  We sort the points by the x- and y-coordinates in two separate lists.  The two lists are divided again into left and right sides of the plane.  Determine a closest pair of points on each side.  If there exists a pair of points, each in a separate set, with a smaller distance than that found in the respective subsets ($), then each of the point lies within $ of the dividing line.  Following this logic, we need only search the points within $ of the dividing line for a better result than the separate sets of points.  The running time of the algorithm is O(n log n).