Analysis Design of Algorithm (ADA) | Divide And Conquer Strategy Introduction

📌Highlights: Hi friends! In this I am going to explain about Divide and Conquer Strategy.

Divide and conquer strategy simply says that if any problem is big and easy to solve than that problem is divided into sub problems , process it and get solution, But if the sub problem is also big and not easy to solve than sub problem is divided sub sub problems if it will not solve than do the same thing again on that sub sub problem until we are not getting solution.

It is a strategy to solve a problem like Dynamic problem , Back tracking , Branch and bound etc. so it is one of the strategy.

Let we understand about strategy. Strategy is a approach or design to solve a problem for solving any computational problem, we will adopt this strategy.

Suppose if we have any problem (P) of size (n). means if we have big size problem than we break this problem into many sub problems such as:

All sub problems are solved individually. Once you have solved these sub problems now you combine all sub problems to get solution.

Now It is noted that if the category of problem is P than category of sub problem must be P. That means category of sub problem is same as main problem.

This is recursive in nature. For solving sub problem we must call same function inside the function.

Here some method is used to combine all sub problems to get solution of original one.

We can also understand by following steps:

START

For Perform Divide and Conquer 

STEP -1

Create Method of Divide and Conquer for any Problem (P).

STEP -2

Check if problem (P) is small  then return Solution

STEP -3

Otherwise Divide problem (P) into many sub problems such as (P1, P2, P3, ...Pn)

STEP -3.1

and Apply Divide and Conquer method on each sub problem until we not getting minimum sub problem which is further not divisible.

STEP-3.2

Then Apply method to combine all sub problems to get complete solution.

END

Some Application Use Divide and Conquer Approach are:

1. Merge Sort.

2. Quick Sort.

3. Binary Search.

4. Strassen's Matrix Multiplication.

Friends ! This is all about the introduction of divide and conquer strategy. I hope by this post you understand what is divide and  conquer strategy. We will meet with new post till continue reading.