Divide and Conquer Technique

Post date: Nov 5, 2013 6:13:10 AM

< Previous-Polynomial Vs.Exponential Running Time Next - Greedy Technique>

Divide and Conquer approach basically works on breaking the problem into sub problems that are similar to the original problem but smaller in size & simpler to solve. once divided sub problems are solved recursively and then combine solutions of sub problems to create a solution to original problem.

At each level of the recursion the divide and conquer approach follows three steps:

1. Divide: In this step whole problem is divided into several sub problems.
2. Conquer: The sub problems are conquered by solving them recursively, only if they are small enough to be solved, otherwise step1 is executed.
3. Combine: In this final step, the solution obtained by the sub problems are combined to create solution to the original problem.

Divide and conquer approach has several advantages as follows:

1. Solving conceptually difficult problems, it just require to divide them into sub problems. for example: Tower of Hanoi
2. Divide and Conquer approach helps in discovering efficient algorithms like Strassen's Algorithm for matrix multiplication.
3. Divide and Conquer also adapts itself to execute in multiprocessor machines. There fore parallel execution of sub problems on different processors with shared memory helps in parallel execution if master problem, results in increased algorithm performance.

Following are the problems which has become very efficient with use of Divide and Conquer approach:

1. Binary Search.
2. Finding the Maximum and Minimum.
3. Merge Sort.
4. Quick Sort.
5. Selection Sort.
6. Strassen's Matrix multiplication.
7. Convex Hull.

All above mentioned problems will be explained on other pages with concerned topics or you can click on provided link to directly read them.

< Previous-Polynomial Vs.Exponential Running Time Next - Greedy Technique>