DIVIDE AND CONQUER

Divide the problem into a number of sub-problems that are smaller instances of the same problem. This step follows a recursive approach to break the problem into modules.

Conquer the sub-problems by solving them recursively. If the sub-problem sizes are small enough, however, just solve the sub-problems in a straightforward manner.

Combine the solutions to the sub-problems into the solution for the original problem. Here the merging process performed recursively till the solution for the actual problem formulated.

Examples: Following are some problems that can be solved by divide and Conquer approach.

1. Binary Search
2. Heap Constructions
3. Tower of Hanoi
4. Exponentiations
5. Quick Sort, Merge Sort
6. Matrix Multiplications
7. Closest Pairs etc.