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.

…

…

…