Chapter 6. Divide, Combine, and Conquer
Divide and rule, a sound motto;
Unite and lead, a better one.
|--Johann Wolfgang von Goethe, Gedichte|
This chapter is the first of three dealing with well-known design strategies. The strategy dealt with in this chapter, divide and conquer (or simply D&C), is based on decomposing your problem in a way that improves performance. You divide the problem instance, solve subproblems recursively, combine the results, and thereby conquer the problem—a pattern that is reflected in the chapter title.
Tree-Shaped Problems: All About the Balance
I have mentioned the idea of a subproblem graph before: we view subproblems as nodes and dependencies (or reductions) as edges. The simplest structure such a subproblem graph ...