Chapter 5 - Divide and Conquer

Summary: Section 5.1 is A First Recurrence: The Mergesort Algorithm. Mergesort sorts a list of numbers by splitting the list in half and sorting each half recursively. It combines the two halves back together using an O(n) process. Because this problem has a runtime of T(n) in the worst case and spends O(n) time splitting and recombining the input, we can define a recurrence relation as: T(n) \leq 2T(n/2) + cn when n > 2 and T(2) \leq c. Most recurrence relations will looks like this: “an inequality or equation that bounds T(n) in terms of an expression involving T(k) for smaller values of k; and there is a base case that generally says that T(n) is equal to a constant when n is a constant” (p 211). We assume input sizes are even to simplify the notation; it ends up not mattering in practice, and it simplifies notation/proofs. We can solve a recurrence relation for an asymptotic runtime of only T(n) using one of two methods: 1) unrolling the recurrence, or 2) guess-and-check. When you unroll a recurrence, you start with a root note of T(n), but then it is replaced by the combination cost (here, cn) with children representing the worst case runtime of the subproblem(s) (here, two children, each T(n/2). You continue forming a tree until you reach the base case at the leaves. To unroll a recurrence and find the total runtime, you determine the runtime for the first few levels, find a pattern, and sum the runtimes over all levels until the recurrence bottoms out at the base case/leaves. For Mergesort, we find that each level contributes at most cn to the total running time and there can be at most log n levels, so the runtime of Mergesort is O(n log n). The other method, guess-and-check, uses induction.

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 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.

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 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: 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.

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.

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.

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.

Note to Self: We saw yet another example of reusing an algorithm: merging two sorted lists.

Readability: 6 - the Sort-and-Count algorithm is still confusing.