divide-and-conquer

$\huge{\color{Cadetblue}\text{Divide-and-Conquer}}$

$\Large{\color{Rosybrown}\text{Overview}}$

${\color{peru}\text{CLRS}}$	${\color{peru}\text{Topic}}$
4.1 [ed3]	Maximum Subarray
4.2	Strassen's Matrix Multiplication
–	Karatsuba's Integer Multiplication
Ex 2.3	Binary Search
Prob 2-4	Inversion Count
9.2-3	Quickselect
33.4 [ed3]	Closest Pair of Points
2.3	Merge Sort
7.1-3	Quicksort

$\Large{\color{Rosybrown}\text{The D-and-C Approach}}$

When a problem is too difficult to solve directly, it is often possible to attack the problem by dividing it into subproblems that are themselves smaller instances of the same problem and then solving these subproblems ${\color{peru}\text{recursively}}$. Such an approach is known as divide and conquer, and it is typically described by a ${\color{peru}\text{recurrence relation}}$, which expresses the solution to a problem in terms of solutions to smaller instances of the same problem.

A divide-and-conquer algorithm consists of three steps at each level of the recursion:

1. ${\color{Mediumorchid}\text{Divide}}$ the problem into a number of subproblems that are smaller instances of the same problem.
2. ${\color{Mediumorchid}\text{Conquer}}$ the subproblems by solving them recursively.
3. ${\color{Mediumorchid}\text{Combine}}$ the solutions to the subproblems into a solution for the original problem.

After sufficiently many levels of recursion, the recursion bottoms out and the subproblems become so small that they can be solved directly. As recursion unwinds, the solutions to the subproblems are then combined to give a solution to the original problem.

Note that if the subproblems are not independent (i.e. solutions to subproblems depend on solutions to other subproblems), the divide-and-conquer approach is not suitable, since the same subproblem would be solved multiple times. In such cases, dynamic programming is the recommended approach.