Explain the divide and conquer technique with a general algorithm
Answer:-
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.