Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2014:journals:haley:chapter5 [2014/03/05 06:15] – archermcclellanh | courses:cs211:winter2014:journals:haley:chapter5 [2014/03/12 02:35] (current) – archermcclellanh | ||
|---|---|---|---|
| Line 9: | Line 9: | ||
| * Mergesort is a D&C algorithm. | * Mergesort is a D&C algorithm. | ||
| * We divide the list to be sorted into smaller lists and sort each at the base level, then merges sorted lists. | * We divide the list to be sorted into smaller lists and sort each at the base level, then merges sorted lists. | ||
| + | |||
| + | ===== 5.2: Recurrence Relations Continued ===== | ||
| + | |||
| + | * When there are more than two subproblems | ||
| + | * For the first few levels, we have a problem of size n taking cn plus the recursive call time. | ||
| + | * At the next level, we have q problems of size n/2, taking time cn/2 plus the recursive call times. | ||
| + | * At the next level, we have q^2 problems of size n/4, taking time q^2*cn/4 time. | ||
| + | * Thus we'll always have q^j distinct instances at level j, of size n/(2^j). Thus at level j we have time q^j(cn/ | ||
| + | * After a lot of math, we get the important thing, which is that T(n)≤O(n^(log_2(q)). | ||
| + | * If we apply partial substitution, | ||
| + | * What if there' | ||
| + | * At level j we have one instance of size n/(2^j) and adds cn/(2^j) to the runtime, which converges as a sum to T(n) ≤ 2cn = O(n). | ||
| + | * Finally, for T(n) ≤ 2T(n/2) + O(n^2) | ||
| + | * After some work (p 220, 221), we find that T(n) ≤ O(n^2). | ||
| + | |||
| + | ===== 5.3: Counting Inversions ===== | ||
| + | |||
| + | * 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, | ||
| + | * 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. | ||
| + | |||
