Skip to main content

Divide And Conquer Method


Define Divide and Conquer method

A Divide and Conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type,until these become simple enough to solve directly..! The solutions to the sub-problems are then combined to give a solution to the original problem.


Define Control Abstraction for D & C method

The meaning of Abstraction is preserving information that is relevant in a given context and forgetting information that is irrelevant in that context. Two types of Abstraction:

  • Control Abstraction
  • Data Abstraction

Control Abstraction: The ability to procedural data where the program procedural data is irrelevant.

Data Abstraction: Data Abstraction is the reduction of a particular body of data to a simplified representation of the whole.


Here we are discussing about Control Abstraction for Divide & Conquer method.Divide and Conquer approach is a three step approach to design a algorithm for a given problem. The three steps are:

  1. Divide
  2. Conquer
  3. Combine

In first step divide and conquer approach make algorithm to divide the big problem into small sub-problems.It may repeatedly do this division till finding the smallest sub-problem which can be solved(conquer) easily.
After finding the smallest sub-problem.... in the Second step it make algorithm to solve(Conquer) the sub-problem recursively and return solution recursively.
In the last step,,,it makes algorithm to combine the solution of sub-problems or solved sub-problems in the same manner it divided to get the soltuion to the given big problem.

Quote:

Let your smile change the world but don't let the world to change your smile....