[0:00]Hello friends, I'm going to start a next topic in algorithms, that is divide and conquer strategy. The first topic was analysis of algorithm, in that topic I have shown you how to write an algorithm and how to analyze an algorithm. And what is the purpose of analysis? Now, the next topic is divide and conquer. This topic is related to a strategy for solving a problem. Like this we have other strategies also in the subject like greedy method, dynamic programming, backtracking, branch and bound. So, this is one of the strategy. So, let us understand what is a strategy. Strategy is an approach or a design for solving a problem. For solving any problem, computational problem, you can adopt this strategy for solving the problem, if the strategy is suitable for the problem. So, by practice you can come to know there is no formula that this is the problem, this strategy is applicable. Though there are few guidelines. So, we can follow those guidelines and we can apply the strategy for solving a problem. If a problem of some size is given, let us say size is N. This size is size of the input for a problem. So, if a problem P is there of some size and if we say that this problem is large, then you can break this problem into smaller subproblems, P1, P2, P3, goes on, as many problems as possible, that depends on you. So, let us say K subproblems. Now, the large problem is broken down into smaller subproblems. So, the size was larger, so we have broken to smaller size problems. Now, these problems, subproblems can be solved to obtain their solutions. So, for this solution one, solution two and solution three and so on, for this solution K. All these are individually solved. Now, once you have the solutions for these, you can combine these solutions to get a solution for main problem.
[2:35]So, if a problem is large, divide the problem into subproblems, and solve those subproblems, and combine the solutions of subproblems to get the solution for main problem. So, it means if a problem cannot be solved, if it is too big, break it into subproblems and solve it. If a subproblem is also large, then do the same thing, apply divide and conquer strategy on subproblems also. If it is large again do the same thing, break it into sub-subproblems and find the solutions, combine the solution. The one important thing about divide and conquer. Whatever the problem is, the subproblems will be same as that problem. For example, if problem is to sort, then the subproblems should also be sort. Each and every subproblem should be sort only. It cannot convert into some other problem. Like example, if problem is, I'll take some real example. If a problem is to conduct a workshop at a college. Then, it's a big work. So, you can divide the work. Preparing invitations, preparing posters, inviting guests, and inviting resource persons, arranging resource person. This is a different task. Each is a different task. No, this is not divide and conquer. If example, this is sort, then the subproblem should also be sort only. Then we call it as divide and conquer strategy. So, if a major problem cannot be solved, divide it, and those problems should also be same. So, this how it is recursive in nature. Like this problem is sorting, then these problems are also sorting. So, divide and conquer algorithms when you write, or strategy when you take, it will be a recursive. So, it says that you recursively solve the problem, if it is too big, recursively solve it. And one important thing is, when you have broken the problem into subproblem, you should have some method for combining their solutions to get a main solution. If you are unable to combine, then you cannot adopt this strategy. So, this is a guideline you can see. See, if any problem, how you can understand, can I apply divide and conquer on this or not? So, if you break it, the problem should remain same. Then I can, then you can apply divide and conquer. Or you should keep it same, then divide and conquer strategy is applicable. And you should have a method for combining them. So, this is the about approach of a divide and conquer strategy. Here is a general method for divide and conquer strategy. Divide and conquer upon a problem P. If small P, if the problem is small, then directly solve it. Yes, definitely there must be a solution for small problem. If it is large you are breaking it. If it is small, then what? Solve it directly. If it is large, divide the problem P into subproblems P1, P2 to PK, and apply divide and conquer on each. This is recursive. Then whatever the solutions you get, you combine these solutions. Okay, combine the solutions of the results of divide and conquer of P1, divide and conquer of P2 and so on, combine them together to get the solution for main problem. So, here you can see that it has having a recursive property, so the procedures are recursive, the algorithms are recursive. These are the problems that are there under this topic. Binary search, finding maximum and minimum, merge sort, quick sort, Strassen's matrix multiplication. We will look at all these problems that will be over different videos, divided into multiple videos. And one more thing is, divide and conquer strategy is recursive, so we should know how to write recursive algorithms, how to write recursive functions, and how to analyze them, how to find the time complexities for them. So, for that we use recurrence relations. So, my next video will be on recurrence relations. So, I'll be having multiple videos on them, so I'll be showing various type of recurrence relations and their solutions. So, you watch all of them, so that you can get a complete idea about recurrence solutions.
