DIVIDE-AND-CONQUER

GENERAL METHOD
Given a function to compute on n inputs the divide-and-conquer strategy suggests splitting
the inputs into k distinct subsets, 1 < k <= n, yielding k subproblems. These subproblems
must be solved, and then a method must be found to combine subsolutions into a solution
of the whole. If the subproblems are still relatively large, then the divide-and-conquer
strategy can possibly be reapplied. Often the subproblems resulting from a divide-and
conquer design are of the same type as the original problem. For those cases the
reapplication of the divide-and-conquer principle is naturally expressed by a recursive
algorithm. Now smaller and smaller subproblems of the same kind are generated until
eventually subproblems that are small enough to be solved without splitting are produced.
DAndC (Algorithm) is initially invoked as DAndC(P), where P is the problem to be
solved.
Small(P) is a Boolean-valued function that determines whether the input size is small
enough that the answer can be computed without splitting. If this is so, the function is
invoked (execute). Otherwise the problem P is divided into smaller subproblems. These
subproblems PI, P2 , ... ,Pk are solved by recursive applications of DAndC. Combine is
a function that determines the solution to P using the solutions to the k subproblems. If the
size of P is n and the sizes of the k subproblems are nl, n2, ... ,nk, respectively
.
Algorithm Control abstraction for divide-and-conquer
Type DAndC(P){
if small (P) return S(P);
else{
Divide P into smaller instances P1, P2,…, Pk, k>1;
Apply DAndC to each of these subproblems;
Return Combine ( DAndC(P1), DAndC(P2),…, DAndC(Pk));
}
}
, then