Divide and Conquer - Concepts and Applications

In divide-and-conquer, we solve a problem recursively, applying three steps at each level of the recursion:

1. Divide the problem into a number of sub-problems that are smaller instances of the same problem.
2. 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.
3. Combine the solutions to the sub-problems into the solution for the original problem.

                                          Source : http://faculty.simpson.edu/

When the sub-problems are large enough to solve recursively, we call that the recursive case. Once the sub-problems become small enough that we no longer recurse, we say that the recursion “bottoms out” and that we have gotten down to the base case.

Applications of Divide and Conquer:

1. Merge Sort
2. Maximum sub-array problem
3. Matrix multiplication
4. Finding closest pair(points) in 2D-plane
5. Integer multiplication
6. Quick Sort
7. Binary Search

Performance Analysis:

For Divide-and-Conquer algorithms the running time is mainly affected by 3 criteria:

The number of sub-instances (alpha) into which a problem is split.
The ratio of initial problem size to sub-problem size. (beta)
The number of steps required to divide the initial instance and to combine sub-solutions, expressed as a function of the input size, n.
Suppose, P, is a divide-and-conquer algorithm that instantiates alpha sub-instances, each of size n/beta.

Let Tp( n ) denote the number of steps taken by P on instances of size n. Then

Tp( n0 )  =  Constant   (Recursive-base)
Tp( n )   =  alpha Tp( n/beta ) + gamma( n )

In the case when alpha and beta are both constant (as in all the examples we have given) there is a general method that can be used to solve such recurrence relations in order to obtain an asymptotic bound for the running time Tp( n ).

In general:

T( n )  =  alpha T( n/beta ) + O( n^gamma )
(where gamma is constant) has the solution


                  O(n^gamma)             if   alpha < beta^gamma
T( n )  =    O(n^gamma log n)       if   alpha = beta^gamma}
                  O(n^{log^-beta(alpha)) if   alpha > beta^gamma

Advantages:

1. Solving difficult problems:
Divide and conquer is a powerful tool for solving conceptually difficult problems: all it requires is a way of breaking the problem into sub-problems, of solving the trivial cases and of combining sub-problems to the original problem.

2. Parallelism:
Divide and conquer algorithms are naturally adapted for execution in multi-processor machines, especially shared-memory systems where the communication of data between processors does not need to be planned in advance, because distinct sub-problems can be executed on different processors.

3. Memory Access:
Divide-and-conquer algorithms naturally tend to make efficient use of memory caches. The reason is that once a sub-problem is small enough, it and all its sub-problems can, in principle, be solved within the cache, without accessing the slower main memory. 

4. Roundoff control:
In computations with rounded arithmetic, e.g. with floating point numbers, a divide-and-conquer algorithm may yield more accurate results than a superficially equivalent iterative method.


References:
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithms
http://www.amazon.com/Introduction-Algorithms-Edition-Thomas-Cormen/dp/0262033844
http://cgi.csc.liv.ac.uk/~ped/teachadmin/algor/d_and_c.html