CT Instructor Session

本站添加: 2026-04-29

[00:04:12]Hi everyone. Am I good?

[00:04:25]>> Am I audible? Can anyone confirm?

[00:04:28]>> Yes ma'am, you are audible.

[00:04:30]Okay.

[00:04:31]>> Good evening.

[00:04:32]>> Okay. So I think uh week 11 content has been discussed, right? The recussion and DFS part.

[00:04:40]So today we can uh solve the PA or if you want I can do a little recap of the theory part.

[00:04:52]Wait I'll share my screen.

[00:05:02]Hope my screen is visible.

[00:05:05]Yes.

[00:05:10]So this week 11 is going to be the last week for CT basically content wise. Week 12 is just a refresher week. So we will not have any content or assignments. So from next week uh actually this week onwards only we will start the interm revision sessions from Friday onwards.

[00:05:27]Okay.

[00:05:29]So let me just quickly recap this recursion and DFS part and then we'll solve the PA.

[00:05:37]So what we mean by recussion is uh recursion means when a function or a procedure calls itself right.

[00:05:45]So instead of writing that same code over and over instead of running a loop what we do is we call the whole function again inside itself. So a procedure calling itself is called a recursive call. So many computations are naturally defined inductively. Right? That is base case. So every recursive function will have a base case. Base case means when will the function stop calling itself, right? So it has to stop somewhere. It cannot infinitely keep calling the same function. So when it reaches that base case, it will stop. So when it reaches the base case, it will directly return the value. That depends on the problem statement whatever we are working with.

[00:06:23]And inductive step is what? Compute value in terms of smaller arguments.

[00:06:27]That means every recursive call the argument value actually reduces. So let's say if I started with 100 then it comes to 90 80 like this some at some point it will reach the base case which might be zero or anything whatever the problem divides right.

[00:06:45]So first uh good example of recussion is factorial problem. So in factorial what we know that if I say I want to find out five factorials. So this basically translates to 5 into 4 into 3 into 2 into 1. This is 5 factorial right?

[00:07:00]So like this I can find the factorial of any number. So it can be n factorial which means n into n minus 1 into n minus2. So like this I will go up to one. But see I will not go beyond one.

[00:07:11]Right? Because if I say into zero then this entire product becomes zero. So one is the base case. One is where I stop.

[00:07:19]Right? So 0 factorial is defined to be one. So factorial of zero is always one.

[00:07:25]This is given. Now for any n that is greater than zero factorial of n is n into factorial of n minus one. So factorial of five I can write it as 5 into this part which is nothing but factorial of four right.

[00:07:52]So we can also write a procedure for this. So let's call that procedure factorial. So here as argument I'm passing whatever number I want to find the factorial of. So let's call it n. So what is the base case? First you define the base case that I will stop counting the factorial for a number if the number is zero because then we directly have a value that factorial of 0 is equal to one. This is the base case or stopping condition. Right? So whenever n becomes zero you directly return one. else if n is greater than zero then you return n into factorial of n minus one right so this part is the recursive call so if I start with five if I want to find factorial of five so in the first call of the function the argument is five so is five equal equal to zero no so I'll come to the else part and this will be five into factorial of four right f of four so now my console my control will shift over here. Now this function call will execute. So now factorial of four this will return what?

[00:08:59]Four into factorial of three. Now again this is the function call. So we will now execute this call. This will return 3 into factorial of 2.

[00:09:10]Again control will shift here. This will return 2 into factorial of 1.

[00:09:18]And this will be my last call. Why?

[00:09:21]Because after this I will get return statement as 1 into factorial of 0. Now this is my base case. So in this function call the same code is getting executed right. So first if statement will check is 0= to0. So this is correct. So it'll directly return one here. So this return statement will return the value one. Where will it return to the previous function call that is to this one. So this will now become 2 into 1 that is two. This gets returned to the previous call that is this one. So this becomes 3 into 2 that is six. 6 gets returned to the previous call again. This becomes 4 into 6 that is 24. And finally 24 is returned back to the >> [clears throat] >> uh first call of the function. So here it becomes 5 into 24 that is 120.

[00:10:14]Right? So this is how recursive functions work. So first you call the function repetitively until you reach the base case. Once you reach base case, you again backtrack until you reach the previous uh first call of the function.

[00:10:29]Right? All the return statements will pile up.

[00:10:33]So you can also do this Fibonacci numbers using this uh recursive way.

[00:10:42]Okay. So recursive procedure factorial n is suspended till factorial n minus one returns a value. Factorial 5 is suspended until I get the value for factorial four. Then factorial 4 is suspended until I get the value for factorial 3 like this.

[00:11:00]Okay. So sum of numbers in a list. So if l is empty list sum is zero.

[00:11:06]Right? If there are no elements then sum will definitely be zero. Otherwise first what we will do is add first of L to sum of rest of L. That means if this is my L 1 2 3 4 5 then I'll say that I will I want to find sum of all these numbers. So what is first of L one plus I will do rest of L that is rest of this other numbers present right to the summation of this.

[00:11:37]So again from here you will do the same thing. I'll say from here I'll do two plus summation of rest of L again. So 3 4 5 then from here you'll get 3 + summation of rest of L that is 4 5 then from here it is 4 + summation of five and this last one will be 5 + summation of empty list and summation of empty list is zero. That's the base case. So this will become 5 + 0 5 that is returned to the previous call like this.

[00:12:14]Now 5 + 4 then 9 + 3 like this it will continue to do the sum.

[00:12:22]Okay. So this is the procedure how to find list sum using the recursive way.

[00:12:27]So procedure name is list sum which takes a parameter l that is the list.

[00:12:32]When list is empty then we can directly say that the summation will be zero because there are no elements. Otherwise the return statement is first of L plus list sum rest of L. That is what we saw that every time you're suspending the sum of the first element until the sum of the rest of the elements is calculated.

[00:12:49]Right? And later on you can just uh end this procedure and this return statement will return the actual sum.

[00:12:59]Okay. You can also do this in a different way. You can also do it using init function. That means we will first take the last element and then add it with the first four elements. Then the uh second last element add it with the first three elements. So just the opposite of that is also the same thing.

[00:13:15]Right?

[00:13:18]Now insertion sort procedure we also saw before this I think in week six or seven we saw. So you first build up a sorted prefix and extend the sorted prefix by inserting the next element in the correct position. So this means what?

[00:13:35]See this procedure first I have a sorted list which is empty. Now for each zed in L right insertion sort this is taking some L which is a list. Okay. So I'm saying that this list might be like this 3 2 1 4.

[00:13:53]Okay. This is L. Then first you have an empty list in which you will be storing the sorted list once it is sorted. Now for each Z and L. So what is the first Z thing? Sorted list becomes you again call the same procedure sorted list insert. So we have seen all the sorted list insert procedure. If you have forgotten just go back to that week and check out this procedure again. So you can basically every time you're inserting an element in a new list it should be inserted in its correct position.

[00:14:25]Right?

[00:14:27]So the prefix should always be sorted.

[00:14:29]like if I have entered three then before that I should already have one and two in the list okay so this is the whole uh function if you want I will just explain this one more time so sorted list insert does what it calls this insertion sort will call this procedial right so I'll again write the list I took 3 2 1 4 this is my unsorted list so now for each uh zed and l so first zed is three. Now you're calling sorted list insert with this sorted list which is an empty list and Z that is three.

[00:15:06]Right? So here this is empty list and three. So new list is what?

[00:15:14]What is new list? It is an empty list.

[00:15:17]Inserted is first set to false for each Z in L. Right?

[00:15:24]If not inserted that means when will not inserted give uh true. When inserted is false. So that's why we're starting with false. So not of false is true. But see here this for loop will not work because this list is already empty. There is nothing in this list. Right? So we'll directly come to this if statement. If not of inserted. So inserted was false. Not of inserted is true. So you can directly insert the first element inside the new list which is now three. That's the element I passed. So it is three.

[00:16:03]Right? Now return new list. So new list is returned. So now sorted list is nothing but this. Now again for the next element two again call this procedure.

[00:16:12]Now you're passing this list as argument and the next element. So this should come before three. Right? So now for each Z and L again inserted is false.

[00:16:21]New list is empty for each Z in. What is the only element present? Three. So Z is three. Not of inserted is true because inserted is false. If X is less than Z.

[00:16:34]So our current X is two. Current Z is three. So two less than three. This is correct. So in new list, I will first insert the current element and then set inserted inserted to true. So new list was empty. Now new list contains two and inserted is set to true. Right? Now you come out of this if blocks and new list plus zed that means the other element the zed that we're working with that is three that we passed as argument list element. Now that is added to new list.

[00:17:05]So new list becomes 2a 3. Now when you come outside here see no more elements are there in l right? There was only one element. So one time the for loop will iterate. Now in this if statement not of inserted inserted is true set to true here. So not of inserted is false. So two will not be added to the end of the list. So this is the sorted way in which the elements are being inserted. So that's what I'm saying that whenever you're inserting the next element, it should already have a sorted prefix.

[00:17:34]Right? So you can try the rest of the elements like this in this code. We have already seen this in previous weeks.

[00:17:42]So all of this uh code that you see in this week we have already done all this using for loops while loops but here we are doing it using recursive problems are same just we're using a different method.

[00:17:56]So insertion sort inductively list of length one or less is sorted right any element any list that contains only one element is always sorted or any empty list is also sorted but for longer lists we insert first of l into sorted rest of l that means if this is the list 2 3 2 1 4 right first of l is what three and rest of L is 214. So I'm saying that whenever I want to insert this first of L into this rest of L, this part should already be sorted. So this should be 1 2 4. So that three can find its correct position. So that's what I'm doing in that procedure.

[00:18:50]So see if length of L is less than equal to 1 then you directly return L because it is already sorted. If length is greater than one then there is the problem of whether the list is sorted or not. So what do you return? Sorted list insert insertion sort rest of L first of L that means now what I'm doing is inductive way. See it is also a recursive uh it is also a function call only here. Okay. So it is the recursive call previous one that we saw this one.

[00:19:26]Here I am calling inside insertion sort.

[00:19:29]I'm calling sorted list insert. This was the regular way that we saw before. Now this is the recursive way because insertion sort is calling insertion sort inside itself. Right? So what am I passing here? So again if I start with that same list 3 2 1 4 first of l is three and insertion sort on rest of l that is 214. So like this now.

[00:19:59]Excuse me. You are not Hello.

[00:21:23]Okay. Am I audible now?

[00:21:28]>> Yes.

[00:21:30]>> Okay. Sorry, I lost the connection.

[00:21:34]Yeah. So again in the return statement you will take the first of this and the rest of the list that is just containing four. That means every time I'm calling this insertion sort right it is having a list that that is containing one less element than the previous call. So after this see when I go to this function call where the list contains only one element. This is satisfying your base case. So this will directly return this list. Then you go back right you go back to the previous call from where this came. So now you have this one and this four right. So where should one come? It should come before four. So now you can insert it in the correct position.

[00:22:16]Again this will go back to the previous one. So like this every time see now two can be inserted in its correct position.

[00:22:23]1 2 4. Every time I'm breaking down the list it should come back as a sorted list.

[00:22:29]Right? So like this we can do a lot of examples throughout this last 10 weeks of content. Lot of codes that we have written using loops you can write using this.

[00:22:42]Okay. Now I think we should do some problems. Okay. Let me go through the DFS part also once since we're doing this.

[00:22:57]So DFS is what it is a graph traversal algorithm right. So there are two types of graph traversal algorithms that we mainly learn. One is breath first search and one is depth first search. Right? So here in our syllabus we only have DFS and also we don't have a lot of implementation of it. Why we are learning DFS is because it is a very good example of recursion. So depth for search.

[00:23:27]Let's take a very simple graph like this.

[00:23:36]I'm starting here. Traversal means what?

[00:23:39]I want to traverse through the entire graph. I want to see what all nodes are there. Right? So let me first start with node A. So who are the neighbors of node A, B and C? Now I can pick either path I want. Let me pick this path. So after a I got C. Now from C how many neighbors do I have? I have only one neighbor that is D. So I have to take this path. So now I have reached D. Now from D I don't have any more neighbors. So I will backtrack to C and check if C has any more neighbors. No. So I'll backtrack to A again and check if A has any more neighbors. Yes, A has one more neighbor that is B.

[00:24:17]So if we have this type of a traversal uh that we see all the nodes present in the graph after doing DFS we can say that the graph is connected right that means I can reach any node from any so depth first search does what it explores it doesn't explore one node completely right it goes to a node's neighbor then the neighbor of that node then the neighbor of that node until I reach a node who doesn't have any neighbors like some leaf node. Okay.

[00:24:50]So once I reach such a node that doesn't have any neighbors then I backtrack to the last traverse node. Okay. And I will check that if that node has any more neighbors. If it does then I will check that neighbor. So you will keep on backtracking until you find a node that has some neighbors. So how long will I do this process? As long as I can find all the nodes of my graph in this traversal, right? So that is depth first search. So we'll see the algorithm for this how we can use recursion here. So reachability in graphs means what are the vertices reachable from node I that is here in this example I can ask what are the vertices I can reach from node A. I can reach B C D all of these are reachable.

[00:25:31]So start from I and visit a neighbor G.

[00:25:35]Next suspend the exploration of I. That means I am not going to see who all are the neighbors of A anymore. I will pick one neighbor and I will go with with that neighbor and see that who are the neighbors of this this one now. Right?

[00:25:47]So I will suspend exploration of I and explore J instead.

[00:25:52]So continue till you reach a vertex with no unexplored neighbors. Then we will start to backtrack.

[00:26:00]So uh backtrack to the nearest suspended vertex. That means whose exploration I stopped because I found a neighbor and I started exploring that neighbor. So I'll now backtrack to that nearest suspended vertex that still has an unexplored neighbor. If you don't have any vertex with an unexplored neighbor that means your traversal is completed right. So best defined recursively maintain information about visited nodes in a dictionary called visited. So now we will have a dictionary structure in which there will be an entry for every node. Once I have visited that node, that node should be present in the visited dictionary. And we can recursively update this visited dictionary every time we explore an unvisited neighbor. That means after every recursive call, this visited dictionary should be updated and sent back to the last recursive call. Right?

[00:26:47]It should be in the return statement.

[00:26:51]So, uh to explore vertices reachable from I, initialize this visited dictionary which is empty at first. Now visited in this dictionary I am calling DFS procedure with this graph as a parameter visited dictionary as a parameter and the start vertx I as a parameter. Three parameters will be there. The graph itself the visited dictionary and the starting vertex. Now who are the keys of visited dictionary at any point? It is the set of nodes that can be reached from I because I is my starting point. So whichever nodes I can reach by starting from I all of them should be updated in this vis dictionary.

[00:27:32]So see this is the procedure.

[00:27:35]So procedure DFS takes graphs visited and I. Now visited of I is always true because I is the starting node. So I is already traversed right? So for that the entry of I in visited will be true. That means for every node in visited dictionary we either have a true or false entry. we won't have false because uh every time we visit a neighbor then only we enter it and then the value becomes true itself right so the keys are nothing but graph nodes so visited of the first node is always true because we are starting there now for J for each J in columns of graph okay that means that uh rows and columns of that matrix adjgency matrix of a graph it represents what the nodes itself and I know that uh adjgency matrix I J that value is equal to equal to 1 when there is an edge between I and J node I and node J right so if I find that for my starting vertex I there is some other node in the graph J such that graph of I J is equal to equal to 1 graph is nothing but an adjacy matrix so if I say graph of I is equal to equal to 1 that means I and J are connected by an H I can go from I to J so J is a neighbor of Right. And not of is king.

[00:29:03]Okay. Graph of i is equal to equal to 1.

[00:29:06]That means there is an edge between i to j. So I can go from i to node j. So these are neighbors. And not of is key visited j. That means j is not yet visited. J is an unexplored node. So visited dictionary doesn't have an entry for J. So you can insert J into visited right. So is key for an unexplored node in visited will have false value because it is not present in the dictionary. So not of false is true. So when both of these conditions are true that I have an edge from node I to node J that is J is a neighbor of I and J has not yet been explored then we are going to explore J next. So in visited dictionary we are now calling this DFS procedure again. This is the recursive call part.

[00:29:47]So now the control shifts here. Now this recursive call will work right. So see currently my visited dictionary has been updated or not in the next call visited of J will be set to true because now J became my starting point. Right? Like this how long we will do the recursive calls when I am at a point where there are no more unexplored neighbors. Then I will keep on backtracking. So at the last backtrack when I come back to this first call visited dictionary should have all the keys right that is all the nodes of the graph as its keys if the graph is connected that is all nodes are reachable from the starting node.

[00:30:28]So that is your depth first search procedure. Um see keys of visited include all nodes that means graph is connected. So you can see some examples here we'll do one or two. So if I start from this node let's say they're saying DFS of graph visited four. Okay.

[00:30:45]Initially visited is uh empty dictionary. So we are starting from node four. This is my start node. Okay. So node four is set to true. Now I have traversed node four. Now from node four how many neighbors do I have? I have 1, five and 8. So I decided to go to one first. So now next call will be dfs of graph visited one. So now one is the starting node. So one is set to true.

[00:31:08]From one where all can I go? I can go to two or I can go to three. So first I'll go to two. Okay. So now there is an entry for two as well. From two I can go to three.

[00:31:20]So now there is an entry for three. From three, can I go anywhere? No. Three is not connected to any other unexplored neighbors. It has neighbors one and two, but they're already explored. So I'll backtrack to the last node that I was exploring. That is two. Two also doesn't have any unexplored neighbors left. So I will go back to the last unexplored neighbor that is uh last neighbor we were exploring that is one. Now does one have any more unexplored neighbors? No.

[00:31:45]So I will go back to four again. So now from four do I have any more unexplored neighbors? I have five and eight. So now I decide to explore five. So next entry will be five true.

[00:31:57]From five I have six and seven two edges. So I decide to go to six. So now there is an entry for six.

[00:32:05]From six I can go to seven.

[00:32:08]So seven true. From seven can I go anywhere that is not explored? No. So let me go back to six. From six can I go to any other unexplored neighbors? 8 and 9 I have. So I'll go to eight first. So now there is an entry for eight. From eight I can directly go to 9.

[00:32:25]So there is an entry for 9. And from 9 I can go to 10 finally. So there is an entry for 10 also. Now from 10 there are no more unexplored neighbors. Now when I backtrack to 9 again, no unexplored neighbors. Backtrack to eight, no no neighbors left. Same backtrack to six, backtrack to five, backtrack to four. So now at the end of this recursive coil, now I have reached the base condition that is there are no unexplored neighbors left for any of the nodes. Right? So this is a complete BFS DFS traversal.

[00:32:58]So like this you can explore some other examples that are also given. Uh I think this is the same example. So they are traversing. You can do it in many different ways. The DFS traversal doesn't have to follow a unique path. So here I can start from four and I can go to one then two then three or I can decide that I want to explore five first. So I can also go to four to five then six and then later on I explore this one two three path. So many DFS traversal paths can be there.

[00:33:31]Okay. So these are the two main topics for this week. So let me now switch to the assignment. These problems should be very simple for you because we have already practiced all of this. So the only difference is that this time we are going to impose recurs recursion concept over here. Right?

[00:33:50]So see the first question it is saying unique is a procedure that accepts one second.

[00:33:59]Unique is a procedure that accepts a list L as input. It returns the unique elements in the list after removing the duplicates.

[00:34:08]Right? So unique is the procedure name.

[00:34:11]It accepts any list L as input and it returns the unique elements in the list after removing the duplicate. So you have to select the correct code fragment to complete the pseudo code.

[00:34:22]See what all we have given here is procedure unique taking L as argument.

[00:34:27]init elements is an empty list. If length of L is less than equal to one, then you directly return L because if there is only one element or less than one, there is no elements, then there is no chance of getting a duplicate, right?

[00:34:41]So in that case you directly return L.

[00:34:44]If you have more than one elements then in init elements you're taking init of L. And then in this part something is happening which you have to find out from the options.

[00:34:54]So check the first option. Okay, let's take an example list like this. So, uh 3 2 1 2 If this is my list, so length is four.

[00:35:06]Len of L is four. So, the first condition doesn't work. Init element says now init of L which is in it means last element gone. So, 3 2 1.

[00:35:21]Now if I work with the first option, it is checking if member init elements last of L. So is the last of L already a member of init elements.

[00:35:32]Who is last of L? Two.

[00:35:36]See I haven't changed L itself. I have just taken the init of L inside this init elements list. That's it. L is still this original list. So last of L is two, right? Is it a member of init elements? Yes, two is present here also.

[00:35:50]That means what? This if statement will evaluate to true.

[00:35:56]So now you can enter the if block and return unique of init elements. So again this procedure is recursively calling itself. So now next call what is the list you are passing 3 to 1.

[00:36:12]Again do the same check. What is the length of this list? Three. So the first if statement doesn't work in init elements. Now you take init of this cell. So you remove the last element. So you have 3, 2.

[00:36:29]Now again check is the last of L member of init elements. Last of L is one. It is not a member of this. Right? That means it's a unique element. So you go to else part and return unique init elements. that is call the function again plus plus last of n. So I'll write the return statement. This is the first recursive call.

[00:36:52]So again you call unique procedure in uh init elements is 3, 2 plus plus last of l which is 1.

[00:37:03]Right?

[00:37:05]But we will not add one yet because we first have to execute this part. This is where the control shifts to the next call. So now second recursive call unique of 32.

[00:37:20]Okay. Again check what is the length of L. It is two. So first if statement fails. We will not return L. Init elements now contains what? Innate of L.

[00:37:31]That means last element gone. So now it has three.

[00:37:36]Now check what is the last of L? two is two already a member of this init elements no so again we'll go to the else part and return statement will be unique of three plus 2 now control shifts to this call unique of three this is the third recursive Okay. So what happens here? Now you again check what is the length of this.

[00:38:14]Length of L is now one. There is only one element. So now this if statement is true. Length of list is less than equal to one. So you can directly return this.

[00:38:22]So what will I return? I will return three. It returns three. Where does it return three? To the previous call. So now you can do 3 + 2.

[00:38:34]So list becomes 3A 2. This is returned to the call before this that is the first recursive column.

[00:38:44]So this becomes 3A 2 + 1 that is 3a 2a 1.

[00:38:55]Right?

[00:38:59]So that's all you have to do. So now you have this list which doesn't have the duplicate the last two that is discarded in this first call right because here we only do unique uh return unique elements. We don't add the last element again because that's a duplicate.

[00:39:17]So this 3a 2a 1 is the final answer. So this option has to be correct. This is might be an msq. So let's check the other options also here. What is is it correct? So what is the change in the code? Init elements last of return init elements. So it is not calling the unique procedure at all. Right? So what are you doing differently? You are just adding to that same list init elements.

[00:39:42]This is not going to work because this is no procedure call. This is just the list you are returning. It will not remove any of the duplicates. The unique call is not there. So this is clearly wrong.

[00:39:54]Here also what happens if it is already a member then you are directly returning in elements not calling the unique procedure. So here the unique call is missing.

[00:40:05]This one is it correct?

[00:40:11]See what is different between this one and the first one. If member init elements last of return unique init elements. So here in the last one member in elements last of return unique init elements. Up to this everything is same.

[00:40:25]Else part return unique elements plus+ last of it.

[00:40:32]This looks very similar.

[00:40:35]Oh okay. So here the last of L is put inside a list right. So last of L is just going to fetch the element. See I have written the element in a list. Right? The last of L should be in a list like this. So this option actually is wrong because it is not given in brackets. So you cannot just add an element, right? You cannot extract a single element and add it to a list. So it has to be enclosed within box brackets. So that's a very subtle error. I even missed it here. So this option becomes wrong because of this simple box bracket. So option D should be correct.

[00:41:13]The only Yeah. See this is the recursive steps.

[00:41:18]So I'm starting out with this list. Then the next call. So this one is extracted five. Is five present in this list? No.

[00:41:26]So I will add five later. I'll work with this part. So next you extract this three. Is three present in the rest of the list? Yes. So I will not add three back. I will again call unique on this part. Again extract the last element. Is one present in 1, three? Yes. So I will not add one back. Again unique in this part. take the last element that is three. Is three present in one? No. So now I will just add one, three and five and get the final list. But we must have this inside box brackets otherwise we cannot append the element. Right?

[00:42:01]So the option D is the correct option.

[00:42:04]Option A and D are very similar. It's just this very subtle thing.

[00:42:10]Anyone has a doubt here in this code.

[00:42:17]Okay.

[00:42:20]So question two is saying a word is said to be a palenrome if the word is obtained by reversing it. If the word obtained by reversing it is the same as the original word. Example madam is a palenrome. So you can read madam from left to right or from right to left. It will give the same word. So let X be a row in words table. At the end of the following pseudo code flag stores true if the word in row X is a palendrome. So X is a row in the words table. Every row in words table contains a word. Right?

[00:42:52]So at the end of the following pseudo code flag is a variable that stores true if the current word in row X is a palendrome and false otherwise. So you have to select the correct implementation of the procedure is palendrome. It is an MSQ.

[00:43:07]Okay. So we have to basically find out which is the correct implementation of this is palendrome procedure and there might be more than one answers.

[00:43:15]So we just have to check that is it checking the palendrome conditions correctly. Right. So first I have this word list which is empty and flag which is false set to false. So word list is explode x.word. What does explode procedure do? This will be mentioned in the question. Normally explode just excludes the words of a uh the letters of a word. So if I have the word as madam this is the x word. So in x after x dot word is exploded it will give us a list of all the different characters in this word. So it will look like this.

[00:43:50]So this is your word list.

[00:43:53]Now flag is is palendrome of word list.

[00:43:56]So after this procedure is executed, flag should either be true or false depending on whether this is a palendrome or not. So for this example, flag should be true. So now you have to fill in the code for this is palendrome procedure.

[00:44:09]So basically this is palendrome should return what some boolean value true or false. Right? So first option is saying is palendrome of L. So let's take L as our exploded word. Madam this one length of L is less than equal to one. No length of L is five.

[00:44:29]So this is the base call for base call length of L is five. So first if statement is wrong. First of L is not equal to last of L. No they are equal. So second if statement also is wrong. Else. So now you have to come here. Return is paling room in it rest of L. That means I will remove these two elements and work on the rest of the list.

[00:44:54]So now the first recursive call here the return statement is in base call it is is P. I'm writing this as P. This is taking init rest of L. So rest of L will remove last element. Then in it will uh rest of L will remove first element.

[00:45:09]Then init will remove last element. So now we are basically dealing with this list. A D A right. So now this part is where the control shifts. So this is the first recursive call and the second call of this function overall.

[00:45:27]Okay. So now my list is a comma d comma a. What is the length of l? It is three.

[00:45:34]So first if statement is wrong. First of l not equals to last of l. No they are same. So again you go to the cells part and the return statement now is going to again call this procedure is spelling wrong with init rest of l. So again this and this are removed. So now we are working with just D.

[00:45:54]Now the control shifts to this call which is the second recursive call and third call overall the list is D. What is the length of this list? One. So first if statement is true. Now length of list less than equal to one. So you directly return true. So here the return statement will return true.

[00:46:19]Okay.

[00:46:21]So finally once this returns true but is it returning this true? Is it returning true to the directly to the function or is it returning this back to the last call?

[00:46:38]Just a second.

[00:46:54]Can you see my screen?

[00:47:01]>> Wait, now it is visible, right?

[00:47:09]>> Yes. Yes.

[00:47:12]Okay. So once this return true happens, this will go back to this base call. So the entire result for this is the logic is all correct. So this procedure is working correctly. So this is one of the answers. I don't know if there are more correct options, right?

[00:47:33]Because see basically this goes back to this call. So this is also returned true. Again this is also returned true.

[00:47:39]So like this you will reach the base call which is giving flag will be set to true. This is the first call of the function.

[00:47:50]Second one also let us check what is wrong here. So uh there are some palindrome words which are also can be even number letters right like noon. No noon is such a pendromeum which has even letters even number of letters. So here if I start see length of L is L is what the exploded list that is L O O L N L.

[00:48:14]So length is four. Okay. Length is equal to equal to 1. No. So then this one first of L is equal to equal to last of L. Correct. This is correct.

[00:48:25]So I'm calling this as the first call.

[00:48:27]Okay. So is wrong. Now return statement is calling the procedure again. first and last are removed. So now I'm working with double O.

[00:48:41]Okay. Now control shifts to this call.

[00:48:44]Second call.

[00:48:46]Now my list is O, O. Length of list again first if statement doesn't work.

[00:48:54]Second one first of L is equal to equal to last of L. Correct? So again you are returning what? Now init rest of L will remove both of these elements.

[00:49:05]So you are basically calling the procedure with an empty list now. So when the control shifts to here and the third recursive call is there. Now the length of your list is zero. There is no condition to handle that situation. So the base case should not be equal to equal to one. It should be less than equal to one because paren can be odd or even number words. Right?

[00:49:28]So this is wrong.

[00:49:32]Third one base case is true. I can see uh here see first of l is equal to equal to last of l. So again uh let's check with our previous example noom.

[00:49:46]Okay. So uh length for the first call is four.

[00:49:51]First if statement doesn't work. Second one works. So here the return statement is now a spell in room of in of rest of l that is o.

[00:50:02]Now control shift to second call we are working with O this list length is two. So first if statement doesn't work again. Next if statement first of is equal to equal to last of correct return is P of init rest will remove both the elements. So we will have an empty list.

[00:50:25]Now control shifts here. Now you have empty list. That means length of L is zero. So 0 can be handled in the first if statement less than equal to one. So you can directly return true. So this is correct.

[00:50:41]Last one. Can you tell me anything that is wrong here? You can see see here I am directly returning true.

[00:50:52]Right? But there are plenty of words which have the same first and last word.

[00:50:56]Right? But the middle words might not be the same in the ordering.

[00:51:03]So what can be such a word? Tell me with the same first and last letters. So I'll just take some arbitrary uh string maybe.

[00:51:21]Let's take this string.

[00:51:25]So in this string here first the length will be four right. So which is less uh not less than equal to one. So nothing happens here. Now the next one first of L last of L. A and B uh A and A these two are equal. So I'm directly returning true without checking further. But this is not a valid wrong right? Because B and C are there. If it was B or C then it would be a valid wrong but without checking that you're directly returning true. So this is wrong.

[00:51:54]E and C are correct.

[00:51:57]So anyone has a doubt here.

[00:52:03]See we have already done all this logic.

[00:52:05]It is just checking the recussion procedure. That's it.

[00:52:10]Okay. So consider the following pseudo code. Assume that a and b are two positive integers. So procedure calculate a comma b. Difference is set to zero.

[00:52:21]We'll just do a rough run of this procedure and see what it's doing and then we will go to the questions. Okay, this is the common question for 3 to seven questions.

[00:52:30]So first we check that if a is less than b then you return calculate b comma a.

[00:52:38]Okay, next if you check that means uh here now you will call so let's say whatever is the number. Okay, we'll see that in the question. Whatever is a, whatever is b, you will just reverse it and then call the same procedure but with the reversed order of arguments. If a is equal equal to b, directly return b. So if they're equal, you can also return a, right? A or b both are same.

[00:53:03]Difference is a variable which is set here. So that means if this if statement does not work or this does not work, that means a is greater than b. In that case you in difference you store a minus b. See the other two possibilities are taken care of here. A is less than B or A is equal to B then either of these return statements will work. But if A is greater than B then you first calculate the difference. What is A minus B. If difference is greater than B then return calculate difference comma B. Else return calculate B comma difference.

[00:53:37]So this is the procedure. Now what is the question asking what is the return value of calculate 12A 3.

[00:53:46]So let us run it here. So calculate 12A 3. First difference is set to zero.

[00:53:57]A less than b no.

[00:54:01]A equal to equal to b also no. So now I have to calculate the difference. So difference is a minus b that is 12 - 3 that is 9.

[00:54:13]Now next if statement checks is 9 greater than three. Correct? So return statement is call the procedure recursively. This is the base call.

[00:54:26]This is the first recursive call. So difference is 9. B is three. So 9a 3. Now move to this call is the first recursive call.

[00:54:37]So calculate of 9, 3.

[00:54:41]First if statement is wrong because a is not less than b. Second is also wrong.

[00:54:46]So again calculate the difference. So difference is 9 - 3 that is six.

[00:54:53]Is 6 greater than current B that is three? Yes. So again return statement becomes what?

[00:55:00]Call the procedure recursively. Again difference is 6, B is 3.

[00:55:07]This is the second recursive call.

[00:55:10]So calculate 6, 3. Again first two if statements will fail. Difference is now set to 6 - 3 that is 3.

[00:55:24]Now you check is difference greater than B? 3 is greater than three. No. So go to the else part and return statement in else part is again recursively call this procedure P is three difference is three.

[00:55:38]So now this is the third call third recursive call. So calculate 3. First if statement will not work but the second one will work. A is equal to B. So directly you return what?

[00:55:55]B itself.

[00:55:57]Right. So three is returned for the first question. So which option is correct? Option C.

[00:56:05]Can you tell me what is this actually implementing? This procedure is implementing something which we all know.

[00:56:14]Okay, let's do one more maybe then you can figure out let's take 14 and 17.

[00:56:23]Okay. So I will just quickly do it here.

[00:56:26]So calculate 14, 17.

[00:56:30]So A is less than B. This is correct, right? A is 14, B is 17. So return statement, this is base call.

[00:56:41]Return statement is calculate of B, comma, A that is return calculate of 17, 14.

[00:56:53]Now first recursive call.

[00:56:56]So this does what? Calculate of 17, 14.

[00:57:03]Uh this so first if statement fails. A not less than b. A not equals to equals to b. So now we calculate the difference which is a minus b that is 17 - 14 that is 3.

[00:57:18]Right? Now is difference greater than b?

[00:57:22]Is three greater than 14? No. So go to the else part. In else part return statement gives calculate of B comma difference. B is 14. Difference is three.

[00:57:33]Second recursive call.

[00:57:36]Calculate of 14, 3. Again first if statement fails. Second if statement fails. Calculate the difference. 14 - 3 that is 11.

[00:57:52]Is 11 greater than three?

[00:57:56]Uh wait I think yeah so is 11 greater than three? Yes.

[00:58:03]So calculate again call this procedure that is calculate of difference comma b.

[00:58:08]So 11a 3.

[00:58:12]Third recursive call. I'll just write the return statement now. Okay. So let's check uh is a less than b no. A equals to B. No difference is 11 - 3 which is 8. So 8 is greater than 3. So return statement will be calculate difference which is 8, 3.

[00:58:34]Now for this fourth recursive call.

[00:58:38]Again check 8 less than 3. No 8= to 3.

[00:58:42]No difference 8 - 3 which is 5. So 5 is greater than 3. Yes. So again return statement gives calculate of difference comma b that is 5a 3.

[00:58:56]Okay fifth recursive call.

[00:59:00]So 5 less than 3. No 5 = to 3 again no 5 - 3 is 2. Now the difference is 2. So 2 is greater than three. No. So come to the else part. So it becomes b comma difference. That means 3a 2. So return calculate of 3,2 I don't have space to write. Okay. So six recursive call here.

[00:59:27]Again a less than b 3 less than 2. No. 3 equals to 2. No. Difference is 1. 3 - 2.

[00:59:34]So difference 1 is greater than 2. No.

[00:59:37]So come to the else part. Return statement is calculate of what is B? Two. What is difference? One.

[00:59:51]7th call.

[00:59:53]So 2 is less than 1. No. 2 is equal to 1. Again no difference is 2 - 1 that is 1. Okay. So 1 is greater than 1. No.

[01:00:02]Come to the else part. So return statement is calculate of B comma difference which is 1 comma 1.

[01:00:12]So now in the next 8th recursive call this part will evaluate to true. A is equal to equal to B. So you will return B that is 1. So for 14 and 17 this is yielding the value one means there are no common factors between 14 and 17. So this is basically finding the HCF right or the GCD greatest common denominator.

[01:00:36]See for 12 and 3 the GCD is three itself. For 14 and 17 one is the greatest common denominator between these two. Right? Only one can divide both 14 and 17. Nothing else. So on if you figured this out you don't have to do it recursively.

[01:00:53]So here B this is the answer. So this one see how many times is the procedure calculate called in order to compute 14A 17. This we just saw nine times. Nine times why because one for the base call this one and eight other recursive calls. See from here also one recursive call eight is done right where this will return this return B that is one. So eight recursive calls one base call. So how many times calculate procedure is called? total of nine times right don't just calculate the recursive calls take the base call also so yeah any doubt in these uh three four questions three questions till now see question six again based on that same value okay for any two same comprehension type so for any two positive inteious a and b what does calculate a comma b return it returns the hcf of the two numbers right see why not this option because provided a greater than b is not required wherever I'm seeing a is less than b I am reversing the arguments I'm making b as a and a as b see here this part is just for that the first if statement that if a is less than b call the same procedure with b as a and a as d so that we always make sure that the First argument is the greater one so that the difference never goes to negative.

[01:02:29]Okay. So option B is correct here.

[01:02:33]Again this is the same comprehension.

[01:02:34]Last question. What is the result of the following expression? Assume that A and B are two positive integers. So calculate a comma b is equal to equal to calculate b comma a.

[01:02:45]These two will return the same value.

[01:02:47]Right? Because I am reversing it anyways if b is less than a.

[01:02:53]So both of this procedure will return what the HCF of A and B. HCF of the two numbers. So when I compare these two it will give true value.

[01:03:04]So option A is correct.

[01:03:08]So these are the questions from week 11 PA. Now you can easily solve the graded assignment. It is pretty simple.

[01:03:16]Okay. So from the Friday class onwards we will start our endm revision because our endm is nearby after next week. So we'll have around two to three classes for endm revision that is uh this Friday Saturday and the next Monday and after that we won't have any more sessions till your uh endm but if you want any extra sessions in that week also we can conduct if you have doubts or anything.

[01:03:45]Okay.

[01:03:48]Okay. Thank you everyone. Thanks for joining.

[01:03:52]Thank you.

[01:03:53]>> Thank you.