ADA MODULE 5 SUPER IMPORTANT| BCS401 MODEL PAPER SOLUTIONS + PASS PACKAGE | VTU 4th SEM CSE

[00:00:01]Hello everyone, today in this video I'll be discussing the module five of AD Supernode question. These questions are the most repeated ones from the previous two papers. Don't miss any of these questions. And before starting, please do like and subscribe. It helps me make more videos like this. If you have any questions, you can DM me on Instagram here.

[00:00:16]So let's get started with the first question. Explain the following with examples. Okay, there are different types of problems in the AD, which are P problem, NP problem, NP complete, and NP hard problem. What are the differences between them? Okay, with example you have to explain. So what is P problem? P means polynomial time.

[00:00:33]Okay, polynomial time means if the input is N, it will be either 4N or it will be N squared or it will be N cubed like that it will be. If it is exponential, that means it will be 2 power N, 3 power N, 4 power N or E power N like that. The based on the input if it is taking in the powers, that means it will take very huge amount of time for larger inputs. Okay, that is exponential time, which is having 3N or N cubed or N cubed like that. The powers are constant, that is the polynomial time. It is lesser time. Okay, so these are the problems that can be solved in polynomial time by deterministic machine.

[00:01:08]That means the time to solve the problem grows at most at polynomial function of the input size. Okay, polynomial it will be. It will be N squared and all. It will not be exponential.

[00:01:16]Examples are sorting algorithms like merge sort or quick sort, which solve in O of N log N time and binary search which solve solves in O of log N time.

[00:01:25]And conclusion is P problems are efficiently solvable. Next [snorts] is NP problem. NP means non-deterministic polynomial time. Okay, means to solve them it will take exponential time.

[00:01:35]Okay, to solve them it will take exponential time, but to verify it will take non-exponential time, which is polynomial time. Okay, that is the non-deterministic polynomial time. These are the problems where a given solution can be verified in polynomial time, even if finding the solution may not be polynomial. It is not known whether all NP problems can also be solved in polynomial time. Examples are subset sum problem, which is in a set of numbers we have to find out if there is a sum subset which whose sum is equal into a given number. And verifying a solution is easy, but finding a one may exponentially take exponential time.

[00:02:07]Okay. So, NP problems may not be solvable in polynomial time, but they are verifiable in polynomial time. Next one is NP complete problem. In NP complete problem, it is NP complete if it is in NP. Okay, in the class of NP problem if it comes non-deterministic polynomial and every NP problem can be reduced to its polynomial time. If all these conditions satisfy, then it is NP complete problem. Okay, and these are the hardest problems in NP. If [snorts] any one NP complete problem can be solved in polynomial time, all the NP problems can be solved in polynomial time. Okay, that is the conclusion. And [snorts] the example are traveling salesman, Boolean satisfiability problem, and 0/1 knapsack problem. The fourth one is NP hard problem.

[00:02:44]These problems are at least as hard as NP complete problem, but they don't have to be in NP. Solution may not be verifiable in polynomial time. At least the above one was verifiable in polynomial time. Here it is not verifiable in polynomial time. So, this is the NP hard problem. Solving an NP hard problem would solve all NP problems because this is the hardest problem. If the hardest problem is solved, it is pretty common sense that the other easier ones will also be solved. This may or may not have a decision version. Okay. Example is halting problem, traveling salesman problem, and chess in general case.

[00:03:15]Moving on to the second super market question, which is illustrate N queen problem using backtracking to solve four queens problem. Okay, this is the very highly repeated problem. Okay. So, here the problem is to place N queens on a N cross N board such that no queen is attacking any other queen by being either on the same row, column, or diagonal. You in the chess you know, right? If a queen is placed like this, the queen can attack in the same column, same row, and same diagonal. Okay. So, we have to place four queens such that e- each of the queen will not attack each of the other queen. Okay. So, four rows, four queens should be placed. So, if we started basically from here, this is the diagram you need to make in the exam. Start from the empty board here and place the first queen. We can place the first queen anywhere, right? If you place it here, fine. And if not, we'll be placing it here. But first we'll start from here. Okay, let's assume we place the first queen here. No issue.

[00:04:05]Then second queen. Can you place the second queen here? I cannot place because this queen will attack. Can I place the second queen here? No, because this queen will attack. Can I place the second queen here? Yes, I can place because this queen and this queen cannot attack each other. So there is the place where I will be placing. Okay, so here I have placed it. And >> [clears throat] >> third queen where I will place? Third queen have to place in the third row.

[00:04:26]Third row I cannot place here. I cannot place here. I cannot place here. I cannot place here. Why? Because these two queens will attack in all of these positions. So this is the wrong position. So we have to change this position. Try it here. When we try it here and if you place the third queen while placing the second queen here, if I place here I cannot place it because it will attack. Can I place it here? Yes, I can place it, right? I can place it here. But then fourth queen I cannot place. Fourth queen I cannot place here, here, here and here because in all of these positions these three queens will attack. So this position is wrong. Then we'll check this position. This position if I place this queen will attack. If this position if I place this queen will attack. So it has been seen that either of these positions, whatever I place the queen here there is no solution. That means this queen's position has to be changed. If this queen's position has to be changed the second solution is here. Here if I place the queen and the second queen if I place here it will get attacked. Here it will get attacked. Here it will get attacked.

[00:05:21]Here it will not get attacked. So I'll place the second queen here. Now taking this into consideration, I'll place the first queen here. If I place the first queen here any queen attacks? No, it does not attack. So I'll be placing the third queen here. And taking this into consideration, fourth queen can I place here? No. I can place here? No. Can I place here? Yes, I can place here because this queen will not be attacked by either of these queens and already these queens are not attacking each other. So, if I place the four queens in this manner, I'll be getting the final solution. Okay? Like that you have to make this diagram. Okay? To expect full marks. Next is how the branch and bound technique is different from backtracking. Okay? And solve the following instance of a knapsack problem using branch and branch and bound technique. Give knapsack capacity 10. Okay? Now, this is the table given to us and we have to first find out the difference between branch and bound and backtracking. Now, in backtracking we find out a solution.

[00:06:15]Okay? But in branch and bound we find optimized solution. Okay? Solutions might be there, but what is the best solution? We find out that. Here we find [snorts] any feasible solution. Here find the optimal solution, maximum or minimum cost value. Here we reject infeasible paths based on constraints.

[00:06:30]Here we reject suboptimal paths based on bounds like cost. If the cost is increasing a certain limit, we'll reject that path. Okay? No need to evaluate solution value, only check feasibility.

[00:06:39]Here we are checking feasibility as well as the value, which is the best value we are selecting. Here it is depth first search. Here it is breadth first search. And N queen, Sudoku, subset problem are the examples of the backtracking. And in branch and bound we will be solving the problem such as traveling salesman problem and 0/1 knapsack problem. Okay? Now, this is the table given to us and the knapsack capacity is 10. First thing what you need to do is find the weight by value sorry, value by weight ratio.

[00:07:04]Divide these two and write here. Divide these two and write here. Divide these two, divide these two, write the answers here. After writing these answers, use this formula to find out the upper bound. Okay? What you have to do first is first take the zeroth node. Okay?

[00:07:16]Now, W is equal to zero. That means initially I have not taken any node, so the weight will be zero. And since weight is zero, I'm not taking any item, value will also be zero. Okay? And we have to find out the upper bound. Apply these values W V in this formula. And capital W will always be 10. So, when you apply these values here, which is zero is from the V value, which is zero here, and 10 is from the upper bound I mean, sorry, the knapsack capacity is W here. And this zero is nothing but this W value. And here is the ratio. Ratio also we have to take, which is 10. Ratio how we will get? This is the ratio, okay? And you have to take the ratio I + 1 and W I + 1. I value here it is initially zero.

[00:07:56]Zero + 1 is 1. So, I value when it is 1, this is the I value, okay? This value have to take. Zero + 1 is 1. So, I + 1 here it is 1. So, this value, what is the value weight ratio? This we have to take and write it here. So, when you do that, you'll be getting here 10, okay?

[00:08:12]So, 10 into 10, which is 100. So, upper bound will be writing here 100, okay?

[00:08:17]And we have to expand those nodes whose upper bound is greater, okay? Now, since this is single upper bound, we'll be expanding both of them, okay? Means with one and without one, okay? First item you have to consider with first item or without first item you are will be taking into consideration. Now, with the first item when we do, what we are trying to say is that with including this first item, if I calculate the upper bound, what will be it, okay? So, with one means I've taken the first item, so weight will be equal to four, and the value will be 40, okay? If I take the first item, the weight will be four, value will be 40, like that, okay?

[00:08:52]So, V will be 40 and W will be four.

[00:08:54]Then we'll calculate upper bound again using the same formula, okay? So, when we apply the values, 40 + 10 - 4 into 6, we'll be getting the value 76. Without one means first item I've not taken. If I don't take the first item, W and V value will be still zero, and upper bound will be 60, okay? If we take this into consideration, then apply the formula here. Zero, which is the V value, 10 - 0 into 6. Why we are taking 6? Because I + 1. Now, I value is here as one. First item we are taking the I value, right? Because first item we are taking into consideration, okay? That matters. If you take into consideration, you have to do I + 1. This is the I value.

[00:09:30]So, I + 1 will be equal to two. In the two, what is the ratio here? The ratio is six. So, the ratio you'll be applying here, I plus one's ratio. So, if you take the first item into consideration, you have to take the ratio of the I plus one's second item. So, six will be multiplied here. Okay. Now, since uh this is 60 and this is 76, we'll be expanding that one which has the higher upper bound value.

[00:09:53]So, if you expand this one with two and without two, without the second item and with the second item. So, if we take the second item or suppose that if we take the first item and second item, what will be the total weight? Weight will be 4 plus 7 which is equal to 11 and the capacity is 10. So, we cannot expand it further. Weight will become 11, it exceeds the capital W value which is the capacity value. So, we'll be stopping it here. Without two, when we do without two, what will be the W value? If you don't take the second item, the value will be uh the weight will be four uh four and the value will be 40 only. Upper bound will change because now we have to take the into consideration the third uh weight value. Right? We're taking into consideration second item. So, you have to do I plus one which is uh the ratio as five. So, five will be multiplied with this value and we'll get the upper bound as 70. Now, again compare, 70 is greater, 60 is greater. 70 is greater, so expand 70. When you do that with three and without three, we'll be getting two other values for the upper bound and in uh in this case again, here in this case the value which we have got is 64 and here in this case we have got is 69. Now, which is greater? 69 is greater, so we'll be expanding this.

[00:11:01]When we take with four, it exceeds the value as 12 because suppose we took the one value and three and four. First item, third item, and fourth item. First item plus third item is 4 plus 5 9, 9 plus 3 is fourth item if we take, it will be 12.

[00:11:16]So, it will exceed the value, right? 12 we cannot take. So, it will be it will be uh not going with the solution. And if we take without four, without four when we do, we'll get the value as 65 here. Okay. And uh 65 again is greater than 64 and 60. And here we have reached the final solution also. Right? We have got the value as W as 9, V as 65, and value as 65. And after this point, you can either expand this or not expand this. Even if you expand this, there is no point. Why? Because the upper bound is smaller here. Okay? You will not get the optimal solution. Optimal solution we have got here by considering all the elements and deleting the elements and selecting the elements consecutively. Okay, so first element, second third element uh only selecting the first and the third element will give us the optimal solution. Okay? So, if we select the first and the third element, the weight will be 9, and the value will be 65.

[00:12:09]That is the uh highest value which we can obtain with the capacity as 10. So, this is how the branch and bound technique works. This is the thing which you need to make in the exam. Okay?

[00:12:18]Next is what is backtracking? Explain the backtracking to solve the subset sum problem. Okay? Now, see. Backtracking is a systematic way of trying out different possibilities for the problem. We will say call the possibilities you which can uh give us the solution. And where we build a uh step-by-step solution to reach a point where we can't continue, we go back and try another option. Okay?

[00:12:37]So, if you reach a point where we cannot continue, we'll go back and try some other option until we reach the final solution. Okay? That is a backtracking.

[00:12:45]Now, given uh value of D is 30, and this is the uh subset uh set given to us, which contains the following elements in the increasing order. Okay? Now, what you have to do is in increasing order only you have to take into consideration. Now, D is equal to 30.

[00:12:58]What is basically the subset sum problem is, I have to select the elements from this uh set such that the sum will be 30. Example I can give you one. Five I will select, I will select 10, I will select 15. What is the sum? 5 + 10 is 15 + 15 is 30. So, this forms one solution, 5 10 and 15 from this set. Like that we have to find out all the possibilities.

[00:13:16]So, how do we do that using subset sum problem? You have to make this in exam.

[00:13:19]Okay? Now, see. From uh if you don't take an element, it will be zero. The value will be zero, the sum value. In this entire node, all the nodes what you can see the numbers, these are the values of the sum till that point, okay?

[00:13:30]Now, the first element I have is five, right? I can take five or reject five.

[00:13:34]If I take five, my sum will be five. If I reject five, my sum will be zero, okay? Now, we'll be expanding each of these, okay?

[00:13:41]>> [snorts] >> If I don't If I select five, my next option is After selecting five, I can select or not select 10. In that case, again two branches will be formed.

[00:13:49]Select 10 or not select 10. If I select 10, I'll get 15 here. If I don't select 10, I'll be remaining with five. Again, after five 15 is 12. I can select 12 or reject 12, right? So, if I select 12, it will be 27. And if you observe carefully, if I select five, 10, and 12, it will become 27. And after that, there is no element if I add, it will become 30. So, here the solution ends, like that, okay? And if I reject 12, if I don't select as 12 here, my next option will be 13. Either select or reject 13. So, that's what I'll do.

[00:14:21]Either select or reject 13. If I select 13, it is 28. Again, it's not the solution. After that, also there is no element uh which will give me the value 30. If I don't select 13, I'll be remaining with 15. And if I reject 13 also, my next element is 15 here. Now, 15 I can select or reject. If I select 15, I'll get an answer which is 30, which is the answer I want, one of the answers. So, in this case, basically what happened, I selected five, I selected 10, I rejected 12, I rejected 13, I selected 15. So, five, 10, and 15 if I select, that will form 30, and that is one of the solution, which I initially also discussed with you, right? If I don't select 15, it will remain 15, and after 15, there is no other element which is uh in this case only 18. If I add 15 with 18, it will not be 30. So, the solution ends here, okay? And uh the same thing we'll check with the other one. We have expanded this part and got one solution here, right? Now, we'll expand this part where without 10. If I don't select 10, my next option is 12. I have the sum five only if I don't select 12. I I mean, don't select 10. If I select 12 with five, it will be 17. And if I don't select uh 12, it will be still five only. And if I don't select 12, okay, if I don't select 12, it is still five only. I till this point I have the sum five, okay.

[00:15:33]Five plus any of these combination of elements will give me 30. It can't give me 30. Five plus 13 is 18, no 30. Five plus 15 is 12 20, no 30. And five plus 18 is 23, and that is also not equivalent to 30. And after that also if I add any element it will exceed 30. So no combination of these elements with five gives me the result. So without uh Where I was? Yeah, I was here, right?

[00:16:00]With five, without 10, and without 12.

[00:16:02]If I do, after that I'll not get a solution with any combination. So here it will end. But from here, if I select 13 and reject 13. If I select 13, I'll get 17 plus 13, which is 30. It is a solution. If I don't select 13, I'll remain with 17. And after the 13th element, uh 17 plus any of these elements I'll not get the solution. So here if I select or deselect 15, 18, and all, I'll not get a solution. So I'll be stopping it here. I've got two solutions. By expanding this part here, okay. Now I've got two solutions with five. Without five, let's see if there is a solution or not. Without five, if I select with 10, without 10, it will be in these two nodes, okay. With 10 means the sum will be 10, okay. I did not select five, I selected 10 here, so it will be with 10. And if I select with 12, again it will be 22, and that will not give me any solution. Without 12 if I go, there will be 10, okay. Now without 12 I have 10. Without 12 I have 10. And 10 plus any of these elements I'll not get a 30, so I'll be stopping it there itself, okay. Now coming to this point, where I don't select 10 also, I select 12, okay. I select 12 means I have the value 12 here. If I don't select 12, I have the value zero. And if I come till this point and don't select any element, after this point the combination of any of these element with zero will not give me the solution. So, till this point I'm zero and after that if I select 13, 15, 18 in any combination, I'll not be getting the answer. So, I'll be stopping it here. Now, if I select with 12, I have two options, select 13 or reject 13. If I select 13, my answer is 25, that will not give me the solution. And if I select without 13, I still have a possibility. It is 12 only. Now, I have after 13 is 15. Select 15 or reject 15.

[00:17:45]select 15, I'll get 27, that will not give me any solution after that point of any combination of the elements. But if I don't select 15, I still have the possibility. 12 is present. And after that point, if I rejected 15, the only possibility is remaining as 18. And I have 12. And this is a perfect solution.

[00:18:02]12 + 18 is 30. So, in this case, after rejecting 15, I'll be adding with 18.

[00:18:08]And if I reject 18, after that there is no possibility getting the answer 30.

[00:18:11]So, this is one of the solution. Which is the solution? Don't select five.

[00:18:15]Don't select another three.

[00:18:17]Subset sum problem. So, there are three solutions which you have. As you can see in the green, I have the answer is 30.

[00:18:22]This is the solution for this value 5, 12, and 13. 12 and 18. The three solutions for the given subset problem.

[00:18:29]Next is the greedy algorithm to solve the subset problem. Discrete knapsack means in the either is discrete knapsack problem. We're going to select in the case two means two elements we'll select what is the optimal solution. That is the main idea of the greedy algorithm to solve discrete knapsack problem. An example is here. If the K value is two, means two elements are present which you have to select with one element which gives us the optimal solution. Okay. Now, see. In this case, if you observe, what is the solution which you have? The solution which you have is this one.

[00:19:02]4 + 5 is 9. 9 + 1 is 10. Okay. So, 1, 3, and 4 will give us the solution here.

[00:19:07]Okay. Now, in subset I can have two elements. K is equal to two means subset will have two elements. And along with the subset I can have one or more elements. Okay. Now, if I take the subset as one, okay, the remaining elements I'll have is three and four. It will be 69. If I select two, the remaining elements If I select two here, the remaining item I can select is the four. Okay. If I select that, I'll get the value as 46. Okay. Means two and four if I select it will be 46. Like that it will be checking all of them.

[00:20:05]First we'll not select any elements, select single elements, select double elements. Based on these combinations when you find out, we'll be observing that whenever it is one, three, and four we are getting 69 in all cases. Okay.

[00:20:15]Whenever it is one, three, and four.

[00:20:16]Right? So, that is the optimal solution.

[00:20:18]So, this is find out automatically using this formula. Okay. So, this is the thing you need to write. Write this theory and give an example like this.

[00:20:25]That should be sufficient for full marks. Okay. That's all for this video.

[00:20:28]If you found this video helpful, please do like and subscribe. It helps me make more videos like this. And thank you so much for watching. I'll see you in the next one.