Chapter 5 - Divide and Conquer

This section introduces the Divide and Conquer algorithms as a whole by starting with the MergeSort algorithm. The text first covers the logic behind the algorithm. We take an input of size n, split this input into two pieces of equal size, solve the two subproblems separately by recursion, and then combine these two solutions to form an overall solution for the initial problem. And we only spend linear time on the division and recombining process. They also lay out the recurrence relation for Mergesort: T(n) ⇐ 2T(n/2)+cn when n>2 and T(2)⇐c.

The text then goes into the two ways we can solve recurrence relations to see the runtime complexity of an algorithm with a structure such as that of Mergesort. The first strategy is unrolling the recurrence and the second is to guess-and-check and prove your guess by means of induction. I far prefer unrolling the recurrence rather than induction. It makes more intuitive sense to me and the book does a good job reinforcing the material covered in class. The text uses the structure of unrolling and induction to prove that the mergesort algorithm runs in O(n log n) time. The text also briefly mentions a method to prove a recurrence relation using partial substitution, but I did not find this nearly as intuitive as simply using a regular inductive argument.

I would rate the readability at 9/10.

This section dives into a few different recurrence relations that are very similar to the mergesort relation covered in 5.1. The first of these is the general class of algorithms created by letting there be q subproblems (rather than 2) of size n/2 each and then combine those results in O(n) time. The text lets q=3 and dives into the example. They unroll the recurrence and give us some properties about summations such that we can derive the running time of this recurrence relation. It ends up that, with q>2 and subproblems of size n/2, we have that the relation is bounded by O(n^log_2(q)). I understood this argument. But the book also walks through a way of solving this using partial substitution, which again, I found far less intuitive than unrolling the relation as is. I was still able to follow the argument, but I far prefer unrolling the relation.

The text then covers the case of just one subproblem. That is, instead of generating more than one subproblem from T(n), we generate just one and are asked to find the recurrence relation. It turns out that this is fairly simple. We still have log(n) levels, and each subproblem (assuming we are starting at n) has size n/2. So we are creating a very similar sum as we created with q, another geometric series. And it ends up that T(n) ⇐ 2cn = O(n). The book's argument to prove this is clear and succinct.

The text ends the section by covering a related recurrence: T(n) ⇐ 2T(n/2)+O(n^2). This is the same as mergesort, except instead of the linear combine/recombine time, it is quadratic. Intuitively, we would think that this would be bounded by O(n^2log(n)). However, it turns out that n^2 changes the magnitude of the bound. The book walks through this clearly in identifying the pattern on page 221, but the convergent geometric series in this example sums similarly to the case when we have just one subproblem, which ends up yielding a runtime of O(n^2).

I would rate the readability of this section at 8/10. Some parts were difficult to follow(partial substitution). However, others flowed very smoothly.