Python Algorithms: Mastering Basic Algorithms in the Python Language

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