A Textbook of Data Structures and Algorithms, Volume 3

19Divide and Conquer

In this chapter, the Divide and Conquer strategy is detailed and demonstrated over the problems of finding the max/min element in a list, merge sort and matrix multiplication.

19.1. Introduction

Divide and Conquer is a popular algorithm design strategy that has been widely used over a variety of problem classes. As the name indicates, the strategy solves a problem by dividing it repeatedly into smaller sub-problems, until the smaller sub-problems can be individually and easily solved. The strategy then backtracks, combining the solutions of the smaller sub-problems phase by phase on its return, until the solution to the original problem is automatically constructed, thereby conquering the problem. Needless to say, Divide and Conquer has been a time-tested political strategy too!

The fact that the strategy repeatedly moves onward to “divide” the problem and backtracks to “conquer” its solution, is suggestive of the application of recursion. Thus, Divide and Conquer-based solutions to problems are ideally implemented as recursive procedures or programs (see section 2.7 of Chapter 2, Volume 1, for a discussion on recursion and analysis of recursive procedures).

19.2. Principle and abstraction

Figure 19.1(a) illustrates the principle of Divide and Conquer, where a problem whose data set size is n, is repeatedly divided into smaller sub-problems each of which are solved independently, before the principle backtracks to combine the solutions of the sub-problems, ...