Chapter 5: Divide and Conquer

• Summary:

Divide and conquer - break the input into several parts, solve the problem in each part recursively, combine the solutions to the subproblems into an overall solution. Recurrence relations are necessary to discuss the running time of these algorithms. These algorithms might not improve running time as much as in the previous section (because they're reducing the degree of a polynomial running time instead of solving a naturally exponential problem in polynomial time like before), but they're still really important. Mergesort sorts a list by dividing it into two equal halves, sorting each half separately by recursion, and then merging the two sorted halves. Pattern: “divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.” You need a base case for these problems - in this case when the list is 2 elements long, we sort it the “normal” way. The recurrence relation is: T(n) ⇐ 2T(n/2)+cn for n>2 and T(2) ⇐ c. There are two ways to figure out running time from this: unrolling the recurrence or substitution. We went through both of these in class, the notes are good, and it's on p.212. We didn't discuss partial substitution in class, but it's also useful. Substitution methods can help you work out the exact constants when you've got a guess about the general form of the solution.

• Insights and Questions:

I am curious about this concept of “exact constants” in running times. I don't know why I didn't think about it earlier. Is it just the number of steps or is it based on the complexity of each step? I know that sometimes a really big constant can make a “better” algorithm (i.e. better O-notationally) not run as fast, but I am not really sure still how they get this constant or what it means.

• Readability:

I found this section very readable, like the others. No exciting comments on that front.

• Summary:

More generally, there are problems where you can split the input of size n into q subproblems of size n/2 and recombine solutions in constant time. This gives the recurrence relation T(n) ⇐ qT(n/2)+cn for n>2 and T(2)⇐c. They go into how to figure out running times by unrolling the recursion and substitution and partial substitution. We did the first two in class so see those notes. You end up with an O(n^(logbase2q)) running time. Then they go into the case of one subproblem. I guess I'll have to trust them that this is useful (it won't come up until Ch 13), but it seems strange to me that this would ever happen. This problem's bounded by O(n), which is interesting because that means that half of the work for the entire problem is done at the top “level.” A final recurrence relation: T(n)⇐2T(n/2)+O(n^2). Based on this: “divide the input into two pieces of equal size; solve the two subproblems separately by recursion; and then combine the two results into an overall solution, spending quadratic time for the initial division and final recombining.” They unroll the recurrence and show that it's bounded by O(n^2) instead of O(logn*n^2) like you might expect. That's because the work decreases a lot at every level and it turns out to be a converging geometric sum.

• Insights and Questions:

Just the one already sort of mentioned. I can't imagine a problem that could be solved with q=1.

• Readability:

I think these sections would have been easier to read with more motivation for these recurrence relations, but it was generally pretty readable.

• Summary:

• Insights and Questions:

• Readability:

• Summary:

• Insights and Questions:

• Readability: