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:52] – [5.3 Counting Inversions] nasona | courses:cs211:winter2018:journals:nasona:chapter5 [2018/03/11 22:21] (current) – [5.3 Counting Inversions] nasona | ||
|---|---|---|---|
| Line 2: | Line 2: | ||
| ==Summary== | ==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 43: | Line 45: | ||
| ==Additional Information== | ==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. | 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. | ||
| Line 48: | Line 51: | ||
| ==Summary== | ==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 99: | 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== | ==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' | 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' | ||
| Line 106: | Line 113: | ||
| ==Summary== | ==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== | ==The Problem== | ||
| Line 160: | Line 168: | ||
| ==Additional Information== | ==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. | 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. | ||
