UNIT: II - Divide and Conquer

 

v   Divide and Conquer:

^Ø  In divide and conquer approach, the problem is divided into smaller sub-problems and then each problem is solved independently. When we keep on dividing the sub-problems into even smaller sub-problems, we may eventually reach a stage where no more division is possible.

^Ø  Those "atomic" smallest possible sub-problems (fractions) are solved. The solution of all sub-problems is finally merged in order to obtain the solution of an original problem.

^Ø   Broadly, we can understand divide-and-conquer approach in a three-step process.

Divide/Break

^Ø  This step involves breaking the problem into smaller sub-problems. Sub-problems should represent a part of the original problem. This step generally takes a recursive approach to divide the problem until no sub-problem is further divisible. At this stage, sub-problems become atomic in nature but still represent some part of the actual problem.

Conquer/Solve

^Ø  This step receives a lot of smaller sub-problems to be solved. Generally, at this level, the problems are considered 'solved' on their own.

Merge/Combine

^Ø  When the smaller sub-problems are solved, this stage recursively combines them until they formulate a solution of the original problem. This algorithmic approach works recursively and conquers & merge steps works so close that they appear as one.

For complete notes : Click Here