Explain Divide and Conquer technique with a general algorithm

Explain the divide and conquer technique with a general algorithm


Divide and Conquer is one of the best-known general algorithm design technique. It works
according to the following general plan:

  • 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’ sub problems.
  • These sub problems must be solved, and then a method must be found to combine sub solutions into a solution of the whole.
  • If the sub problems are still relatively large, then the divide-and-conquer strategy can possibly be reapplied.
  • Often the sub problems 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

A typical case with k=2 is diagrammatically shown below.

Control Abstraction for divide and conquer:

In the above specification,

  • Initially DAndC(P) is invoked, 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 so, the function ‘S’ is invoked. Otherwise, the problem P is divided into smaller subproblems. These sub-problems P1, P2 …Pk are solved by recursive application of DAndC.
  • Combine is a function that determines the solution to P using the solutions to the ‘k’ sub-problems.

Leave a Reply

Your email address will not be published. Required fields are marked *