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) ⇐ 2T(n/2) + cn when n > 2 and T(2) ⇐ 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 equal 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 on only T(n) using one of two methods: 1) unrolling the recurrence, or 2) guess-and-check. To unroll a recurrence, 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. When you unroll a recurrence, the root starts at T(n), but then 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. 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 solving 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) ⇐ 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.

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.

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.

Readability: 9 - I like the unrolling process.

Summary & Motivations: Section 5.3 is Counting Inversions.

About the Algorithms:

My Questions:

Second Time Around:

Note to Self:

Readability: