BIFURCATE AND RULE

Hii people!! In today’s world of software, it is very important to code. To make coding easy we should think and write different algorithms for different problems. In this blog, I’m going to write about an algorithm, i.e DIVIDE AND CONQUER algorithm. for that, you should first need to know what is meant by an algorithm. It’s not like that we are using algorithm only in computer science, we are using in our daily life also…For we will be following some certain steps in making tea that steps are roughly known as an algorithm. An algorithm can be formally defined as it is finite steps of instructions to solve a computational problem.

Divide and conquer is an algorithm technique that is mainly used in sorting methods. For some questions, we cannot solve them by a greedy algorithm, but we can solve that question by the divide and conquer algorithm.

We can define divide and conquer as it is an important algorithm design technique that is based on “recursion”. We can also implement a non-recursive program but that stores the sub-problems in data structures like a queue, stack, etc… This approach allows freedom of choosing the subproblem that is to be solved next. It works by recursively breaking down a problem into two or more subproblems of the same type until they become simple enough to be solved directly. The solution of the sub-problems is then combined to give the solution to the original problem.

Now we’ll be knowing about the strategies and techniques in this divide and conquer algorithm. There are three things: 1) Divide 2) Recursion 3) Conquer i.e you should think of a divide and conquer algorithm as having these three parts. Firstly Divide is nothing but breaking down a given problem into some sub-problems in which the subproblems are the same as the bigger one. After this recursion it is nothing but just recursively we will solve the subproblems. At last conquer, it is something that appropriately combines all the answers of the subproblems to get the final solution…

Now we’ll be raising a question in our mind that does this algorithm always work???

The answer for this will be, No it doesn’t….. Because as per the definition, the recursion basically solves the subproblems which are of the same type. But for all problems, it is not possible to find the subproblems that are of the same type.

Now we’ll understand the working of this algorithm with the above example…Firstly in a function named DNC we’ll be passing a problem P, first we will check whether the given p is small or not, if it is small then the solution is obvious i.e we’ll just return the solution else we’ll divide the problem p into some k subproblems (p1,p2….pk)…At last we’ll just call this function.

Next, we will be knowing the pros and cons of the divide and conquer algorithm… Firstly the advantages are:

1. This algorithm is very easy to code. i.e we can easily write the code for the given question without any confusion.
2. This is very easy to understand.
3. It helps in solving very different problems... Ex: Tower of Hanoi, we already know the problem of the tower of Hanoi the difficulty level is very high, This tower of Hanoi is a problem mostly used to teach recursion and also it has some real-world uses. By the divide and conquer method we can solve the problem efficiently...
4. This process enables ‘parallelism’ that means this allows us to solve independently, this allows for executing parallelly i.e we will be solving all the subproblems with no extra time.
5. It reduces the time complexity and space complexity. As we all know that time complexity plays an important role in today’s coding world so, it is very important to take an eye on time complexity and space complexity.

The disadvantages are :

1. The approach of this method is slow, I.e that recursion is slow in the approach because of repeated subproblem calls…
2. The complexity in this method, i.e sometimes the recursion solution is actually becoming very complex….For example: if the question is to find the sum of n numbers.. for this we can just solve by using for or while loop, but if we follow this algorithm the process really becomes very very complex rather the original thing is a cup of cake.
3. This algorithm i.e divide and conquer is slower than the greedy algorithm but this gives the optimal solution.

We will now know some applications of the divide and conquer algorithm… This algorithm is used in many places mainly in binary search, merge sort, quick sort, matrix multiplication, karatsuba algorithm for fast multiplication, while finding closest pair of points, etc…. Now briefly discuss the usage in some applications:

Binary search

Q) The question is to find an element in a sorted array….

The first thing we should do is to find the mid element in that sorted array. The next step is that we should compare the mid element with the element that should be found then we can just search in either the left part of the middle element or the right part of the middle element accordingly…I think we clearly noticed how to divide and to conquer helped us in finding the element.

Merge sort

Now we’ll see how the divide and conquer method is used in merge sort. The question is we should sort an array in ascending order!!!

The first thing is we should divide the given array into 2 equal size subsequences of n/2 element each, sort the subsequences recursively, next compare the values of both the parts and merge the two sorted subsequences to provide a single sorted array...

Here comes the end of the blog I hope now you will be having a piece of very good knowledge about the divide and conquer algorithm. also hoping that this blog will be useful material in exploring the knowledge.

Enjoy Algorithms! Happy coding !! Code code code !!!