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) ⇐ qT(n/2) + cn when n > 2, and T(2) ⇐ c, for some constant c. We explore unrolling, substitution (

My Questions:

Second Time Around:

Note to Self:

Readability:

Summary & Motivations: Section 5.3 is Counting Inversions.

About the Algorithms:

My Questions:

Second Time Around:

Note to Self:

Readability: