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.[69]

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 ...

Get Python Algorithms: Mastering Basic Algorithms in the Python Language now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.