Differences

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

--- courses:cs211:winter2018:journals:melkersonr:chapter5 [2018/03/13 01:45] – [Section 5.1] melkersonr
+++ courses:cs211:winter2018:journals:melkersonr:chapter5 [2018/03/13 01:52] (current) – [Section 5.3] melkersonr
@@ Line 7: / Line 7: @@
    * **My Questions:** How on earth would someone be able to guess a runtime? Unrolling the recurrence seems so much easier.
    * **Second Time Around:** This section is another example where I liked explanations from class better than from the book. I liked how in class we broke the process down even more than the book when unrolling the recurrence. We started with T(n) as the root, erased it, replaced it with cn, and added two child nodes of T(n/2). And so on.
-   * **Note to Self:** There are two ways to solving a recurrence relation, but the guess-and-check method seems harder for now, while I'm less familiar with Divide and Conquer runtimes.
+   * **Note to Self:** There are two ways to solve a recurrence relation, but the guess-and-check method seems harder for now, while I'm less familiar with Divide and Conquer runtimes.
    * **Readability:** 9 - pretty straightforward and short.
 ===== Section 5.2 =====
-   * **Summary:** Section 5.2 is Further Recurrence Relations. In this section, we generalize the recurrence relation from Mergesort to ones that "create recursive calls on 1 subproblems of size n/2 each and then combine the results in O(n) time" (p 215). For Mergesort, q = 2. The recurrence relation is T(n) <= q*T(n/2) + cn when n > 2, and T(2) <= c, for some constant c. We explore both q > 2 and q = 1, since they're "qualitatively different from each other" (p 215). When we unroll for q > 2, we find that the total work per level actually increases, unlike for Mergesort. Specifically, the total work for level j is q^j(cn / 2^j) = (q/2)^j(cn). We use a geometric sum to determine the total work, which is O(n^{log q}) after some algebra. The partial substitution method for q > 2 can be found on page 217; I skip it here because I prefer the unrolling method. When we unroll for q = 1, we find that the total work per level actually decreases, unlike both Mergesort and the q > 2 case. Specifically, the total work for level j is (cn / 2^j). We again use a geometric sum to determine the total work, which is O(n). To close out the section, we explore another, related recurrence: T(n) <= 2*T(n/2) + cn^2 when n > 2, and T(2) <= c, for some constant c. This recurrence is similar to Mergesort, but it spends quadratic time on the initial "divide" and the final recombination. Here also, the total work per level decreases. Specifically, the total work for level j is (2^j)*c*(n / 2^j)^2 = c*n^2/2^j. Yet another geometric sum reveals that the total runtime is O(n^2). We note that the intuitive guess of O(n^2 log n) is technically correct, but that unrolling the recurrence gives a tighter bound.
+   * **Summary:** Section 5.2 is Further Recurrence Relations. In this section, we generalize the recurrence relation from Mergesort to ones that "create recursive calls on 1 subproblems of size n/2 each and then combine the results in O(n) time" (p 215). For Mergesort, q = 2. The recurrence relation is T(n) \leq q*T(n/2) + cn when n > 2, and T(2) \leq c, for some constant c. We explore both q > 2 and q = 1, since they're "qualitatively different from each other" (p 215). When we unroll for q > 2, we find that the total work per level actually increases, unlike for Mergesort. Specifically, the total work for level j is q^j(cn / 2^j) = (q/2)^j(cn). We use a geometric sum to determine the total work, which is, after some algebra, O(n^{log q}). The partial substitution method for q > 2 can be found on page 217; I skip it here because I prefer the unrolling method. When we unroll for q = 1, we find that the total work per level actually decreases, unlike both Mergesort and the q > 2 case. Specifically, the total work for level j is (cn / 2^j). We again use a geometric sum to determine the total work, which is O(n). To close out the section, we explore another, related recurrence: T(n) \leq 2*T(n/2) + cn^2 when n > 2, and T(2) \leq c, for some constant c. This recurrence is similar to Mergesort, but it spends quadratic time on the initial "divide" and the final recombination. Here also, the total work per level decreases. Specifically, the total work for level j is (2^j)*c*(n / 2^j)^2 = c*n^2/2^j. Yet another geometric sum reveals that the total runtime is O(n^2). We note that the intuitive guess of O(n^2 log n) is technically correct, but that unrolling the recurrence gives a tighter bound.
    * **My Questions:** I still wonder why you'd choose the substitution method for determining the total runtime. It seems so much less intuitive.
-   * **Second Time Around:** I know we touched on the geometric sums in lecture, but it was nice to seem them worked out with notation where it should be (as opposed to single-line representation). I think it helped with the understanding.
+   * **Second Time Around:** I know we touched on the geometric sums in lecture, but it was nice to see them worked out with notation where it should be (as opposed to single-line representation). I think it helped with the understanding.
-   * **Note to Self:** Cannot simply guess the runtime for a new recurrence relation even if it looks similar to one we already know, as in the case of T(n) <= 2*T(n/2) + cn vs T(n) <= 2*T(n/2) + cn^2.
+   * **Note to Self:** You cannot simply guess the runtime for a new recurrence relation even if it looks similar to one we already know, as in the case of T(n) \leq 2*T(n/2) + cn vs T(n) \leq 2*T(n/2) + cn^2.
    * **Readability:** 9 - I like the unrolling process.
 ===== Section 5.3 =====
-   * **Summary & Motivations:** Section 5.3 is Counting Inversions.
+   * **Summary & Motivations:** Section 5.3 is Counting Inversions. Enter the problem of comparing rankings. This problem arises in collaborative filtering, where an algorithm tries to match your preferences to someone else's preferences and make a recommendation, and in //meta-search tools//, where a query is run on multiple search engines and the results are synthesized (p 221-2). In the context of collaborative filtering, we can ask how many rankings of yours are out of order with with respect to another person's rankings. More concisely, we want to find a measure for how out of order a sequence of distinct numbers is. The metric will equal 0 only if a_1 < a_2 < ... < a_n for all n numbers. We can quantify the out-of-order-ness by counting the number of inversions in the ranking/list, where an inversion exists between indices i < j if a_i > a_j.
-Enter the problem of comparing rankings. This problem arises in collaborative filtering, where an algorithm tries to match your preferences to someone else's preferences and make a recommendation, and in meta-search tools, where a query is run on multiple search engines and the results are synthesized (p 221-2). In the context of collaborative filtering, we can ask how many rankings of yours are out of order with with respect to another person's rankings. More concisely, we want to find a measure of how out of order a sequence of distinct numbers is. The metric will equal 0 only if a1 < a2 < ... < an for all n numbers. We can quantify the out-of-order-ness by counting the number of inversions in the ranking/list, where an inversion exists between indices i < j if a_i > a_j.
+   * **About the Algorithms:** The brute-force approach to this problem, determining if each and every pair is inverted, is O(n^2). We suspect we can do better, though. The algorithm uses the recursion relation T(n) \leq 2T(n/2) + cn when n > 2 and T(2) \leq c (same as for Mergesort) by dividing the list into two, counting the number of inversions in each half, and counting the number of inversions between halves. We make the recursive step also sort the two halves so that the combination step is "easier" (p 223). We employ a Merge-and-Count algorithm, which assumes that we've already counted the inversions in each half of the list and sorted them. This is nearly merging two sorted lists into one, except that we're also counting inversions. That's easy enough. Merge-and-Count iterates through the two halves with pointers, appending the front element to the full sorted list of whichever half has a smaller front element. Each time we append to the full list, we ask if the smaller element comes from list B, and if so, we increase the inversion counter by the number of elements remaining in list A. If one of the lists becomes empty, we add the rest of the other list to the full list. We effectively count the number of inversions in constant time, which we can do because both lists are sorted. If the smaller element comes from list B, it is smaller than //everything// remaining in list A. We also know that we can simply append the remaining list when the other becomes empty because it is also already sorted and the last item added to the full list was smaller than its front item. The full algorithm is called Sort-and-Count, and it has an O(n log n) runtime.
-   * **About the Algorithms:** The brute-force approach to this problem, determining if each and every pair is inverted, is O(n^2). We suspect we can do better, though. The algorithm uses the recursion relation of Mergesort by dividing the list into two, counting the number of inversions in each half, and counting the number of inversions between halves. We make the recursive step also sort the two halves so that the combination step is "easier" (p 223). We employ a Merge-and-Count algorithm, which assumes that we've already counted the inversions in each half of the list and sorted them. This is nearly merging two sorted lists into one, except that we're also counting inversions. That's easy enough. Merge-and-Count iterates through the two halves with pointers, appending the front element to the full sorted list of whichever half has a smaller front element. Each time we append to the full list, we ask if the smaller element comes from list B, and if so, we increase the inversion counter by the number of elements remaining in list A. If one of the lists becomes empty, we add the rest of the other list to the full list. We effectively count the number of inversions in constant time, which we can do because both lists are sorted. If the smaller element comes from list B, it is smaller than //everything// remaining in list A. We also know that we can simply append the remaining list when the other becomes empty because it is also already sorted and the list item added to the full list was smaller than its front item. The full algorithm is called Sort-and-Count, and it has a O(n log n) runtime.
    * **My Questions:** I'm still a little confused about the Sort-and-Count algorithm, especially the "(r_A, A) = Sort-and-Count(A)" etc. notation. I suppose it's pattern matching. It's just hard to think about recursive algorithms without running through an example.
    * **Second Time Around:** I really liked Figure 5.4 for visualizing inversions with crossed lines.