CT - Live session

Ajouté : 2026-05-04

[00:01:08]So I hope can can anyone confirm?

[00:01:14]>> Yes.

[00:01:17]>> So today we are going to discuss uh week 11 concept. So in week 11 we taught uh deput search on our 12th data set. So we will see some examples and uh check how dust search work and uh also we discussed uh recursion. So I'll give uh some questions and uh I'll basically discuss some questions related to this recursion and uh we will see how this person so let me share my screen.

[00:02:12]Okay. So first of all uh recursion. So what is recursion?

[00:02:17]So a recursion is basically uh a way or uh an algorithm that we use to solve uh some problems and uh uh in like uh those problems there will be a pattern where uh we will have uh some base case Yeah. So we will have uh some base case and uh based on the base case we will do something. Okay. So this will be there and uh then we will have uh the recursive step.

[00:03:07]Okay.

[00:03:11]So the base case is basically uh uh it helps us to terminate the algorithm like uh suppose we are calculating factorial.

[00:03:20]So in factorial uh the base case could be uh if we have to find uh the factorial of zero so it is what one similarly if we have to find uh the factorial of one so both are one. So we can say if n suppose n is the variable that we are using to track the numbers.

[00:03:42]If n is less than equal to 1 then we can just say uh in the base case that if n is less than equal to 1 then factorial of n would be one. Okay. And then we have the recursive step. So what recursive step does? So I'll take the example of uh factorial itself and try to explain what uh recursive step do. So suppose we have to find the factorial of some number n. Okay, we have to find the factorial of some number n and uh suppose in the question it's given that uh or it's uh like it could be given that n is greater than one or uh uh there is a possibility that uh we don't provide any related then what you can do is in the base case you already have this part that if n is less than equal to one then we will just return one. Okay. And uh the other case is if n is greater than 1. In that case what we will do? So we can just say that uh we will find the factorial of n -1.

[00:05:13]Okay.

[00:05:14]And uh we will okay so we can uh do that.

[00:05:32]Sorry uh not f of m it should be f of okay we can do this. So suppose if we have to find the factorial of three. Okay. So based on this recursive step what we can do? So we can uh pick our d.

[00:06:03]So we can pick our n and uh n is currently t and then we would do f of n minus 1 which is 2. Okay. Similarly we need to expand this part.

[00:06:21]I'll expand that part as well.

[00:06:28]We can write that over here.

[00:06:35]Okay. Now uh we will expand this part.

[00:06:38]So it would be the same thing. We will use the same formula 2 into factorial of 1. Okay. Now in the base case we already have defined that if the value of n is less than equal to 1 in that case we we will just return one.

[00:07:04]So the value of factorial of one would be 1 itself. Okay. So we will get 3 into 2 into 1.

[00:07:16]So using this algorithm we can just say that uh the factorial of uh three is six right now now uh there is uh another way to say or solve the same problem. So uh if we have to find the factorial of three again and we don't need to we don't want to use recursion then what we can do then we will uh use a loop maybe a for loop and uh using the for loop we can solve it. So uh we can say if uh we will say that uh we will run the loop and uh the loop will be uh executed until we hit three and is three. So what are the possible values of n? So possible values are of n are 1 2 and three. Okay. And we will initialize a variable. suppose uh f itself and we will say that uh f is one. Okay. And uh then we will start iterating over this. We will use a for loop or a while loop and start iterating over this. And uh based on the iteration we will do current f into the number itself. So if we do 1 + 1 for the first number we'll get one itself.

[00:09:14]Then for the second one we will get uh again f cross or f into two. So the current value of f is 1 itself. So we will do 1 + 2 and we are getting two. Okay.

[00:09:40]Now for the third number that is three.

[00:09:42]We will again do the same thing.

[00:09:47]So current value of s is two. We'll do 2 + three. So that is six. So this is a simple method uh using loop and the previous one that we used was recursion where uh we have a base case factorial of one was our base case.

[00:10:09]Okay. And uh uh we then uh started decreasing the value of n. And uh once we hit the uh base case we put the value of uh f of uh n for the base case we put the value and then try to calculate uh any factorial that we want. Okay. So this is basically what we do in recursion. So if we want to have uh a pseudo code maybe or a rough idea what a recursion has. So suppose we want to define a procedure.

[00:11:00]Okay.

[00:11:08]So we will just say if n is to zero we will just stop whatever we were doing. Okay.

[00:11:25]It could be zero. This depends on the problem that you are trying to solve.

[00:11:29]like in the previous problem uh it could have been zero itself. Okay. And uh this will change the condition will change but uh this is the uh thing or this is uh the base condition that you use generally. Okay. So if uh the condition is met you will just stop otherwise you will do something.

[00:11:55]Okay, do something and then you again call this function or this procedure recursion instead of Fn we could have just record.

[00:12:37]So we could just call recursion of n minus one. Okay.

[00:12:45]So this is the thing that we can do.

[00:12:49]Any doubt in this one?

[00:13:00]anyone?

[00:13:06]>> Okay. So, similarly uh suppose we want to find uh the sum of uh maybe first n numbers. Okay. So in that case there is a for loop method where we iterate over all the numbers and then try to add the numbers and get the result. Uh then there is a recursion based uh method. So if the numbers are uh positive.

[00:13:38]Okay. So if n is greater than uh zero so numbers are positive then if we have to uh create a method or a procedures suppose uh we want to create a procedure sub and this sum would return the sum of all first of integers positive integers. Okay. So till n will some uh and give the result.

[00:14:19]So suppose uh app has some value. So we will add these things up till end and then we will return the result. So for this procedure what we can do? So our base case is what?

[00:14:40]If what is the base condition when we will terminate this particular procedure when the value of this?

[00:15:01]>> Yeah. one. Yes.

[00:15:02]>> Okay.

[00:15:04]So if the value of this is double equal to let me add.

[00:15:17]So if the value of n is this then we will just uh uh return.

[00:15:26]What we will return? If n is just one, what will be the sum?

[00:15:34]One, right?

[00:15:37]>> If the value of n is one and this is the condition, then we we started at one and then after that we didn't have anything. So we'll just return one. So this is our base condition and then we will have our recursive statement and that recursive statement is sum of n minus 1.

[00:16:09]Do we need to add anything else or this is fine?

[00:16:20]So if we just do this we will uh get the result or what >> n plus right >> sorry plus n you're saying >> plus n yeah plus n you >> yeah so we need to add the cell why because if we just do this we are just decreasing and uh uh like suppose uh if we get uh if we use five as the value of n then if we just do this then let's see what happen so we won't execute this part why because n is five right now we'll just directly move to this part and uh we will decrease the value of n I'm for now I'm is skipping this part plus n part I'm just using this one okay so if you do that then you will have log of four.

[00:17:32]Initially we had this then uh we uh we will calculate this. This will return sum of three.

[00:17:43]Again this will return sum of two.

[00:17:49]Again this will return sum of one. And finally this will return what?

[00:18:00]One. Right?

[00:18:03]This condition if n is one n is over here. If n is one >> written one. Yeah.

[00:18:09]>> Yeah. So that is the thing. But uh uh this is not the answer that we are expecting right. So we skipped the plus n part. Let's try to incorporate that.

[00:18:21]Let's try to use that and see what uh we are getting.

[00:18:44]So first we are here the value of n is five.

[00:18:53]Now we won't execute this because n is uh not uh one. So we'll move to this part. This part is same sum of n minus one that is sum of uh 4 plus n. n is what five right?

[00:19:15]So this uh when we uh call this we are getting this from the function. Now this is again a call to this particular procedure right so we will uh expand this as well.

[00:19:31]Sum of four is what? Sum of four is again coming from this part. So sum of four is sum of three.

[00:19:40]Then we have + n. So plus n is what?

[00:19:43]Four plus five. Five we already have over here. So I'll just add that. Then we need to expand this as well. So if we expand this, this will become this + 3 + 4 + again expand.

[00:20:20]Now again this is again a function call.

[00:20:23]So we'll try to expand it again.

[00:20:34]Now one thing uh you should note is sum we are calling sum with uh value of one.

[00:20:42]So this is true for this case and if this is true we'll return one right and uh from the previous state we already had this. So let's try to just add it and now we can sum this and return the result. Okay so uh we'll get 15. Okay.

[00:21:13]Any doubt in this one? Whatever we have done.

[00:21:32]Okay. I I assume there are no doubt this particular question. So if that is the case now uh let's try to do one more problem on recursion then we'll move to the deficit.

[00:21:49]So and uh this problem uh basically you will have to tell me what uh we will do.

[00:21:55]I won't uh write the procedure itself.

[00:21:58]You will guide me what to write and uh based on whatever we get then we'll take an example and try to see whether we are getting the correct thing or not. Okay.

[00:22:13]So are you guys familiar with Fibonacci series?

[00:22:19]Anyone familiar with uh the series?

[00:22:22]>> What is that?

[00:22:24]Uh so it is the sum of previous numbers starting from 1 1 2 3.

[00:22:34]>> Okay. So we just uh sum the previous numbers that is the only condition or uh do we have uh anything else as well?

[00:22:46]>> Sorry.

[00:22:48]>> So you said that it's just the sum of previous right?

[00:22:53]So all the previous numbers or uh do we have any conditional impact?

[00:22:59]>> No just one previous number >> just the current number and the one just before that.

[00:23:09]>> Okay. So let's try to see some example.

[00:23:13]So we'll start from you know >> so like if you want to write it in equation it will be f_sub_n equal to uh f_sub_n -1 + fn minus2 >> okay let's try to write that those who are not familiar with uh this uh this is uh one of the most important series that we use in programming. So just try to remember this part.

[00:23:51]Okay. So the current value of uh the series would be the sum of whatever we had uh the sum of previous two elements that we have in the series. Okay. So suppose we have zero and then one to get the third element. What we will do? We will just add these two things. Okay. So if we add these two things we are getting one. To get the next number what we will do? Add the previous two. So we will get two. Okay. To get the uh fifth element we'll add third and fourth symbol. So this will become three.

[00:24:36]Similarly, if we have to find this five and so on. Is this clear?

[00:24:43]So get to get the current element, we will uh sum the previous two elements and uh that is the value of your current element. This is the function that we use.

[00:24:56]Any doubt in this one?

[00:25:04]Okay. So I hope there are no doubts.

[00:25:07]>> Understood.

[00:25:09]>> Okay. If that is the case, uh let's try to write a recursive method and you guys will guide me what to write in the procedure or method and uh then we will just take an example and see whether whatever you guys think the procedure should look like it is giving the predictive number. Okay.

[00:25:35]scope and just say fib n.

[00:25:40]So this is our uh name of the procedure.

[00:25:47]Now uh we have two things. So I'll add uh those two things. So this is our base case and then over here we will have our recursive case. Okay.

[00:26:05]So, what should be the base case?

[00:26:19]Anyone? What should be the base case?

[00:26:38]You have to remember uh the initial values of the CDs. So the CDs goes like this.

[00:26:52]These are some of the initial values.

[00:26:54]Now based on these initial values you have to tell what is the base case. Now uh what is n?

[00:27:02]N is the index basically. So for this particular thing n is uh for zero n is uh one for this first one n is two.

[00:27:17]Sorry we use zero based indexing. So this is zero. Okay, this is 0 one.

[00:27:28]This is two. This is basically indexing.

[00:27:30]Uh nothing fancy. So we are using zerobased indexing. That's it. Okay. And uh if you want you can use uh this as both have the same thing.

[00:27:42]But uh when you start programming you will use this because in programming uh the indexing is zero based indexing. So that's why.

[00:27:52]Okay. So we'll uh create uh the base case. We'll create the condition for the base case using this part the initial thing. Which one do you think we should take the zero index the first index or second index?

[00:28:22]It is fine to make mistakes but you have to try index.

[00:28:56]So you are saying if n is equal to zero we will return zero.

[00:29:12]Right? We are saying this uh what about the recursive step?

[00:29:30]What about the recursive step?

[00:29:41]N= - 1 + 7.

[00:29:46]Yeah.

[00:29:47]So we will just say uh fn minus 1 plus fn minus 2.

[00:30:05]Let's try to take an example and see whether we are getting the correct thing or not. So let's first write uh the whole like some initial part of the series so that we can check.

[00:30:26]Okay.

[00:30:28]So let's say we are checking for this one. Okay. When n is equal to what? four or the three and equal to five >> sorry I'm talking about this element we have to find the value of this element so for this particular element >> two what is the value of n what should we This is your zeroth index, first index, second index, third, >> third. Right?

[00:31:16]>> Is three.

[00:31:20]So we will do this.

[00:31:25]Now we will check this condition the base condition. Now n is not equal to zero. So we will move to this part. This will become f of 2 plus f of >> 1. Right?

[00:31:49]Now we need to again expand. So we need to expand this and this. Let's see what we are getting. Both are calling uh the same uh procedure. So we need to expand both the things. In the previous example uh there was a con constant so a number and uh there was one function call only.

[00:32:09]So that's why we were uh just expanding that function called but here the function is getting called uh twice. So we'll try to uh expand both the things.

[00:32:20]Okay. So uh suppose in any other example if you find that uh your recursive so a step is calling the same function or the recursion function five times. So you will have to expand all the five things.

[00:32:37]Okay. So we will expand this f of uh two. So for this again we will do this because n is not equal to zero. So this part will become let me change the color so that uh we are clear what we are doing. So the first part I'm writing is background.

[00:33:11]So for this one we can do this. Okay.

[00:33:22]And uh for the second part this one we will do of zero.

[00:33:46]Now this part is not there. Okay. So either in the record step itself you can say instead of having this particular thing you could directly say if it's less than equal to zero then you will return zero. So if we use this analogy um for this particular thing let's first try to explain this. So f of 1 is again the same thing. So we'll write f of 0 plus f of minus one.

[00:34:30]What about this one?

[00:34:36]What about f of z? When it comes to when it comes to zero, you have to return it.

[00:34:42]How to put only directly zero, right?

[00:34:45]Why minus one? You are put it here.

[00:34:50]>> For this one, we have to use this, right?

[00:34:55]>> Sum of previous uh two elements.

[00:34:59]>> We need to go with two base cases.

[00:35:04]>> Not two base cases.

[00:35:06]I there are there is uh uh recursive uh definition uh where you used to have two base cases but uh in the current definition or in the current procedure we are not using that. Let me clear this and uh write it clearly so that uh you are clear what we are trying. So if n is less than equal to zero in that case we are returning this.

[00:35:37]Why we use this? Because uh while expanding we encountered minus one. We can't change the definition of the function. The definition of the function is f of n is what?

[00:35:51]f of n minus 1 plus f of n minus 2. Okay. So we can't change this. Now for this one while expanding this if we use this formula then we are we will get f of n minus1 will be f of0 and f of n -2 will be f of minus1 right now again the same thing for this one as well that I have written.

[00:36:26]So f of 1 would be f of uh 1 - 1 that would be f of uh 0. Then f of 1 - 2. So that is your f of -1. Okay.

[00:36:41]Now I was asking about this part. So we haven't added that yet. So what will be the value of f of z?

[00:36:52]>> f of 0 would be zero. Why? Because we have uh written over here that uh if uh n is less than equal to zero then we will directly return zero. So that is what we are doing. Okay. So this is return zero. Then again we have the same thing again. So we'll again write zero.

[00:37:18]This will again give zero because what?

[00:37:37]Because add is less than equal to this.

[00:37:40]Right now f of uh zero. Okay, I think I made some mistake because the answer will is zero based on this.

[00:37:57]Let me check once.

[00:38:02]So we are finding this part.

[00:38:27]Okay. Uh for this we need one more thing that uh we hadn't added earlier.

[00:38:39]Let me remove this part.

[00:38:49]So we have one base case over here and we will add one more base case that is if n is equal to 1 then we will return one. Why are we using this? So if you remember while defining the function or some uh while we were writing uh some of the elements of the series so we started with this and then we started to build the whole thing. Okay. So in the base condition this first base condition we used this but this was not there. So we need to add this as well.

[00:39:32]Okay. So that's what I have added. And uh the last thing the recursive step would remain the same. So we'll just say f of n minus one and then some uh add f of n minus 2.

[00:39:53]Any doubt in this part?

[00:40:00]>> Okay, there is no doubt. Let's try to expand this again. Let's see what we are getting now.

[00:40:12]So in this case uh we have two base uh conditions. Okay. So for this problem we have two base uh conditions and uh like uh in some other case you may have more than that as well. So you have to carefully analyze the problem and based on that uh you have to create your base step the base condition and your uh uh final recursive condition. Okay let's again try to expand this.

[00:40:45]So this will be f of 2 plus f of one.

[00:40:58]And yeah, that's it.

[00:41:11]f of one and uh then we will expand f of two part. So let's try to do the f of two will become f of 1 plus f of this is z right?

[00:41:31]So this is your expansion for the blue part and uh what about the green part what we will get for this one >> right from this case we're directly getting one.

[00:41:49]>> Now let's see this again. What about this >> one?

[00:41:56]>> Again one because n is one so we will get one. What about this one?

[00:42:02]>> Zero.

[00:42:03]>> Zero.

[00:42:04]>> Zero from this base condition. And then we already have one. So we'll do that.

[00:42:11]And we are getting two. Okay. So this particular thing you can use for any uh you will you can basically use to calculate any element uh of the F.

[00:42:24]>> Can we remove less than sign after adding two bas?

[00:42:29]>> Yeah. And uh that you can do to because uh uh once we hook uh up these two base condition we won't uh go to minus one and other thing. So if you want you can change this particular thing to equal to.

[00:42:50]So this is also okay both are the same thing.

[00:42:56]any doubt.

[00:43:03]Okay. Uh let's try to see one more thing and uh then we will move to your uh DFS part.

[00:43:14]So I'll remove this expansion part. I'll keep the definition of the procedure and uh remove. So sir, we can get recurs recursion questions in the exam as well, right?

[00:43:26]>> Since it's uh used in your uh lectures, we have taught uh recursion in the lecture. So you can expect to get the questions related to recursion. So what is the weightage going to be for week 1 to uh 8 and 8 uh 9 to 12?

[00:43:51]on that I'll have to check with the team maybe uh I think on Monday Mandepai will take the second I think you can check with her because uh I think uh the end turn paper was made by her so you can check her okay >> okay and one more thing sir actually uh so sir right now I'm already uh like I have enough you marks in quiz one and quiz two. So the formula for calculation is that they'll take 25% from quiz one and 30% from quiz two and 45% from the final. Right?

[00:44:30]>> That's the grading rate.

[00:44:32]>> So right now if I see I'm already getting enough marks to like clear the subject.

[00:44:38]>> Uh for like 40% is the threshold to clear the subject. Right.

[00:44:44]>> Mhm. Right.

[00:44:45]So I'm already getting with both the quizzes enough marks to clear the subject. So in the end term there is a threshold marks I need to get in the end term also or like uh I can like get as many like even if I get like 0 1 2 I will still clear the exam because I already have 40 or this again you have to clear with because uh she is working slowly uh these topics. Okay. So check with her on Monday. You can ask these questions and she will give you the correct.

[00:45:23]>> Okay.

[00:45:23]>> I don't want to comment on things which I don't know because uh suppose I say that uh you can skip in term and uh you skipped it and later you find that uh >> no sir I don't want to skip it per se.

[00:45:36]Obviously I want to maintain my grades but I'm just asking to you know to get an idea because yeah just to get an idea. you can uh ask manip and uh she will give uh you the accurate answer. Okay.

[00:45:51]>> Yeah.

[00:45:52]Now uh this particular thing we can use uh a tree diagram to visualize this in BFS and DFS we use trees. So are you guys familiar with BFS?

[00:46:06]>> Yes.

[00:46:07]>> Breath first search. Okay. So we use bre first search and uh death first search to search some uh thing and any gate type list or anything. Okay. Oh, give me Okay.

[00:47:09]So suppose uh we have to calculate again I'm taking the example of same thing. So f of uh three only.

[00:47:26]Okay. So f for f of three uh what we did it was dependent on fibonacio of two and fibonacio one. Right? Now uh f of one what was uh it dependent on >> it's not dependent on anything because in the base case we already have that right so it's not dependent on anything now f of two is again dependent on something let's try to figure this out.

[00:48:15]>> Okay.

[00:48:17]Now you can use uh these kind of diagrams to visualize uh your uh recursion method and uh based on this you can just expand the thing. So what you can do instead of writing the whole thing expanding the whole thing you can just create this diagram uh it will help you to visualize uh the steps and uh for this one you will just write one then for this one you will write zero just expand the leaves first. So this is the leaf this is the leaf this is the leaf.

[00:48:48]So let's try to expand those first.

[00:48:51]Once that is done, move one step uh before.

[00:48:56]So let's try to expand this one. So this is what this is the sum of these two. So 1 + 0 is 1. So this one has value 1. For this one, we have already expanded. Now for this one, this is sum of this and this. So that is two. Okay.

[00:49:21]I hope this is clear.

[00:49:23]>> Yes.

[00:49:26]>> So if that is the case then now we will move to DFS.

[00:49:42]Okay.

[00:49:43]So suppose we have a graph.

[00:50:25]This is your node. One, two, 3, 4, 5.

[00:50:35]Let's use some print color otherwise it would be very cluttered.

[00:50:55]So we have eight more. Okay. So NDF is uh basically the concept is uh suppose you are trying to expand a node. So suppose we start at this node one.

[00:51:11]Suppose we try to expand this node. So what we will see that uh we have there are two data structures that we maintain. So one is scene and uh uh the other one is uh your children's you can say. So uh we will just see the children's of one. So we will store it in some data uh data type. Okay. So we'll store and use that. So currently we have seen this node. So I'll add scene over here. Uh one over here and uh we will explore one. Okay. So for explore I'll just write E. Okay. So if we explore one, so this will give uh the childrens of the children of one. So we have uh two children two and three.

[00:52:05]Okay. Now we have to explore one of them. Okay. So let's say I'm um taking the smaller index. So we will then do explore two. So in scene we will say that we have explore two. And this explore two will again give us the children of node two. So they are what?

[00:52:30]Four and five. Right? Those are the two children of uh node two.

[00:52:38]Now again we will do the same thing. So we'll pick four. We'll say that we are exploring four. Add four to scene.

[00:52:49]And uh while exploring four we'll see whether uh there are any child note or not related to four. There are none. So we'll maybe say nothing. We found nothing.

[00:53:10]Okay. And uh once we found nothing, we will move one step back to the parent.

[00:53:18]Okay. And uh this was the parent and we have already seen this and in the expansion we will check whether do uh we have any other node or not in the child.

[00:53:29]So four we already explored five is there. So now we will explode pi.

[00:53:37]Okay. So we'll explode pi. We will add it to this scene list. And uh this is basically a set not list. So when we implement this uh particular uh procedure dfs uh then we use uh seen as a set so that we don't have any detail values. Now again we are doing the same thing for node five. We are not getting anything. We'll move one step back.

[00:54:09]See this part over here. We have two things right. And we have already explored both the things. So we will again go back uh go to this part check its children. So two we already have explored. Three we haven't. So let's explore three. We're exploding three.

[00:54:33]Now add three over here. And now three has one child.

[00:54:40]Three has six. Okay. Now we will explore six. So let's explore six.

[00:54:48]We're exploring six. It is added to the scene set. Now we will expand six. So it has two children seven and eight. Now we will pick the smaller one.

[00:55:04]Explore seven.

[00:55:08]Seven is added over here. When we are doing explore 7, we are getting nothing because uh seven is the leaf node. It doesn't have any children.

[00:55:19]So now we will again go back to this step. We have two things. over here eight is not 8 was not explored. So now we'll explore eight when we explore eight we'll add this over here and uh we will get nothing. Okay.

[00:55:46]Now uh so we won't go back in this case because uh uh in the real implementation of uh DFS what we do is we check this part this scene set and check whether uh we have exhausted all the nodes or not.

[00:56:08]Okay. So in this case if you see there are eight nodes and uh in the scene set we already have eight uh distinct uh nodes. So that means we have already exhausted uh the list of nodes that we had. So we would stop executing this uh algorithm and uh this is the order uh in which we check the notes. So first we check one we visited one then from one we move to two from two we've moved to four from four we move to 5 to 3 to 6 to 7 and finally we move to eight so this is the order in which we visited the nodes okay so this is DFS so how do we know it's DFS so uh and the DFS D is for depth. Okay. And uh F is first and uh S is search. So if you see when we moved so first uh we went from one to two and two to four. So first we check this. Okay. Then we check this part.

[00:57:29]Then again let me clear up this diagram a bit.

[00:57:56]Okay. So, first we explode this, then we explode this, then we explode this part till 7 and finally we explode this part. So if you see when we start exploring the left branch so these are branches. So this is your first branch.

[00:58:22]This is your second branch. So when we uh started exploring the branches uh first we explored one of the branch till its leaf. Okay. So we went till here then explored this part. Once that was finished, once the left branch was finished, we explode all the nodes, then we move to the right one. Okay. So that's why we call this DFS left first sort. So first we explore all the uh children till which are available on a particular branch and uh then we move to the next branch. Okay, next level branch that is DFS. Let's uh see uh BFS as well.

[00:59:15]So you might be familiar with DFS. Let's try to see what we are uh getting in BFS. And uh I'll keep uh this particular thing for DFS. we are getting this and uh I'll clear the other thing so that uh we get uh the space to see what we are getting for BFS.

[00:59:50]Any doubt in DFS what we did there is any doubt you can ask right now because uh after this we'll just uh try to see how we can implement DFS using some pseudo code and then I'll wrap wrap the session.

[01:00:26]Okay, seems like there are no doubts.

[01:00:30]So let's move to BFS now. So BFS is uh like uh uh in BFS the B stands for breath. So we'll use that. So keep that in mind. So we'll again maintain seal.

[01:00:51]Okay.

[01:00:54]And uh we will again start uh with your first node. We'll explode this one is added to the scene set.

[01:01:09]It has two children two and three. Now we will explore two. Two is added to C.

[01:01:17]Two has again two children four and five.

[01:01:24]Okay.

[01:01:26]Now uh like in DFS we used to check four but uh in BFS instead of doing that we will see whether uh all the children in this state are exhausted or not. If the if they are then we will move to this thing otherwise we will just explore all the childrens and then move ahead. Okay. So now we are exploring three.

[01:01:55]Three is added to this and uh we got six. Now we will see we have this child available, this child available and this child available.

[01:02:06]We'll pick the smaller one. The smaller one is four. So we are picking that. We will explode four. Now four is added over here. And uh when we did explore four, we got nothing because we don't have any child attached to code. Okay.

[01:02:26]Now we'll do explore five.

[01:02:31]So five we have added.

[01:02:34]And uh again when we are doing this we won't get anything because five doesn't have any chat. Now we will pick six.

[01:02:43]Let's do explore of six.

[01:02:47]When we did this we're getting seven and eight. Six was added to C. Now we have explored this this this this is also done. So seven is remaining now.

[01:03:03]So we'll do explode of seven and uh when we do this [snorts] we won't get anything because seven is again a child node. It doesn't have any child connected to it. So that is there. Then 8 is left. We'll do E of 8 and this finish with our algorithm. Okay. So we got this particular list. Now if we compare this one with this one the order is different right? In the in the case of DFS we uh went uh from two to four but if you see here from two we are moving to three not four.

[01:03:54]Correct.

[01:04:00]So this is the thing any doubt in DFS or BFS algorithm.

[01:04:16]I hope I am audible.

[01:04:20]>> Yes.

[01:04:22]>> Okay.

[01:04:24]So if there are no doubts let's try to see how we can construct a recursive uh DFS procedure and uh use that. Okay.

[01:04:40]So let me clear these things related to BFS.

[01:05:06]Okay. So to define a recursive method or a procedure we need two things. What are the two things >> base case and recursive >> base case and recursive condition or recursive case okay so I'll just write these two things. So we need to just uh focus on these part. So okay so first we need to focus on base case what uh we will use as the base case and then once uh we figured out that then we will do the recursive step.

[01:06:00]Okay.

[01:06:06]So can anyone tell what uh we should use as the base case?

[01:06:46]We uh just solved an example using uh DFS right now. So you have to just figure out what will be the base case why when will you terminate uh your DFS algorithm Okay.

[01:07:30]So, we were maintaining a set if you remember, right?

[01:07:38]we had a scene set and uh while solving the example I also mentioned that we will check whether uh a node is present in scene set or not. Okay. So that is our base condition. So we will check whether uh let's me first write this.

[01:08:02]We will pass uh two things. First is your node which node you are exploring and uh then we will pass your scene set. Okay, whatever you have saved it.

[01:08:22]Now in the base case we will say if node is n I'm using plain English mostly instead of uh using the syntax that we use uh while defining the procedure.

[01:08:50]If you get confused anywhere just let me know then I'll use uh the syntax that we use in lectures. Okay. So if node is in scene what we will do we will just return. Okay. We'll say that uh this node is already there.

[01:09:10]We'll just return. We won't return a node or anything. Okay. We'll say that uh this was seen. We have seen this. So just skip this part. Otherwise what we used to do?

[01:09:25]We used to So this is your base case.

[01:09:28]Okay. So let me add B over here.

[01:09:32]Otherwise in the recursive step we used to add this node.

[01:09:40]So scene used to becomes scene used to become scene plus node. Okay.

[01:09:55]So since scene is a set we are we will use uh set.

[01:10:04]Okay. So we are adding uh the node to scene and uh then what we used to do anyone >> explore node >> explore the node. Okay. So we will explore them. So let me just write children. Okay.

[01:10:36]children would be what?

[01:10:39]E is explorer the note that the method we were using earlier it's the same thing. Okay. So we are getting the list of children.

[01:10:49]Okay.

[01:10:51]Now what we will do?

[01:10:55]We'll say for each children or for each child in children instead of writing the whole thing let's see we'll just say capital okay and uh for this one I'm just uh using or maybe let's use a little okay so for each child and children we will again call DFS with child.

[01:11:45]Okay, node is our child and uh then we have our scene set. We will pass them.

[01:11:58]Okay, is this part clear?

[01:12:05]So this is our uh base case.

[01:12:10]This one is our base case. And whatever we have done over here, this will create our recursive step. So we are calling the function over here.

[01:12:23]And yeah, that's the thing. So any doubt in this implementation? Why are we using this in the base case? Why are we using that in the recursive step? So any doubts?

[01:13:03]Okay.

[01:13:06]So uh let's try to connect this procedure with the example that we discussed uh just uh before implementing this whole thing. Okay. So let's try to explore that our how this uh will give the same thing that we are we got earlier. So whether it will be able to give the same thing. So over here first we will start with one. So the value of node is one over here and scene is currently thin is what empty set right we don't have anything in scene right now.

[01:13:50]So that is the starting point. Now we will see if node is in scene or not.

[01:13:55]This condition we will check that is not the case because uh initially scene was empty. So we won't execute this part.

[01:14:11]We won't execute this part. We'll directly move to this part. Okay. So in the scene we will now add one. Okay. Then we are saying seeing this part. So C is basically what C is all the children of your uh so in the current step C is what C is all the children of node.

[01:14:42]So if we are we were over here we added uh one to scene these are the children. So we will get two and three. Okay. Now over here we are saying for each child in C. So this one we will again run the DFS part. So that means we pick this and now we will again do these steps. So let's try to do that.

[01:15:16]So for two this condition will again be false because the scene uh right now contains just uh one element and that is one. So we will execute this part. We are exploding two and uh over here we are adding two to the scene set. I am doing that. Then we are exploring the node that is we are exploring two.

[01:15:43]So when we explore two we will get four and five. Okay. So we got this. Now over here we have again for each child in C we are doing bfs of. So let's try to do that again. So because of uh the for loop we'll again pick one child. So once we pick the child we will move to this part and this part will again it's because it's recursion. So we will again start doing this part. Okay before moving to the next step. So uh right now the value of node is four and set has uh 1 comma 2 sorry scene set. Yeah scene set has 1 comma 2. We'll again check this part. Is it true or false?

[01:16:39]Sorry.

[01:16:40]>> Uh this for loop you put DFS bracket child and scene right. Uh but how it'll be make a recursive? Uh in top we are mentioning node comma scene right?

[01:16:51]Um so these are variables only right? Child is variables variable.

[01:17:00]>> Yeah uh that is variable. So uh child is also a node right?

[01:17:06]No, but you are using the variable name is different, right? How it will form as a request this year?

[01:17:13]>> That is fine. No, like uh if you remember uh let me give one example.

[01:17:21]So suppose we define a procedure do something. Okay.

[01:17:32]And we say that uh you are passing X in this. Okay.

[01:17:36]>> Yeah.

[01:17:37]>> You might have solved uh this kind of thing many times.

[01:17:40]>> Yes.

[01:17:41]>> While calling it is not mandatory that we use uh the same thing. It's not mandatory to call uh do something with x only. You can have a variable maybe y and y has some value seven maybe and you can call this using y as well. Is that correct?

[01:18:04]>> Uh yes.

[01:18:06]>> So that is the same thing we are doing over there. So one thing that you need to know is that the data type that we are using uh for x over here should be the same uh as y. So if uh x is a list, y should also be a list.

[01:18:24]Okay.

[01:18:26]>> Mhm.

[01:18:27]>> So that is the same. Now over here what I am doing?

[01:18:32]I have uh said that uh we'll call DFS and the first parameter is node. Okay.

[01:18:39]And over here we are again saying that we'll call DFS. This is definition.

[01:18:45]Okay. This is the definition of the procedure and this is calling the procedure. So when we are calling the procedure we can pass anything just make sure that uh whatever data type you expect here we are passing the same data type. So if you see when we are saying that we are uh exploring node one at the same time we are saying that uh node two and node three are the children of node one right so these are again type node only node so the child are only node so that's why we can call dfs using child as Okay.

[01:19:33]Is this clear?

[01:19:35]H but uh this node general it's a um we can use x and y the same way we can put it there right instead of node or you have to specify any variable >> just for readability so that you don't confuse get confused between x and y it's uh better better to use the actual name okay >> okay >> so instead Instead of writing uh children over here, I just uh wrote C.

[01:20:08]Right. It's behaving the same way.

[01:20:11]>> Okay. Okay. Thank you.

[01:20:17]>> Any other doubt?

[01:20:19]If not, I'll move ahead.

[01:20:26]Okay. So, do we explode? We are currently doing four. So, the value of node is what?

[01:20:34]four and scene has these two elements right now. So the question was whether the base condition will evaluate to true or false in this case if it is seen the node is >> is not seen right we don't have uh in this set so how is It's seen.

[01:21:14]It's not seen. Okay.

[01:21:16]>> Mhm.

[01:21:17]>> We passed four over here and scene has one and two.

[01:21:23]And then we evaluate this. This came as false because node is uh that is four is not in scene. So we'll move to this part and we will say that now we are adding the node that is four to scene and now we will explore its children. So do we have any child for four? We don't right.

[01:21:46]So I'll just say we don't have anything.

[01:21:49]So this for loop will this execute?

[01:21:59]Will the for loop execute or not?

[01:22:10]>> Anyone not execute?

[01:22:23]>> It won't execute. Why? Because we don't have any child.

[01:22:27]If you don't have any child, how will you iterate? There is nothing you can't iterate, right? So, this won't run.

[01:22:36]Now, this won't run. So, if you see uh in the previous step, we had for each child in C when we were doing this particular step, right? We had for each child in C. Since we don't have any child for four, we'll move back to that step.

[01:22:59]Okay, we'll move back to that step and see whether we have any child or not. If there is any child because uh we have to execute uh on all the child but we just did on four. Five was left. So now we will do on five. So same thing with five.

[01:23:24]So the the value for node is now five.

[01:23:28]The current uh value for scene is 1 2 4.

[01:23:36]Now we'll see this part. Is this true or false?

[01:23:49]This is false. Right? because current value of node is five and the current value of scene is 1 to 4 which is not uh like which which doesn't contain five.

[01:24:02]So we will not execute this part because this is evaluating to false. We'll again move to this part in scene we will add five and then we will explore the nodes of uh the child of uh five. So again we will see that five doesn't have anything. So we'll move to this part.

[01:24:24]This part has all the child like we have visited all the child. We have seen all the child. So now we will move one step back.

[01:24:34]Three is was left. So let's do three.

[01:24:43]So again the same thing. Current uh value of scene is this and node is three. Now from here three is not uh present in scene. So we'll skip this part and we will execute this part.

[01:24:58]Okay.

[01:25:04]Five. We have done three. We are doing added three. This part won't execute.

[01:25:14]This part we will do. So three was added to the scene set. Now we will explore the children of three. So it has just one child. We'll add six.

[01:25:27]And again we will do the same thing for each child and see. So there is just one child six.

[01:25:37]Now we'll pass six to DFS. This part we are passing six as child and uh scene has uh 1 2 4 5 and three. So we are passing that. Again we will check the base condition.

[01:26:04]Again we will check the base condition that is this part and uh this will again execute. This will again not execute because node is not in scene because we don't have six in scene. So this part we will skip and we'll move to this part.

[01:26:22]We will add six in scene.

[01:26:25]We'll explore the children of six. So let's see what do we have for six. So six has two children 7 and 8.

[01:26:38]Seven and 8. We will explore the children one by one. So we'll first pick seven. Do the same thing. Seven is not there in set. We'll add seven.

[01:26:52]And seven was a child node. Seven. Seven is a child node itself. So seven doesn't have any child. Then we will explore eight. Same thing.

[01:27:05]And finally DFS will return this thing. Okay.

[01:27:12]So over here we are currently not returning anything.

[01:27:17]So you can just say that we are returning C. Okay. So if you return C then you will get the path. So the current path that we are getting is 1 using the sodo code 1 2 4 5 3 6 then we have 7 and then we had 8. Okay.

[01:27:44]So this is the order 1 2 4 5 3 6 7.

[01:27:49]Let's try to compare it uh with what we had earlier.

[01:27:53]So 1 2 4 5 3 6 7 and 8. Okay. So both are uh matching with any doubt.

[01:28:10]If not, I'll close the session.

[01:28:23]Okay. So, this is DFS and uh for BFS uh as you like we discussed BFS as well. So try to like uh as maybe your homework what you have to do is you uh just uh try to write uh uh the recursive implementation for BFS. How will you use recursion to implement BFS and uh pick one example if you want you can just uh pick this example itself and uh since we stream these uh live sessions so uh I already provided uh those flow or uh the sequence in which we will visit the nodes using BFS. So just compare your uh answer uh with that if you're getting the same thing great. If you're not getting then in the next session just remind me I'll uh show you how to implement BFS uh using recursion and then you can then we can discuss uh the same example as well.

[01:29:33]Okay. So that's pretty much it for this session.

[01:29:41]If you have uh anything from your uh practice assignment or graded assignment and if you want to ask you can ask right now otherwise I'll just close the session.

[01:30:04]Oh, okay. Uh, thank you everyone for joining. I'll see you guys uh next.

[01:30:11]Thank you.

[01:30:13]>> Thank you. Bye.

[01:30:16][snorts]