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 books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.