Divide and Conquer approach of Data Structures

DATA STRUCTURES DIVIDE AND CONQUER DATA STRUCTURE & ALGORITHMS

Explain the Divide and Conquer approach of Data Structures?

As the name implies, in divide and conquer approach, the problem is divided into sub-problems and each sub-problem is independently solved. The problems can be divided into sub-problems and sub-problems to even smaller sub-problems, but to a stage where division is not possible. Now the smallest possible sub-problems of the sub-problems are solved. Finally, the solution of all the sub-problems is merged to obtain solution of original problem.

What are the different steps of a divide-and-conquer approach?

The concept of divide-and-conquer approach is explained in a three-step process.

Divide/Break

In this step, the problem is broken into smaller sub-problems such that each sub-part should represent a part of the original problem. Recursive approach is used in this step to divide the problem till further sub-division of the problem is not possible. In this approach, the problems turn to be atomic in nature but even then represent some part of the original problem.

Conquer/Solve

In this step, the sub-problems are solved. At this level, usually the problems are considered 'solved' on their own.

Merge/Combine

After the sub-problems being solved, this stage enables in combining the solution to formulate a solution for the original problem. This algorithmic approach works recursively and conquers & merge steps works so close that they appear as one.

What are the different computer algorithms that are based on divide-and-conquer programming approach?

The computer algorithms which are based on divide-and-conquer programming approach are:

• Merge Sort
• Quick Sort
• Binary Search
• Strassen's Matrix Multiplication
• Closest pair (points)

There are many other ways to solve the computer problem, the above mentioned serve to be good examples of divide and conquer approach.