Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 15:34] – [5.2 Further Recurrence Relations] nasona | courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 22:21] (current) – [5.3 Counting Inversions] nasona | ||
|---|---|---|---|
| Line 1: | Line 1: | ||
| =======5.1 The Mergesort Algorithm======= | =======5.1 The Mergesort Algorithm======= | ||
| + | |||
| + | ==Summary== | ||
| + | Mergesort sorts a list by dividing it into two equal parts, sorting each half by recursion, then combining resulting sorted components. The recurrence relation for mergesort is T(n) <= 2T(n/2) + cn when n>2 and T(2) <= c. There are two ways to solve the recurrence relation: unrolling the recursion and substituting a solution. Unrolling the recurrence includes analyzing the first few levels, identifying a level pattern, and sum over all levels of recursive calls. Substituting requires you to is where you guess the solution, substitute it in, and prove that it works. The total runtime of mergesort is O(nlogn). | ||
| + | |||
| ==Mergesort== | ==Mergesort== | ||
| Line 40: | Line 44: | ||
| * Method can actually be useful in working out the exact constant when one has some guesses of the general form of the solution | * Method can actually be useful in working out the exact constant when one has some guesses of the general form of the solution | ||
| + | ==Additional Information== | ||
| + | At first, the concept of unrolling a recurrence was difficult for me to grasp. However, now, it is easy to see that you just see the number of problems on each level, the size of each problem, and the time cost of each problem on the level. Once you add them all up and are able to generalize a level rule, then you just have to think about how many times the recursion can occur, then you're done! You have a runtime. | ||
| + | |||
| + | On a scale of 1 to 10, the readability of this section is an 8. The only reason this is not a 10 is that at first, unrolling was a difficult concept for me to grasp. However, now, after seeing unrolling in class a few times and reading all of the sections for this reading, unrolling makes a lot of sense now. It was a really great idea for the authors to unroll an algorithm that we already knew the runtime of and knew how it worked. | ||
| =======5.2 Further Recurrence Relations======= | =======5.2 Further Recurrence Relations======= | ||
| + | |||
| + | ==Summary== | ||
| + | Now, we need to consider divide and conquer algorithms that create recursive calls on q subproblems of size n/2 and comibine the results in linear time. We already handled when q=2 with mergesort. When q > 2, the recurrence relation is T(n) <= qT(n/2) + cn when n > 2 and T(2) <=c. By unrolling the recursion, we come to the conclusion that the runtime of the algorithm is O(n^(log2q)). When q = 1, by unrolling the recurrence, we get that T(n) <= 2cn = O(n). A related recurrence of T(n) < | ||
| ==The Case of q>2 Subproblems== | ==The Case of q>2 Subproblems== | ||
| Line 92: | Line 103: | ||
| * Log2n levels of recursion | * Log2n levels of recursion | ||
| * Get a geometric sum whose solution is T(n) <= 2cn^2 = O(n^2) | * Get a geometric sum whose solution is T(n) <= 2cn^2 = O(n^2) | ||
| + | ==Question== | ||
| + | * Under what conditions would this recurrence T(n) <= 2T(n/2) + O(n^2) happen? Do you have an example algorithm that has this recurrence equation? | ||
| + | ==Additional Information== | ||
| + | At first, I was confused on why the general q>2 subproblems still had log2n recurrences, | ||
| + | |||
| + | On a scale of 1 to 10, the readability of this section was a 9. The progression of the general solution of what was discussed in the previous chapter to the special cases of q = 1 was a really great structuring on the authors' | ||
| =======5.3 Counting Inversions======= | =======5.3 Counting Inversions======= | ||
| + | |||
| + | ==Summary== | ||
| + | We want to be able to tell how far away a list is from being in order. In order to do this, we just have to count the number of inversions. The brute force solution to the algorithm runs in O(n^2) time, but we can do better than that. We will divide the list in half, count the number of inversions in each piece, and make the algorithm recursively sort the two halves. Once we get the two sorted halves, we want to combine them into a single sorted list while counting the number of inversions as we go. The Merge-and-Count routine takes O(n) time and the Sort-and-Count algorithm takes a total O(nlogn) time. | ||
| + | |||
| + | ==The Problem== | ||
| + | * Core issue is the problem of comparing two rankings | ||
| + | * Want to define a measure that tells us how far this list is from being in ascending order | ||
| + | * Natural way to qualify this notion is by counting the number of inversion | ||
| + | * When sequence is in ascending order, there are no inversions | ||
| + | * When sequence is in descending order, every pair forms an inversion, so there are C(n, 2) inversions (“n choose 2”) | ||
| + | |||
| + | ==Designing the Algorithm== | ||
| + | * Brute force: we could look at every pair of numbers (ai, aj) and determine whether they constitute an inversion, O(n^2) runtime | ||
| + | * Our goal is to count the inversions in O(nlogn) time | ||
| + | * Divide the list into two pieces, count the number of inversions (ai, aj) where the two numbers belong to different halves in O(n) time, make the algorithm recursively sort the numbers in the two halves | ||
| + | * Crucial routine: Merge-and-Count | ||
| + | * After recursively sorting the two halves of the list and counter the inversions in each, now have two sorted lists A and B. We want to produce a single sorted list C from their union, while counting the number of pairs (a, b) with a in set A, b in set B, and a>b. | ||
| + | * Walk through the sorted lists A and B, removing elements from the front and appending them to sorted list C | ||
| + | * In a given step, we have a Current pointer into each list showing our current position. Compare the elements ai and bj being pointed to in each list, remove the smaller one form its list and append it to the end of C. | ||
| + | * Every time the element ai is appended to C no inversions are encountered, | ||
| + | * If bj is appended to list C, then it is smaller than all the remaining items in A and it comes after all of them, so we increase our count of the number of inversions by the number of elements remaining in A. | ||
| + | |||
| + | ==Merge-and-Count== | ||
| + | | ||
| + | Maintain a current pointer into each list, initialize to point to the front elements | ||
| + | Maintain a variable Count for the number of inversion, initialized to 0 | ||
| + | While both lists are nonempty: | ||
| + | Let ai and bj be the elements pointed to by the Current pointer | ||
| + | | ||
| + | If bj is the smaller element: | ||
| + | Increment Count by the number of elements remaining in A | ||
| + | Endif | ||
| + | | ||
| + | Endwhile | ||
| + | Once one list is empty, append the remainder of the other list to the output | ||
| + | Return Count and the merged list | ||
| + | |||
| + | * Each iteration of the while loop takes constant time and number of iterations can be done at most the sum of the initial lengths of A and B, so the total runtime is O(n) | ||
| + | |||
| + | ==Sort-and-Count== | ||
| + | | ||
| + | If the list has one element: | ||
| + | There are no inversions | ||
| + | Else: | ||
| + | | ||
| + | A contains the first half of the elements (ceiling of n/2) | ||
| + | B contains the remaining elements (floor of n/2) | ||
| + | (rA, A) = Sort-and-Count(A) | ||
| + | (rB, B) = Sort-and-Count(B) | ||
| + | (r, L) = Merge-and-Count(A, | ||
| + | Endif | ||
| + | Return r = rA + rB + r, and the sorted list L | ||
| + | |||
| + | * Merge-and-Count procedure takes O(n) time, the running time T(n) of the full Sort-and-Count procedure satisfies the recurrence | ||
| + | * The Sort-and-Count Algorithm correctly sorts the input list and counts the number of inversions: it runs in O(nlogn) time for a list with n elements. | ||
| + | |||
| + | ==Additional Information== | ||
| + | At first, I was confused on exactly how we were counting the inversions by sorting. Later, it became clear. In the Merge-and-Count list merges the two sorted lists together and if an element in the second list (which was later in the ordering) comes before elements in the first list, you increment the inversion count by the number of elements left in the first list. Inversions are also counted when the two separate lists in divide and conquer are sorted. | ||
| + | |||
| + | On a scale of 1 to 10, the readability of this section was an 8. We had already learned about inversions before this section in regards to exchange arguments, so the problem was easy to comprehend, and the solution was very clever but once they told us what it was, it was not difficult to comprehend. It kind of built off mergesort, which is what we learned about in the first section. | ||
