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 20:31] – [5.2 Further Recurrence Relations] 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 49: | 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 110: | 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 164: | 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. | ||
