A WHOLE NEW WORLD OF DIVIDE AND CONQUER…

Politically and socially, Divide and Conquer is a strategy to gain and maintain control by dividing the superpowers into smaller parts each with less power than the person using the strategy. In earlier times, Divide and Conquer was used by regions to weaken enemy military alliances. This often happens when propaganda spreads among enemy nations in an effort to raise doubts about the alliance. Once the coalition was weakened or melted away, the gap will allow the state to gain military supremacy.

Explanation of Algorithm

Divide and conquer is an excellent way to solve any programming question and optimise several algorithms. If you are trying to negotiate technology or write productive applications, the best strategy to make the algorithms work well is Divide and Conquer. Many algorithms, such as Binary Search, Merge Sort, and Fast Fourier Transform also use it. Dividing and conquering means that when you face a major problem, you rearrange it into smaller versions of the same problem. When you classify a problem in this way, the difficulty is greatly reduced, leading to O(n log n) instead of O(n) time complexity.

WORKING…

The following 3 steps shows the way in which Divide and Conquer Algorithm works :-

1. DIVIDE- A problem should be broken down into smaller problems.
2. CONQUER- Understand and solving the sub problems separately.
3. COMBINE- Then combine them and get the output.

Example showing sorting an array using Divide and Conquer.

ADVANTAGES…

1. MAKING PROBLEMS EASIER:- Divide and conquer is a powerful way to solve complex psychological problems: all you need is a way to break the problem into smaller problems, solve smaller cases, and then combine small problems to solve real problems
2. EFFICIENCY OF ALGORITHMS:- The strategy of divide and conquer is often used to acquire effective skills. It has been used in Karatsuba’s rapid replication process, quick sort and merge sort algorithms, Strassen matrix multiplication algorithm, and Fourier variable, among other things.
3. PARALLELISM:- Divide and Conquer algorithms are well suited to most processor machines, especially shared memory systems, where data communication between processors does not need to be pre-programmed because minor problems below can be solved on different processors.
4. MEMORY MANAGEMENT:- This algorithm uses memory caches in an efficient manner.
5. ROUNDOFF CONTROL:- This algorithm can produce more accurate results than the same recurring method in multiplication by rounded numbers, such as floating point numbers.

TIME COMPLEXITY…

The complexity of the time algorithm means the time it takes for the system to start from start to finish. Capital ‘O’ notation is widely used to express the time complexity of algorithms. The number of basic tasks performed by the algorithm is widely used to estimate the complexity of time, assuming that each basic task takes a set amount of time to complete. In the case of Divide and Conquer, Master’s theorem is used to calculate the time complexity.

Master’s Theorem

IMPLEMENTATION ISSUES…

1. RECURSION:- Recursive functions are used to implement divide and conquer algorithm. In that case, the procedure call stack automatically stores the partial sub-problems that correspond to the one currently being solved. A recursive function is one that calls itself within the function.
2. EXPLICIT STACK:- Non-recursive programs that store partial sub-problems in an explicit data structure, such as a stack, queue, or priority queue, may also be used to implement divide-and-conquer algorithms. This method provides more flexibility in selecting the underlying problem to be solved, which is required for other applications.
3. STACK SIZE:- When using recursive Divide & Conquer algorithms, make sure there is enough memory allocated to the return stack; otherwise, processing may fail due to stack overflow.
4. CHOOSING THE BASE CASES:- In any recursive algorithm, the option of the base cases, or tiny subproblems that are solved directly to end the recursion, has a lot of latitude.
5. REPEATED SUBPROBLEMS:- Branch recurrence can end up examining the same problem over and over again in other problems. It would be good to find and keep solutions to these conflicting problems in such cases.

DIVIDE AND CONQUER VS DYNAMIC APPROACH…

The process of dividing and conquering divides the problem into smaller, more complex problems. The outcome of each problem is not stored for future reference, while the results of each problem are stored for future use in a more efficient way. If the same small problem can be solved several times, use a strategy to divide and conquer. If the result of the problem below is not used several times in the future, use dynamic approach.

The below example of finding the fibonacci series will help you understand this in a much better way and for that you need to know what is a fibonacci series. So it is a sequence of numbers, starting from 0 and 1, which is then created by adding the previous two numbers.

Divide and Conquer Approach

Dynamic Approach (result of each problem is saved in ‘mem’)

WHEN SHOULD YOU USE DIVIDE AND CONQUER…

It will be useful if we have a problem similar to the well-known divide and conquer algorithm (such as merge sort).Most of the time, we will build algorithms that are very close to compiling the form. We will be able to use divide and conquer if we have an algorithm that takes a list and does something with each item in the list. If we have a sluggish algorithm and want to expand it, one of our first decisions is to divide and conquer. If we have a frustrated algorithm and want to boost it, one of our first decisions would be to use divide and conquer.

TO CUT A LONG STORY SHORT…

Once you have identified that this is the problem where you can use divide and conquer, then it becomes an easy job. The real work is performed in three stages: partitioning problems into subproblems, solving subproblems outright at the very end of the recursion, and gluing together partial answers. The algorithm’s central recursive structure binds them all together and coordinates them and thus speeds up the algorithm. Now that you know all this, you won’t have any problem in solving problems related to divide and conquer algorithm.

I hope that you have gained some knowledge from this blog.

THANK YOU FOR YOUR TIME !!!