Chapter 5: Divide and Conquer

Large inputs can be computationally costly to work with. Smaller inputs are necessarily less so. We consider dividing large problems into smaller, easier ones and combining our findings later. Although combining results has an associated cost, the hope is that our solution will be more efficient than it was before.

Example problems: Finding the closest pair of points in the plane; multiplying two integers; smoothing a noisy signal.

This section introduces the complex idea of recurrence relations with a simple example. A typical recurrence relation is formulated in a way similar to T(n) ⇐ 2T(n/2) + cn. The term T(n) denotes the “worst-case running time on input instances of size n.” (Note: the evenness/oddness of n is essentially negligible.) Obviously there is some recursion present. For the example recurrence relation above, the asymptotic bound of T's growth rate is n log n. How do we know/how did we figure it out?

We find asymptotic bounds (solve recurrences) by:

• Unrolling the recursion, identifying patterns, and summing the costs at each level
• Estimating the solution, checking if it works, and then proving it by induction

(5.1) For some constant c, T(n) ⇐ 2T(n/2) + cn when n > 2, and T(2) ⇐ c.

(5.2) Any function T(*) satisfying (5.1) is bounded by O(n log n), when n > 1.

This section gives other kinds of recurrence relations. It was interesting how generalizing from (5.1) to (5.3) produced different unrollings and how (5.2) looked a lot different than (5.4). I don't see why I would ever go the guessing route, as opposed to unrolling.

(5.3) For some constant c, T(n) ⇐ qT(n/2) + cn when n > 2, and T(2) ⇐ c.

(5.4) Any function T(*) satisfying (5.3) with q > 2 is bounded by O(n^log2(q)).

I don't get the final problem section 'Identifying a pattern' on page 221. It says “and hence the total work at this level is bounded by … cn^2/2^j.” But in the section 'Analyzing the first few levels' it says that the third level (j=3) runs for a total of at most cn^2/4. Shouldn't it be cn^2/8?

This section is about comparing ranking systems. Websites like Amazon and YouTube do this to direct their customers/viewers to other products/videos they may like. We generalize the problem drastically, as we start by thinking about the similarities/differences between two sets of integers.

Example: Person A has a preference list for n pizza joints, which we write as follows: 1, 2, 3, .., n (the 1st pizza place is his most favorite, and the nth pizza place is his least favorite). Another person has a different preference list. (The 1st pizza place may be his second most favorite, for example.) The goal is to find “a measure that tells us how far this list is from being in ascending order.”

Inversions are the solution. An inversion is an instance in which two elements are “out of order.” The Sort-and-Count algorithm on page 225 is an example of recursive procedure that “simultaneously sorts and counts the number of inversions in a list L.”

(5.7) The Sort-and-Count algorithm correctly sorts the input list and counts the number of inversions; it runs in O(n log n) time for a list with n elements.

We hammered this home in class. To solve the problem, one must first sort all of the points by their x-coordinates. Then one divides the problem into two subproblems of equal size (those with the smallest x-coordinates in one half, the rest in the other). Then the algorithm recursively finds the closest pair of points in each subarea. Having solved those problems, they need to be combined… since it is possible for the closest pair of points to be somewhere in between the subareas. This is all detailed in this section, and I understand it well because we hammered it down in class.

(5.12) The running time of the [Closest-Pair] algorithm is O(n log n).

This problem gives an algorithm that multiplies integers in sub-quadratic time (better than we usually do when we multiply by hand). It computes the product xy by recursively dividing x and y in half and performing operations on those (n/2)-digit segments. It relies on fewer multiplications and more additions (pp. 232-233 explain this well).

This example shows why thinking about recurrence relations can be useful. For example, we knew that dividing the problem into any more than 3 subproblems (with linear time combination &etc) would result in an equivalent or worse running time than the normal algorithm. Therefore we looked for a way to divide the problem into 3 subproblems (while maintaining linear time combination &etc). Sure, it required our being clever, but the understanding of recurrence relations made it easier than it would have been.

I learned a new math term: convolution. Convolutions are a yuge deal in signal processing. This section gives a sub-quadratic algorithm for computing the convolution. The Fast Fourier Transform computes the convolution in O(n log n) time. (5.15).