L-3.0: Divide and Conquer | Algorithm

Dear students, welcome to Gate Smashers In this video I am going to explain Divide and conquer approach So what is divide and conquer approach? It is an approach to design an algorithm Like we use greedy approach Dynamic programming approach Backtracking approach So first you have to Whether you are preparing for college
university exam or competitive exam So in starting we will talk about Divide and conquer approach So from this name only you will be able to understand What we are actually doing That my problem I am assuming that this is a very big problem So instead of thinking about this big problem What you should do is Divide this problem into small parts Means convert the problem into sub problems Solve those small problems And combine their answers And solve the solution So it is a simple method That my problem is P Which is very large Very large means Let's say we are giving some input The input size is very large So what I did is Divide that problem into small parts Let's say P1, P2, P3, P4 up to let's say Pk All these are my small sub problems What I did to these sub problems I solved them What I did to them Let's say I found their solutions S1, S2, S3, S4, SK What are these sub problems solutions Finally what I did to them After combining After combining I converted the final big solution So this is actually divide and conquer In this you can say a big major That if these are sub problems It is not necessary that you do them serially Means first this and then this If we talk about today's time So what can we use in this today's time Parallel computing concept is used If you have heard about Hadoop If you have heard about Spark So actually this cloud computing If you have heard about it So what are we doing there There these sub problems are Parallel run and find out the output And then combine those outputs The key value pair concept Works like this actually So even in normal life Like you are preparing for the Gate exam Preparing for the Net exam When you check its syllabus Once you see the syllabus You get scared that who will do so much syllabus There are so many subjects It is very difficult to do them in deep So there is a big problem What we did to it is a small problem Means subject wise I started preparing First one subject, second then third Started revising them And finally by combining them in your mind All topics you can say I have made a final preparation So that I feel Finding the solution is easy for me So this is actually divide and conquer approach So this is what its pseudo code says If the problem is small If the problem is already small Then there is no problem Then you find out its solution directly But if the problem is big Then you divide it Big problem in small sub problems What is applied on those small sub problems You divide and conquer Means if the problem is still big Means if you divide it in P1, P2, P3 Even now if you feel it is big Then make it smaller and smaller Take it to the base And then what we do after that Find out their solutions and combine them Their result to find the final answer So it works like this So what kind of applications come in it First comes Binary search Find maximum and minimum Quick sort, Merge sort, Strossen Matrix multiplication So we will discuss this one by one So that in competitive exam, college, university exam Anywhere they ask you you can answer it easily Thank You.