PDSA Week-5 Open Session Part-2 Jan-2024

 

>> PDSA POD: Hello. Hi, good evening. yummy edible Hello. >> PRADEEP KUMAR: That’s a Audible. >> PDSA POD: Okay, so let me wait for a couple of minutes and we start. I hope my screen is visible. Hello. I am in the call. >> Md. Alauddin Ansari: They will. >> PDSA POD: Oh, >> BHANU PRATAP SINGH BAIS: Press it. So could you please mention this YouTube? Url that actually I am. >> PDSA POD: calendar >> BHANU PRATAP SINGH BAIS: Yes in the challenge, but I am different Plus. And it is not. >> PDSA POD: Wait, wait No. >> BHANU PRATAP SINGH BAIS: Yes lost. >> PDSA POD: actually >> BHANU PRATAP SINGH BAIS: This one this one which recording.

 

>> PDSA POD: This is this is the extra session actually session number two. way to Munda white tilling currently link I added. Wait a minute. Where can I add it? This is sweet Oh, I cannot add it what? instrument how to add it is I’ll see that Can add it directly? I cannot add it I think so wait because I am not the admin for this dashboard. Maybe that could be the reason. >> Md. Alauddin Ansari: Oh life access name in Tiger one. >> PDSA POD: Wait previous session. Last Friday session is it added last Friday session? Let me check. Last Friday decisions on this one. Meeting link was there. >> Md. Alauddin Ansari: through YouTube >> PDSA POD: By link is there already this one in? >> BHANU PRATAP SINGH BAIS: yes previously was there but >> PDSA POD: Today’s link not today’s link. >> BHANU PRATAP SINGH BAIS: yes. >> PDSA POD: Today’s link. Actually, I am not the maybe I’m not Deadman. Maybe I’m not having possible dial.

 

I’ll report to my course lead. So that he’ll add it today’s link of it again. I’ll try it. Maybe the students. >> BHANU PRATAP SINGH BAIS: I’m living for now because the class. >> PDSA POD: Yes. Yes, so >> BHANU PRATAP SINGH BAIS: Hey. >> PDSA POD: I I’ll ask him regarding adding of this vitalink of today’s Sure, I’ll report to the course later. >> BHANU PRATAP SINGH BAIS: Thank you. >> PDSA POD: Okay. hmm >> AMITABHA BHATTACHARYYA: so one request for that can the sixth the deadline can be extremely extended to the weight instead. because it is a too much tough to do the 5th and 650 itself is a big one. >> PDSA POD: Mmm, actually, what I’ll do is today I try to discuss grpa at least how to do for fifth week.

 

Today, I’ll discuss you. not a problem. Grpa. I’ll discuss how to do it, but I’m not disclosing actual code what exactly it is. I’ll give you central idea how to do it clear. >> AMITABHA BHATTACHARYYA: Yeah, so >> PDSA POD: so you through to three gr. P s I’ll try to make you to explain today and regarding the sixth week extension. I just know down after this class immediately. I’ll ping to course lead regarding 6. Actually, what is the week 6 submission date? >> AMITABHA BHATTACHARYYA: this Sunday only. >> PDSA POD: Oh Sunday. Actually, the fifth week is third. No third March. >> AMITABHA BHATTACHARYYA: Yes. >> PDSA POD: mmm, Sunday >> AMITABHA BHATTACHARYYA: so making the intermediate is okay for us because at least we get some time to understand because I feel that it’s a pretty >> PDSA POD: hmm >> AMITABHA BHATTACHARYYA: hi everyone.

 

The first topics are discussed. It’s almost all the algorithm is disgusted. >> PDSA POD: Yes Yes actually fifty week is somewhat complex it one and it has a lot of things to discuss and at the same time some of one more week is there like I think divide and conquer also, I think it takes some time So I’ll ask him regarding this extension actually this date of the sixth week. I’ll ask for extension. Definitely, I’ll post after this class. >> AMITABHA BHATTACHARYYA: If okay. Thank you. >> KARTHIKEYAN S: He will only discuss. >> PDSA POD: No, no, I’ll discuss concept for stately pending to algorithms are there mcst? Minimum cost spanning spanning trees have to finish up the algorithms then I’ll discuss that grp how to solve it.

 

>> KARTHIKEYAN S: Okay. I have some doubt in PPE also, maybe >> Md. Alauddin Ansari: Okay. >> KARTHIKEYAN S: I’ll try to take it at >> PDSA POD: Okay. >> KARTHIKEYAN S: the end of the session >> PDSA POD: Okay first let me finish up the >> KARTHIKEYAN S: yeah. >> PDSA POD: algorithms 2 algorithms are pending, No. Okay. Yeah. Okay. peace. So if you consider that last sessions which have been worked all the algorithms are graph algorithms only. So we have stopped it. Three algorithms so far we have finished it. The first two have algorithms are single Source shortest paths. >> KARTHIKEYAN S: the pressure of at least if not the physics the first one this is the second one. you can just just press through before going to next. quickly >> Md. Alauddin Ansari: of >> G HAMSINI: part of >> Md.

 

Alauddin Ansari: not Audible >> PDSA POD: Hello, >> G HAMSINI: Is not going place. >> PDSA POD: cool >> Md. Alauddin Ansari: Oh, yeah now. >> G HAMSINI: Oh, >> PDSA POD: Maybe somebody might problem. Yeah. See look at I think I’m in the call. No. >> Md. Alauddin Ansari: Oh. >> PDSA POD: Okay. Okay. So here we have the two kinds of representations. Is there for the Digital Data representation of the graph? Like earlier in the fourth week. We have seen that graph without weights or we can say the cost. Alright, we can say that, you know distance we can say three two one. There is a distance weight is called three one to two there is a distance weight of this one something like like that. So prithvi converts what we have as we have the graphs with respect to weights or cost or we can say the distance is there. So how to represent this one is this can be considered as a u this can be represented as V like this can be represented as you these things can be represented as you.

 

These things can be represented as V. Of course zero, also we so U2 we how it is connected is If there is a path exists we try to represent a binary data 1 along with what weight is associated to it. For example, from 0 to 1 there is a weight is associated tree. Similar way so we have that one to two you might have that has been that weight. is there so one to two is there there is a weight is there we try to represent that there is a path existed.

 

One and what is the weight of it? It’s 1. So 1 and 0 represents that on and offer first, you know Tuple is having two wireless zero. Evalu is called as you know on and off whether that they’re connected or or not direct ages connected or not. and beside that another couple values their second pair of value second value is that that is the weight it represents that so if it is list, it is somewhat compact format, you know, you don’t have that rows and columns simply we are having. A dictionary, you know, this is called, you know one dictionary. this dictionary contains that 08 Ki first key And the second key and so on. These are all keys. Each key is associated with a list of tuples like Vertex is connected to one with the weight of 3 0 8 vertex connected to 3 with weight of 7 see look at.

 

08 vertex is connected to 7. with weight of 7 so that is what you know, it is a compact format the complete dictionary ended here so that we can say that you know dictionary inside that the nested lists are created. That’s what simple representation. So once Digital Data is ready like you know, whatever you have been inputting. That has to be converted into either a decentralist or adjacency Matrix. Then we try to process different graph algorithms. The first graph algorithm. Is that dextas algorithm? This does algorithm is very simple. We fix that one source. and from that Source we try to find out that distance to all other Witnesses.

 

Which is that shortest distance shortest distance in the sense. It’s not in terms of number of edges. It’s in terms of that. total cost to reach from Essa whereas is fixed it is a fixed one. and S2 all other you know, like, you know as to one s22 let you consider SC is considered here right now 0 you can consider any of them. So as to 6 that is 0 to 60 right now, it is considered as 0 is that starting, you know source with ethics or we can say that, you know our reason what you call this is fixed entire algorithm. It is fixed. 0 to 4 how much distance is there 0 to 2. How much cost is there 0 to 1 I can say the distance caused weight is same all these three things. We are calling its synonyms how much distance was taken to reach from s25? Maybe it is a directage is there or indirect age is there but we want want that minimum distance? So in that way if you find out it. 0 to 0 we don’t have that any kind of self iteration or we can say that self Loop.

 

Zero to one we have that no distance or we can say that cause or weight is called 10 how it is 0 to 110 is that it’s a direct Edge is there. there is no other way of connecting to 0 to 1 which is a minimum one. But whenever you come to here, so please look at here at this place. Earlier 0 to 2. It is 80 is there. when you go for the second iteration it’s going to 16 how it is 80 gone to 16 is very simple. So 0 to 2 is a direct it is it is 80. But there is a indirect path. Is there during the second iteration what you do us 0 to 1. It’s a 10. And want to two it is a 6 so that existing 80 and recent value 16. It is a better value so that we update that 16. So that’s the reason during the second iteration. We got it is a 16 the best value. So what were the basic formula is this one? distance of this existing you plus this weight. So for example from 0 to 2 you want to calculate it’s very simple existing zero plus weight of this 80.

 

If these two some is so less than so a less than that existing distance, you know, whatever the weight distance 0 plus this this particular 80 So initially we put it that infinite all of them are initialized with infinite. Immediately what happens, you know 80 is a smaller value than infinite immediately 8 is replaced whenever second iteration you are doing what happens, you know, this distance is calculated from one. There are two agents are there. if from the one if you calculate 10 plus this weight.

 

This is a 10. This is a 10. And this weight is 6. It is 16 existing already weight is 80. So that 16 is better value. So that here at this place 60 is replaced. So this way it is trying to pull out that. the shortest distance from a single source to all other vertices that is called dikshas, but the problem with the discuss algorithm is It doesn’t work for negative weights See you. Don’t find that any kind of value in the negative. All of them are positive only we cannot give the negative cast there. So that’s the reason we are going for another algorithm. That’s called Belmont order. This is the Belmont Ford. The Belmont Ford what it will dose. It will allow you. The negative weights see look at minus 4 minus 1 minus 2 minus 1 negative weights are allowed.

 

But what happens, you know the negative Cycles are reported. Whenever negative cycle is there it will report it. How can you say it’s a negative cycle is very simple. See look at from 1 to 5 5 to 2 and 2 to 1 there is no negative cycle very simple. One and this so 2 to 1 let you consider that 2 is a single Source short test let you take this part only this one to five as a simple graph. I don’t want to consider a big graph one to five. If you consider one is the source. You Travers from one to five distance of two. Again, five to two it’s a minus 2. It will become 0 again 0 plus 1 it will become 1. So no problem. You are getting a result is 1 But whenever you have a negative cycle, let me consider instead of this minus 2 you consider this one a minus 4 value something, you know bigger value.

 

What happens you know to and this minus 4 it will become minus 2 minus 2 will become this minus 1 it will become minus 1 again minus 1 what happens, you know minus 1 again this one. you know what happens this plus 2 it will become it is 1 again 1 so 1 and this minus 2, it will become so it never ends. It’s keep on repeating the process. And it doesn’t stabilize the values. So what the thing the difference between this you know the dextrous algorithm at Belmont Ford is this Edge relaxing we do this part. is there. No, this is called one time. It’s relaxing we do that. For 08 vertex. We do one one time relaxing. First first vertex. We do that one time relaxing second vertex. We do that one time relaxing where we use that greedy method. We do the greedy method when you go for this Balman Ford, what it will do is again it will repeat this particular cycle is one first cycle.

 

These values are used in the second cycle. So that existing values are used for the next one. So it’s called dynamic programming dynamic programming is you know. choosing a vested decision from a group of decisions. So after the fourth iteration, please look at this is what the fourth iteration. The values are stabilized. So you don’t have change even you go for sixth iteration you go for seventh iteration. No value such changed. So how many iterations are how many edged relaxing so you have to do for have 5 vertices is there you supposed to do 5 minus 1 that is called. 4 Edge times relaxing so that’s the reason if you could look at that, you know the Bellman Ford. So you can find that extreme outer loop. Is there please look at this one? Yeah. So this is what age relaxing. Extreme outer loop is available.

 

Of course. They are running up to Rose number of times. Even you do the rose minus one. Also, not a problem. So that inside this particular one, This is called exclusively Outer loop that it will do every time the past values are still used and new values are calculated. but formula is same see look at it’s relaxing formalizing no change. So the existing distance of the U plus the cost is addition if it is less than that the already existing in the v. So we’ll update the V with new calculated value. That is called, you know minimum updating. So this is it works for Negative Edge weights and it will detect that negative cycle how it will detect is if the values are stabilized. after n minus 1 iterations, actually if 7 or vertices is there after 6th iteration it is fixed if you run one more iteration if there is a change between the sixth value and seventh iteration values definitely this is containing, you know negative Cycles so that you can easily detect that negative Cycles by using Bellman Ford.

 

And if you go for yeah, this is one pretty example, which I discussed earlier. This is what you know Bellman Ford, It will detect the negative Cycles. See if this is started from 0. It goes to 1 so then 1 to 2. It will become minus 3 2 is so this will become 1. This will become it is minus 3. So after this from minus 3 it is going to plus 2 it will become minus 1. Again, it will repeat. So what happens, you know, so minus 1 and this plus 1.

 

So this 0 0 is a lower value comparatively one so that this is gone. This value is gone. Again, 0 minus 4 so you get minus 4 minus 4 is a smaller value than minus 3. So what happens this is updated. Again minus 4 we get minus. so minus 4 and 2 it will become minus 2 minus 2 is a better value. So keep on updating it never stop after three Cycles after four cycle it never stopped. So this can be detected after three iterations. You try for another, you know, another relaxing. Between third its relaxing and 4th generation values are different then you can report sorry this particular, you know algorithm for this particular graph it contains that negative Cycles you can report like, you know, you can say yes or no whether it is containing negative Cycles or not. >> Saurav Kumar: A nectar different means that it is increasing negatively like from >> PDSA POD: Yes, negatively.

 

It is increasing. definitely negatively. See minus 1 is going to minus 2 minus 2 is going to minus 3 if you run one more time, it goes to minus 4 keep on increasing. >> Saurav Kumar: okay, and so >> PDSA POD: That’s what you know, you can. >> Saurav Kumar: that you know chance of becoming positive like >> PDSA POD: Yes. yes no chance of becoming positive and there is no values are stabilized.

 

It never stabilized, okay? After you know n minus 1 values if you want to check the negative cycle one more time. you run it compare the previous distance and existing distance if any change you report sorry this graph contains, you know negative Cycles. Now all pairs shortest, this is what exactly you know. combination of earlier algorithms you learned see here always source is fixed Always One Source you fix that 0 is a source.

 

We try to find out zero to one zero 2 2 0 2 3 which is the minimum shortest path, but this is what you know all pair shortest. You try to find out zero to all other waitresses one to all other Witnesses two to all other Witnesses three to all other Witnesses here also dynamic programming only we are using dynamic programming but here interesting thing is we are trying to use every time the version of updating see look at here. Initially we take that a graph which is that having that, you know rows and columns. How many number of vertices is there? Same number of things we are taking like, you know, which is initially it’s the same what what you have seen that earlier.

 

So 0 to 0 is no self look so that simple is zero. And 0 to 1 3 is there 0 to 2 is not there. so infinite we are taking 0 to 3 if you take it it’s a 5 so all these things we fill it we call it is, you know sp0 which you call. It’s a shortest path zero. So here what happens, you know? This diagonal elements you can fill it with zeros. The reason is simple. So 0 to 0 self Loop is not there one to one self Loop is not the two to two is not the three two, so that we fill it. and after that we we take it that you know these values. 0 it the row sorry, you know you are trying to from this particular zero We got it for all the direct Ages which are connected 0 to 3 0 to 1 0 to 2. There is no direct ages there so that we are putting infinite and 0 to 3.

 

There is a direct which is there five so that in that way we are connecting directors, which call is a yes P0 shortest path what you can say that you know 0 to all other Witnesses in terms of direct edges in terms of direct edges, but it’s not finalization. It’s not finalized. And output now. If you go for the next version SP one, what is you know? We are trying to find out zero to other Witnesses if you consider this particular row, we are considering this particular row. This particular row we are what we are trying to find out is 0 to other Witnesses other vertices via one zero to other vertices wire 2.

 

So that’s what we are going 0 to other vertices via one wire to wire 3. So that is what 0 to other vertices. Why are one if you go for that zero to other Witnesses, why are one there is no path see look at 0 to 1 so that what we do is these values as it is we fill it as it is, whatever values are there same values, whatever this two zero Infinity. is there two zero infinite to four. We are filling similar way. This particular value is 1 3 0 1 as it is we are feeling but other values you are feeling what other values are updated is, please see that here. 5 is updated here earlier. It is infinite is there it is 5 what exactly you know to to three? Ah >> SUBID NEHRA: so many of Music sorry, can you please repeat this last you? >> PDSA POD: in the in this particle in this particular 082 other vertices via 1. Why are one no change no change. It’s clear. same thing is repeated. Is it okay? >> SUBID NEHRA: the first color >> PDSA POD: Is it clear? Yeah.

 

So zero this particular first row and First Column. This particular first row. Sorry first row and First Column we try to fill it as it is because we are we are trying to do the SP one. >> SOWBHAGYA SHRI GOPU: Excuse me, sir. >> PDSA POD: Through SP 0. >> SOWBHAGYA SHRI GOPU: Sir, 0 to 0 while we can go now. >> PDSA POD: how can you self Loop is not there? No. >> SOWBHAGYA SHRI GOPU: 0 to 1 1 2 0 >> PDSA POD: Self CC no.

 

No, that’s not right. See look at this way. This way is called self Loop I’m talking about 0 to 0 means this. >> SOWBHAGYA SHRI GOPU: Okay, why have one we can go right? >> PDSA POD: 0 to 0 no, no, wait. Wait 0 2 1 we are going 0 to 1 to 0 is not there. I’m not considering that let you consider 0 to 0 means a direct Edge. clear >> SOWBHAGYA SHRI GOPU: Okay. >> PDSA POD: wire 1 y 1 if you consider again, it is a different thing, but right now But right now we are trying to fill it. No. So see that I change my code if you see the earlier session earlier session.

 

I use it that the diagonal elements whenever equal elements are there. We want to fill it with zero. clear >> SOWBHAGYA SHRI GOPU: Yes. >> PDSA POD: Ah, so that line of code if I don’t change it what happens, you know, simply 0 to 0, why are one what it will fill, you know 0 to 1 3 again 1 to 2, so it will feel five here clear. >> SOWBHAGYA SHRI GOPU: He is. >> PDSA POD: but thing is I I did not do that one because it doesn’t make a sense. That’s what I change. just one line of code. Okay, but you change it also not a problem because Professor is not given that condition but I have given it that is. >> SOWBHAGYA SHRI GOPU: Yeah in lecture Professor has >> PDSA POD: Yes. >> SOWBHAGYA SHRI GOPU: changed it.

 

That’s >> PDSA POD: Yes Professor is given it yeah. Yeah, you can follow that one out. It’s not a problem. But here one thing you should understand 0 to other Witnesses. Why are one that’s it >> SOWBHAGYA SHRI GOPU: okay. >> PDSA POD: so now because I am following this vertex, you know, same same Matrix. I’m getting here. So that please consider this one is self-loop one. clear fine Now and now 0 to other Witnesses, not 0 to 0. I am considering 0 to other Witnesses why R1 is it possible see 0 to 1 1 2 2 possible? No chance. Is it there? No.

 

Not there. No. Not there. No. yes, so that same value it’s carried but not issue. But here One Thing One update you can find here two to three there is updated two to three earlier. It is infinite this part you can see that this part. This part it is infinite here. But this part here. It’s a five. Did you find it? Hello. Did you find this one? So here it is 5 similar way here. It is infinite. Here. It is 3 now let you see how 2 to 0 via one. It’s three see two. two zero y r 1 see 2 to 1 we are going so then 1 to 0 we are going so that this is one and this is 2 so that it is updated with three. clear so similar way two to three wire one, So two to three actually I change something here. So actual what it contains is this graph it looks like this.

 

This is what the graph. Yeah. so two to three, why are one so two to three wire one is what it is, you know, so 2 2 3 y r 1 so 2 to 1 we are going first. It’s a 1 again 1 2 3 it is four so that it is updated with 5 value. Hope you understand. so earlier Matrix Valley is used for current Matrix. So here whatever values are there in the earlier Matrix. We fill it for this one. See this one. I am feeling this one. I’m feeling which is extracted values of this. So because earlier Matrix value is for using for current Matrix. So what you call it is, you know, this is K. If this is K The Matrix, this is K. Minus 1 am right. Is it right? Hello. This is Kate Matrix. So that what is this? >> ANNAPOORANI MUTHUVEERAPPAN: minus 1 >> ROHINI BALKRISHNA CHAUBAL: Yes. >> PDSA POD: So that the same same kind of thing is calculated here. So if you could see that the detail condition there so you can see that the minimum of so the shortest path of K minus 1 comma >> KARTHIKEYAN S: Ajay K minus 1 like this >> PDSA POD: earlier Matrix while use are used to generate the current Matrix.

 

See if you could see that you know this >> KARTHIKEYAN S: now why we are not increasing rather why we why we >> PDSA POD: use dynamic programming >> KARTHIKEYAN S: why we don’t say >> PDSA POD: dynamic programming is earlier Matrix values We use it final after final iteration. We get complete values. So this is not >> KARTHIKEYAN S: no, I I >> PDSA POD: hmm >> KARTHIKEYAN S: agree, but SP2 why you why we assume it has K and then s p 1 y v siva’s k minus 1 rather. we make it as k equal to 0 for sp0 k equal to 1 for >> PDSA POD: Yes. >> KARTHIKEYAN S: SP. One k equal to 2 for SP2 y >> PDSA POD: Yes you can you can you can you can you can do that. No problem.

 

But thing is why I should do us because this particular vertices I have that zero one two, three, that’s what easy identification. That’s only the thing. clear Yes, P of 0 ya put it is that because 0 it my my Witnesses is labeled like you know 0 1 2 3 in that way. That’s what I went. So instead of SP of 0 you can put it SP of 1 SP of two SP of three you can put it but easy understanding because by graph is matching to my you know, my my Matrix that’s only simple clear. Hello. Kumar edible fine, so that’s the reason I put it that my graph is 0 and at the same time a matrix also SP 0 SP 1 SP2. That’s what easy understand. You can put it to SP one SP2 if your graph is similar way if you can go that that’s very understand if your graph is zero and your Matrix is like, you know some SP one so some confusing is that that’s what to ambiguity avoid it simple clear.

 

So here please look at here. the existing K minus 1 and K minus 1 plus y are this this this K wire, you know. if you want to go for finding the path from I to Z i to Z So why are? k So what we do is we try to find out. i2k value Plus K to J value. these two these two clear So if this is if this is smaller if this is smaller. So existing value is greater like, you know existing values are directed. It might be that I to Z. So direct ages. What is the existing value if it is bigger? And through indirect age of K. It’s a better value or getting simply we replace this particular one. We are replaced. That’s what we have replaced this infinitive with five this infinitive with three this things I replace because of that reason.

 

Hope you got it clear. So this is done by your you know. See look at if you could go for that. Yeah, all pair fluid version. just you look at Sorry, there is incense Matrix and agency two things. Is there so which I am going. Yeah, here it is. So, of course, it’s a you know, I Ajay. This is Matrix for flight Arsenal. I want to go for Belmont Ford. Yeah. This is my yeah, Belmont Ford. So please look at here. Yeah. Wait wait. I have to go for fluoride was shall know all page shortest. Okay. Yes, here it is. See here, you can find it that. Loops which you can find it here this part. Yes this part so please look at here. this part so what really it is, you know the each version of this one. So this finding the minimum so they are trying to find out the minimum one. Which is from I to J or it might be that earlier value y r k minus 1 which is called, you know earlier through it.

 

So these two addition. If it is a smaller we use that value otherwise existing Matrix, which is K minus 1 Matrix. Is there the same value we’ll proceed that is so out of this which one is minimum So actually I did it with you know, less than grater then so to understand, you know better so this what I have written here. Yeah, here it is. So like if condition they have tried I have used actually because of this particular green color one. so instead of if condition they’re directly chosen the minimum value like Min function.

 

Is there whichever is a minimum we update that one. And finally you can look at, you know, complete Matrix. We are getting last updated Matrix slowly. We’ll get it the last version of The Matrix so which is the 08 version first version second version. So after that all versions is finished like, you know, one more version it will finish so after that, you know, then it will come take a conclusion or this Matrix the final one. So that’s the reason the reporting of the results. Also. It’s in the Matrix format.

 

You can look at this reporting of The Matrix. So actually if you could look at you know, they are using INF values. So even in my particular example, even I shown that, you know earlier session if you see that my YouTube link is there in that instead of this, you know, INF I have calculated sometimes sometimes I use it float constant of the INF of python and similar way this self Loops. I’m making like, you know zero zero I make it that zero one one. I make it zero. So that thing only simple line of code. I change it. I hope you can visit the session. That’s not a big deal. Okay. >> SUBID NEHRA: so, can you >> PDSA POD: so that that >> SUBID NEHRA: explain the metrics because I did not get can you just follow the code? >> PDSA POD: mmm Sure.

 

>> SUBID NEHRA: Whether there is shaped it. >> PDSA POD: Hmm. Here here is the vital part. Here is the vital part. >> SUBID NEHRA: Yes, >> PDSA POD: the exist >> SUBID NEHRA: I got this. But can you just scroll up little bit little bit? >> PDSA POD: Ah, yes. Yes. Yes. >> SUBID NEHRA: upset up >> PDSA POD: See, here it is. Here. It is. Wait here. My graph is this please remember this is my graph. So here yes 0 2 It’s a totally seven. Okay zero to seven. So you can find it, you know 0 to 7. So it is 0 to 7 means a it actually it means that 0 it’s a seventh one zero eight one. First one second one third one fourth one fifth one sixth one seventh one clear.

 

>> SUBID NEHRA: the >> PDSA POD: So here let me consider that 7 to 0 so they are showing it is infinite. No. So can we check it this one? 7 to 0 there is no path. to zero see look at here 7 Say 0 to 7. Is there 7 to 0 it’s impossible to go even through other vertices also, it’s not possible. See, why are six it’s not a possible via one. It’s not possible because it is only one way Direction similar way. So if you could see that. 7 to this is 0 this is one seven to one. It’s a minus 3. So, let me see. How did you get that seven to one? It’s a minus 3, so let me go for it. Seven to one. It’s a minus 3. 7 2 1 okay. so it’s a 7 is the source here because it’s all pair shortest one. Are you following then? Hello. >> SUBID NEHRA: business >> PDSA POD: So here all pair shortest means now seven to one. We are trying to find out seven to six it is one.

 

So here it is a minus 3. clear minus 3 so >> Md. Alauddin Ansari: in 14 >> PDSA POD: What is the value we got it? minus 3 simple So now one more thing you want to trace out it so I want to trace out that. 4 2 4 4 2 7 minus 1 how it is. I want to check it. Sorry 4 to 7. It’s not 0 1 2 3 >> Md. Alauddin Ansari: but >> PDSA POD: 4 5 sorry. 4 to 5 that is minus 1 so let me check it. How four to five. it’s a minus 1 now the source is considered as a 4 now. This is the source is it right? so 4 to 5 outs a directed just no issue.

 

So we’ll do >> Md. Alauddin Ansari: that >> PDSA POD: we’ll do something else. We do something else four to seven. It is infinite. Can you check it this one? four to seven it is infinite. clear >> Md. Alauddin Ansari: just >> PDSA POD: so here for four so four to five it is trying to reach 7. So 4 to 5 it went. Five to two it went. So 2 to 1 it went from the one we cannot reach to 7 is always it is, you know outgoing edges there incoming is only from zero is there so we cannot reach it.

 

So that’s the reason it is impossible. That’s what the thing even in my example also. So earlier what I did is this particular graph. I did reversing also see look at instead of that earlier. I erased it just you can look at that YT YouTube the earlier one. I changed this direction. So where you get the case of infinite instead of like three to two I made the two to three’s the direction. So nobody can reach the two but two can reach others so that way it happens. so that all paths reaching to two weeks becoming infinite like 0 to 2. It’s impossible 0 for example, I made a reverse this is reverse. >> Md. Alauddin Ansari: hmm >> PDSA POD: So in this case what happens, you know? So here to to we can reach others but two to others others cannot reach to. The that that’s that happens. So that’s what similar criteria explained so just you can see that white history simple.

 

Yeah, it is pretty much that so I can quickly go for mcst. clear >> SUBID NEHRA: So can you hear that? If we don’t shape. >> PDSA POD: Yes, yes. >> SUBID NEHRA: So again, you just roll up. >> PDSA POD: hmm clear >> SUBID NEHRA: Some area of defined the shape of the metrics. >> PDSA POD: Shape what shape is then? >> SUBID NEHRA: through common column and then >> PDSA POD: Ah, that is a Sensei Matrix. This is called Matrix. No. This is called. >> SUBID NEHRA: you yes, sir, but I have the doubt that I am not able to visualize the metrics and you please follow up. So just go up.

 

>> PDSA POD: Okay. >> SUBID NEHRA: the code to the code >> PDSA POD: Code, okay, okay. >> SUBID NEHRA: yeah, so this SP is equal to increase >> PDSA POD: this one >> SUBID NEHRA: the >> PDSA POD: output output is it >> SUBID NEHRA: speak medial device >> PDSA POD: where >> SUBID NEHRA: So it’s a very assign the variable SD. up >> PDSA POD: variable >> SUBID NEHRA: SP >> PDSA POD: Okay, okay. so see that SP initial version is setting this one. see yes, P initial while values. We are setting the graph entries, you know. >> SUBID NEHRA: But I’m not the line number five, sir. five >> PDSA POD: Line number five. Okay. Okay >> SUBID NEHRA: but yeah, >> PDSA POD: Line number five is creating the rows and columns. >> Md. Alauddin Ansari: Hi, everyone. >> PDSA POD: clear >> SUBID NEHRA: what is this >> PDSA POD: Yes, this is you know, tuple-sizer already. I explained you the Tuple it contains three values. See that so this Tuple this particular column is going you it is columns plus 1 >> SUBID NEHRA: Yeah.

 

>> PDSA POD: So how many columns are there? So let me take it is you know. Shape we are taking it is X. Hello. Hello. >> SUBID NEHRA: seven seven columns >> PDSA POD: Yes seven columns. >> SUBID NEHRA: Yeah. >> PDSA POD: So what it contains what it contains is rows and columns and one more we are giving it is a tuple the Tuple it contains a seven values. Wait, wait why it is Collins plus 1.

 

Why it is 7 values. It should contain Tuple contains only three values. No it is. It is two values. Wait wait. Columns is okay why it is columns plus 1. I think it’s not right columns plus one is not always shape. It takes three parameter. Third one is definitely you know, the size of >> ANNAPOORANI MUTHUVEERAPPAN: weight loss >> PDSA POD: a size of the weight. That’s what third values weight. Wait wait, so I’ll take the shape which is the X we are taking he Wait, because I have to check it where this particular method is called. Yes. Yes. Yes, please. Look at please. Look at here. It is. This part now yes. See before you are going to that function. There is a numpy area is created that’s called w. The W it contains that square Matrix is it right? Square Matrix no if it is 7 means 7 rows and 7 columns like 0 to 7 the output 0 to 7 in the output is clear.

 

>> Md. Alauddin Ansari: hmm >> PDSA POD: So in this each particular cell it contains that two values. two values the Tuple it contains two values. That is V. And the weight of it. clear >> Md. Alauddin Ansari: three men is >> PDSA POD: No, no, no U is already identified UE is already identified by the row see look at we w v w v w that’s just you can recollect that again the which I shown that earlier. this is C this is 0 which is called as U to v u to be you to be that’s what x exactly is it clear so that Tuple only two wireless fine. physically clear >> SUBID NEHRA: Good. >> PDSA POD: see I have shown >> SUBID NEHRA: Okay. >> PDSA POD: you that earlier when I shown you the hsnc Matrix, please please. Is it clear? >> Md.

 

Alauddin Ansari: Yes here. >> PDSA POD: Yeah, yes. Yes, it contains the same same thing. They have been done it the conversion of your whatever your input. This is what your input know your input contains U2. we and W time fine. >> Md. Alauddin Ansari: W yes >> PDSA POD: W do your input your input adjust you are giving but you are not giving >> Md. Alauddin Ansari: yes. >> PDSA POD: that Witnesses, but I have to convert into incense Matrix. >> Md. Alauddin Ansari: Okay. >> PDSA POD: So this for the converting your particular input into instance Matrix.

 

>> Md. Alauddin Ansari: What is that last parameters are two indicated? >> PDSA POD: Wait, wait, let me finish up this particular two jobs has been done in the earlier professor as given two score Snippets. You can see this just follow these codes Snippets same code Snippets they are using how to convert your input into hsnc Matrix how to convert your input into its in list simple clear Is it clear? No? >> Md. Alauddin Ansari: hmm >> PDSA POD: So this part is done by every every particular algorithm before calling the algorithm procedure. So you did it for? What is this? Yeah, it’s a dynamic programming. So we are still at yeah, so this part. Oh, sorry. I’m to go for Belmont Ford. Yeah. This part is exclusively converting your input into agency Matrix while converting what it is doing. Please see this. We are taking that I to say three values are there. No you V is there no so let’s consider is you and J is V. and W is a w three values you are taking from the input fine. so what they are fixing at 08 position, they are fixing one so already said it if their path is existed one.

 

We are setting clear so >> Md. Alauddin Ansari: Okay. >> PDSA POD: that weight is that this 10 is there? No this 10 is fixed here. Is it clear? Okay. It whenever path is existed. So 0 to 7 path is existed. So what happens that 0 to 7? So 7 is the V. And what is the weight? it’s a weight eight is updated. So that’s why it’s keep on adding so that >> Md. Alauddin Ansari: Oh. >> PDSA POD: complete W is created this completely called this completely. Oh, sorry. There is a ReSound is getting because of all mute so this completely this one is a complete converter W. Is it clear? this double >> Md. Alauddin Ansari: Okay. >> KARTHIKEYAN S: the wij 0 >> PDSA POD: hmm >> KARTHIKEYAN S: it should be. one >> PDSA POD: Yeah, it should be one because you know when there is a edge when there is age. We are representing With Honor when there is no age.

 

We are representing with zero is it right? Is it right? >> KARTHIKEYAN S: Yeah. >> PDSA POD: That’s the reason wherever you know, whenever you find a edge immediately. We are fixing it is but rest all them wherever it is not there that is filled by zeros by this particular zeros this part is there no. Except that reminding all zeros. NP Matrix what it will do NP 0s Matrix npra what it will do numpy initially. It creates the 10 square Matrix with all zeros. fine So accept that zeros wherever it huh? >> ANNAPOORANI MUTHUVEERAPPAN: It will be zero comma zero no. >> PDSA POD: Yes zero comma zero simply. >> ANNAPOORANI MUTHUVEERAPPAN: Okay. >> PDSA POD: so except that other things has been filled based on your input.

 

Clear fine >> Md. Alauddin Ansari: Okay means the first node >> PDSA POD: Yes, yes. >> Md. Alauddin Ansari: has been managed from the index in the parallel manager Baki the remaining >> PDSA POD: Yes. Yes. >> Md. Alauddin Ansari: to we are inserting into the metric >> PDSA POD: Okay. Is it clear? >> Md. Alauddin Ansari: so >> PDSA POD: They this is taken as a paramet. This W is taken as a parameter 2 this fluid version. Now this fluoride virtual what it will do us so another local Matrix. It is creating. fine local Matrix. It is creating. So actually they are creating, you know columns. Also, it is plus 1 they are creating like it’s not like, you know, so this particular Matrix output, so please look at finally the result what their resulting is. Colon colon columns only they are written. they are not returning that reminding value. See look at intelligently they are using this part is missing Only The Columns they are printing so that what it will do is it will print that all >> SUBID NEHRA: It is a value of the column.

 

>> PDSA POD: yes. >> SUBID NEHRA: So the value of the column 3 >> PDSA POD: Yes, yes. >> SUBID NEHRA: okay. >> PDSA POD: values are must. Yes other clear so only the printing that I did it if they print all rows and all columns what happens, you know, so you get that another seven mattresses like, you know, first part Matrix zeroid Matrix fast Matrix via third Matrix, why are fourth Matrix you get all versions We don’t want it. Final version only wanted is it rare? So that’s the reason that just they are returning only this part. fine >> KARTHIKEYAN S: This one is not clear how the it is.

 

Yes. >> SUBID NEHRA: so >> PDSA POD: just you just you you look at you. Look at just my earlier session. Just you can better understand because we have to spend a lot of time for you know spanning algorithms clear. >> KARTHIKEYAN S: Now the problem here is not the >> PDSA POD: hmm >> KARTHIKEYAN S: algorithm. >> PDSA POD: Yes. >> KARTHIKEYAN S: the problem here is how we code it. >> PDSA POD: Yes, so actually, you know. >> KARTHIKEYAN S: Coding is what? >> PDSA POD: true true Yes. >> KARTHIKEYAN S: Actually, I am facing difficulty only the coding >> PDSA POD: Yes. >> KARTHIKEYAN S: understanding algorithm is not that. >> PDSA POD: but thing is mmm >> KARTHIKEYAN S: Only thing is writing it in a court and how to write a code and interpret the code is >> PDSA POD: Yes. >> KARTHIKEYAN S: No, I’m having challenge. >> PDSA POD: yes, because you know what happens, you know, if if you are being more practiced with a Sensei mattresses and educationalists like, you know a dictionary nested with the list a list nested with the dictionary and a list is nested with a couple if such kind of you know, it’s in mattresses and it’s since he lists you take another graph my suggestion.

 

hmm >> KARTHIKEYAN S: if we take one one iteration and then fill this return how it will. >> PDSA POD: No, no. >> KARTHIKEYAN S: is going to >> PDSA POD: CCC. >> KARTHIKEYAN S: return for the first iteration at least. >> PDSA POD: That’s what the thing. That’s what the thing already I shown you this one see. That’s what the one iteration see this one. If you go for my best >> KARTHIKEYAN S: No, this is okay that I >> PDSA POD: my versions of my see this is this is what exactly this is. >> KARTHIKEYAN S: yeah, no how the written value will take the information and then to say for example, if it is returning SP one.

 

>> PDSA POD: mmm Yes. >> KARTHIKEYAN S: a little written how that statement will >> PDSA POD: Yes, this is this is DC. >> KARTHIKEYAN S: attendance >> PDSA POD: This is a zeroth column. This is the First Column let you say version version or column. What do you say that I can say that version or column? What what do you say that? It’s a final one? I don’t say it is, you know version or column anything.

 

So here finally we return columns means the last version is written. For example if you could see that. If you could see that. My my code if I did it. Instead of this particular columns. I did it columns minus 1 what happens, you know last but one version you get it. Is it right? Last but one version these are the different versions, you know, one version is maintained. This is a column number 0 maybe the version number one let you consider because if seven vertices is there you might have seven versions if six vertices is that you might have six versions. So this is the column number two each one we can consider this is a column number three. so they want to return final column only see they did it final return with. last column so that last column limits last seventh version the seventh version is simply again combination of rows and columns it returns.

 

That’s what a thing the last version only if I don’t do that you get fast version second version third version keep on printing if you do this job if this return job instead of this return you print this particular, you know SP here you print this SP here. What happens you know, you get the first version you get the second version you get the third version all versions you get it, but I want final version only. clear see integrating the code with this one means my suggestion is please try with another graph see even I’m shared this particular PDF with you. This one contains only a graph with four Witnesses four. It’s not such a complexity graph which was there in the you know code you take this particular Vertex or this particular graph input these values.

 

Input these values to the code and try to see that what is happening? my suggestion is that I I strongly recommend this one, even you take a graph with three vertices. Is it clear? Hello. Yeah, I’m in the call. ah, >> KARTHIKEYAN S: I mean, let me try because the basic Stripes Alpha I was busy. >> PDSA POD: c >> KARTHIKEYAN S: I was facing last night a lot of challenge. >> PDSA POD: what what if frankly again? >> KARTHIKEYAN S: It’s not coming.

 

>> PDSA POD: I I open you. I open you show what way you know, I generally you don’t debug or understanding the existing Professor code is yeah my screen visible. Hello. So what I’ll do was always the professor is given some particular code. I try to test in different ways like, you know, just a matter. Let me go for this week. Why no. Yeah, this is week 5. Yes, so if I go for so even sorry.

 

Week five Floyd Marshall so what I’ll do is this is the graph given by the professor is it right? Is it right? Is it right? Hello. Yamaha edible >> KARTHIKEYAN S: Yes, yes. >> PDSA POD: so what I’ll do is intentionally, I’ll try with my short graph. Is it clear? so similar way you take another graph which you draw it and put the edge values and then try to run it. >> KARTHIKEYAN S: This this program is already shared >> PDSA POD: See our same same nothing. >> KARTHIKEYAN S: with >> PDSA POD: I change it only accept this part. This part is what I did is intentionally I did it. you know this part. Sorry this part this if condition is only added. Because self Loops are not there. I put it the zeros only other things I made it as it is only that 20th line.

 

I changed it. I did not change anything. Is it right? Just you can check it in my earlier session. You can easily understand but thing is my suggestion is always you try to explore the things with your own graph you draw it. And try to input that values to this particular code and then you try to debug your code. That’s very easy clear. because we don’t look at a complex the graph so that you know, seven Witnesses or 10 vertices. Definitely you will be confused. And don’t try to Interlink that particular algorithm to seven vertices and seven vertices with you know code. This integration is somewhat difficult. So my request is take a small graph and try to do that. fine >> Md.

 

Alauddin Ansari: Okay. >> PDSA POD: Okay. okay, so I’m going for spanning. Just give me one second time. I’ll drink the water. I’m back. Look at here. So we have seen that. Always we have fixing what? One Source or we are fixing with the many sources the previous three algorithms like single source multisource So based on it, we are trying to find out the shortest path or shortest distance in terms of weight, please remember in terms of cost only in terms of cost or weight. Another interesting fact of using graphs as which are you know? similar kind of real-time applications real time scenarios We try to find out that.

 

Spanning trees see spanning trees is very simple. a minimum number of edges Which connects that all vertices in the graph? minimum number of edges which is the least number of edges possible. And it connects to all of that like, you know, so you have that zero. one Two three, so you might have this one. so this is not minimum number of edges. So this graph can be converted into a spanning tree in terms of like this.

 

0 to 1 and 1 2 3 and 3 to 2 simple, of course, two to three or three to one is not a problem because it’s a undirected graph so that minimum number of edges so that all the particular Witnesses are connected. And here please remember here is a minimally connected tree. So what it is, you know, there is no cycle is existed. You know, it’s a cyclic one. So the spanning trees. definitely a cyclic one. See you don’t have that against cycle going from 0 to 1 1 2 3 1 2 2 3 2 2 it’s indirectly or going there is no direct is there if again you connected again you have the cycle so that is not you know, it’s a connected graph, you know recall the minimally connected minimally connected. It’s a cyclic one. And the similar way it’s not self-cycle.

 

I’m I’m saying it is it is a cyclic. Please understand self-cyclist, you know 0 to 0 is a self site. That’s you called. So now that adding an edge it creates Loop see if I ladder for this panning tree if I add it. Immediately what happens, you know, it creates a loop 0 to 2 3 2 2 3 3 2 1 again 1 2 0 it creates a loop is created removing in it. For example, so this is a spanning tree. So please remember this is a graph. This is a spanning tree. So of course this self Loop is not there. Now removing an edge because how sensitive is the spanning tree, you know, if any edges removed simply your particular graph will become that disconnect of components. For example, if I remove if I’ll remove this. immediately this 2 and 3 will become one component 0 and 1 it will become one component component means don’t worry. It’s two different graphs. so similar way again, we are connecting this. so if I remove this Edge this Edge So 0 alone is a one component 1 2 3 is a one component so that so the spanning tree is so sensitive like, you know, if any edges removed immediately.

 

It will disconnect the graph. So wanted tree connects to all particular vertices. You want a particular tree which connect that all of them directly or indirectly. more than one spanning tree also possible. Remember one graph. is not containing one spanning tree you might have multiple spanning trees. So this is a graph. This is parindary one for the same graph. I might have another spanning tree see look at I’m making another spanning tree for the same graph. 0 to 2 and this 2 2 sorry 0 to 1 so then after it, I’ll make it. This this is another spanning tree. for the same graph spanning to true, So I’ll make another spanning tree you know trees as trees. We are taking 3 is this one two? And then we want to connect this. one and then want to 0 so many spanning trees is possible. So whenever you are you are making a graph connected with the limited edges. It might result that many spanning trees, but one thing you should understand. So what are the advantage of making multiple spanning trees like this spanning tree one spanning tree true and one more spanning tree. You might create. So that might be spanning to three.

 

So what are the object to offer? We want to find out the minimum cost out of these three spanning trees. Which is the minimum one? so, how can you do that’s one is adding the cost of this edges like, you know, either this Banning trees a a total cost is smaller. Or the spanning tree two is smaller or spanning tree one is so among all different spanning trees choose the which is the minimum one available. And some facts about that trees. if tree with n vertices exactly has that n minus 818 like you know four vertices.

 

Is there the spanning tree? definitely you have three edges only that is what the true. Adding an edge which might create a cycle. So if you add one Edge immediately it will create age. Even you add it here. It will create a cycle. Hope you understand. That’s what the thing so as and when you add one particular any additional one Edge immediately, it creates cycle. so in tree every pie pair of vertices is collected by unique path see unique path. Is there see look at this unique path is that three to two two zero and zero to one. So that’s right similar way two to three three two, one one two zero. So unique path is created. So this is what exactly the spanning tree how really and minimum spanning tree means out of different possibility of spanning trees. We pick up that you know, a minimum one that that’s called, you know minimum cost spanning thing called, you know mcst a shortest form or we can say that abbreviated form of it. now to work with spanning trees We have two algorithms.

 

So I’m taking the same graph because even in this particular Professor example also in summary, he has given the same graph. Hope it is given same graph. Let me check it. Dreams yeah, same algorithm same graph. So I’m taking the same graph. hmm >> KARTHIKEYAN S: Before going for this. can we just understand when we have to use this? This is the first algorithm digits and well forward. >> PDSA POD: Yes, yes. Yes based on the problem based on the problem. >> KARTHIKEYAN S: forward and >> PDSA POD: see >> KARTHIKEYAN S: yeah, can we just discuss that before going to this just >> PDSA POD: Sure, definitely definitely definitely definitely see I want to go with the real time scenarios of example dextras. We want to find out. So I want to find out a shortest part always my source of reason. I’m moving always my particular, you know, there is a best example even your practice assignments or graded assignments as given even in the professor lecture also.

 

A courier central office is there that is a source always. It tries to reach that all of its, you know endpoints where it has to distribute that Parcels to different different. Customers, you know can consider you know delivery points. So always your source is at one place. That is not changed. From that branch office are from that local Distribution Center. We try to reach for all of them. So when you are reaching them. So what could be the shortest path? So shortest path and sense? So if I reach it from 0 to 2 and then two to three So what is the cost of distance if I reach the 0 to 3 directly? What is the cast? So 0 to 3 distances, it is taking 7 kilometers of distance if I go for 0 to 2 and then two to three it is only three kilometers.

 

So I’ll go wire two, so that is called. You know, Dexter is always it is fixed one source. Only always we try to find out. one branch office to distribute to all other, you know endpoints with a shortest resistance. Now the situation is sometimes there is a real-time scenario. Even I discuss the real-time scenario with negative weights in the professor lecture. as discussed about you know. cab driver example if in in my in my instruction of the last week if you have been attended. So I’ve discussed, you know, for example, you have a production company or it might be you you have that selling point is that you’re trying to sell out that Goods to different locations like daily or supplying You are supplying to Bihar you are supplying to Hyderabad.

 

You’re supplying to some mother different states. So when you are supplying to the delay. so items to delay after the expiry date the supposed to return the items. So Delhi people are not meeting the sales demands. We’re going to sales demand. This is the people are not demanding your item in Delhi state. They are returning 90 items back high I distributed 100 items. They are returning 90. So every time they are returning 90 means there is a negative or you know output I’m getting so even I’m getting negative output also, so I have to find out the shortest distance. So in that case I have to go for that.

 

So Bellman Ford Belmont Ford, what it will do is it works with negative weights also always it’s not profit. Sometimes you have to get that you know. loss also that loss we are representing with minus. so such kind of graphs also you can tackle and finally. What is my head office profit to some particular, you know State some particular State some particular State? I can find out, you know all of this particular profits. That is one scenario, which I strongly suggest with negative. And if you go for you know, Floyd Marshall. the Floyd virtual is not single you you have the table one is a source. We try to find out from 0 to all other one to all other two to all other three to all other. See what exactly you know here. You can take a best example of you know, legal lines of the network connections they do. always they do a setup box or it might be a broadband connection. They do a setup box that setup box will distribute to different kind of end the customers like, you know, different clients who have been users of the ISP ISP provider.

 

See the Broadband, you know Central correction point is that it can distribute to three or four? Similar way again. Another Broadband setup box is there it can connect to? Three or four another setup box is there it can collect to three or four So every time I want to choose is different setup box and I want to find out that the shortest distance so that here origin is not single so you have that origin points are every time it’s a different of course The central ISP point is different.

 

I don’t want to tell about it. So every setup box is having its own set of bandwidth that bandwidth is distributed to different kind of end users of this, you know fiber optic line or it might be Broadband connections. So that is the best example for you know, Floyd Marshall, you know multisource. So these are different examples, which you can of course if you the time supports that I I’ll integrate this one to your grp. assignments. Is there no graded programming assignments. I I’ll tell you how to solve it with integration of this algorithms. Okay? Shallow proceed them. >> G HAMSINI: You know, sir. I want to know the difference between a tree and a spanning tree because in >> PDSA POD: Yes. >> G HAMSINI: the notes that you’ve given us as minimally connected.

 

>> PDSA POD: Tree tree can be tree can be spanning tree see so spanning tree is a one version of different Alternatives of trees. That’s nothing else. See see, yeah. >> G HAMSINI: What is a special property of spanning to the like makes it to spanning to? >> PDSA POD: Wait, wait, wait, wait. Wait, let me think about it. This is a tree. clear So, of course it is not binary tree. It’s a tree. so one two Three all of them are descendants, you know, is it clear? so it can be a spanning tree also because it’s a tree and as well as it’s a spanning tree also. Why it is called spanning tree, you know, it’s not having any kind of Cycles.

 

Is it there? >> G HAMSINI: And okay, no, no. >> PDSA POD: so that a tree can be a spanning tree but a GC look at what I what I call is, you know spanning tree is a one. Derived one. Sorry a spanning tree is a derived one. from a connected graph >> G HAMSINI: Okay. >> PDSA POD: a connected >> G HAMSINI: so, can you give me an >> PDSA POD: so not connected not connected cyclic cyclic.

 

I’m sorry cyclic graph. >> G HAMSINI: Oh. >> PDSA POD: So what I say that cyclic graph >> G HAMSINI: So, can you give me an example of when like a when it is a when it is a tree but not a spanning tree or when it is. >> PDSA POD: See, yeah, that’s what the this is a tree. say tree can be a spanning tree. So what I strongly believe see trees always having one parent and descendants are there. It here. you have the tree like this? >> G HAMSINI: No. >> PDSA POD: So what does it mean, you know two weeks having two parities it possible? >> G HAMSINI: No. >> PDSA POD: So it will become a graph. >> G HAMSINI: Okay.

 

>> PDSA POD: so that tree is a spanning tree only for the sake of Span span they use it. So tree is expanding tree both are same same properties. Fine. >> G HAMSINI: Okay, same properties, >> PDSA POD: Yes. Yes. So in the spanning tree you have always it is one parent only. Tree also having one parent only see look at here. This is I can go with another dissonant. to dissonance poor and fine is it possible file is connected to two? No. I’m right. So if it is connected what >> G HAMSINI: Know >> PDSA POD: happens, you know again cycle is formed cyclists form means it’s a graph.

 

Simple clear Yeah. This is yeah. Yeah, so tree and spanning tree. Both of them are synonyms. Only thing is multiple versions of trees are there in that one version We select with a minimum weight so that it’s called mcst minimum cost per entry. That’s nothing else fine. Yeah, so let me go with that. The first algorithm is Prince. See that we So we have the multiple spanning trees are possible from the same graph. So what you strictly do in this mcst algorithm is we take that. a total ages what you call, you know three edges total ages or we can say the tree edges. Initially, it is empty. So what you call this is empty one. So we are considering this might be a dictionary. It’s empty dictionary. in this what you do us we try to start from one of the vertex you you choose any of them? See here, there is no rule that we have one source, three or two or four anyone you can choose it anyone. So let me choose it. This one don’t think it’s a source. It can be a starting vertex.

 

So once you choose it. from the s from the 0 adjacent Sorry, I am sorry this tomato. Now the zero is selected. The 0 is selected, you know. choose choose all exists Sorry. extent to vertices and sent vertices all adjacenter what this is. of zero say don’t think zero is fixed. Even you can do the same thing with one also, even you can do the same thing with 4. Also you get the same kind of spanning tree. So what are the different particular vertices is there is here zero to one is there. It is, you know 0 to 1. You have 0 to 1. What is the weight? It’s a 10 is there is it right? 0 to 110 is there no. fine This one is what is the weight? >> AMEY KULKARNI: 10 >> PDSA POD: Yes, so Advent is there. What is that? What is that? What is that three? yes zero to 3 what is the weight? 18 so here out of these two adjacents, which is the minimum.

 

So that choose the minimum. Choose the men. of above AdSense to append it to tea So T is appended so that what happens, you know, of course already appending once I said it definitely should be taken like list because dictionary cannot have the facility. Yes. So T what it happens, you know, so one immediate edges appended. So what edges appended this 0 to 1 is appended of course, wait if you want to add it you can add it if you don’t want to add it and so this is visited. So this is visited over is it over now? Is it over? This is visited. No. So that I I’ll mark this one is a green color.

 

This is visited. Is it clear? Is it clear? So, I’m sorry. This one is red color only. This one is a red color. So now again again, what we do is find out. One agent Witnesses and zero accent vertices so 0 incentives think I still pending is there what are the pending here? 03 is pending. Is it clear? so that again still so that next vertex adjacents current Any AdSense? So if you choose at this. Still 0 is having another incentives that 0 to 3. So that already this is over. This part is over. So this particular? What is having zero to three? 18 is there. and then so this one is connected to two. So two of them. So one is this one is this fine one is connected to this one. No. So here one more ages there. 1 2 2 there is a weight 20 is there. And again, one two, three, there is a weight of 6. Now three edges are there is it right? So which one is the minimum? out of these three eighteen twenty which one is the minimum? So that this reason minimum so that this is selected.

 

So this is selected means what happens, you know append it. Sorry. append it into T. Sorry. arising Okay. So now choose the minimum. So append it Append it to T. So that is three edges. So now my tree ages it contains that. 0 1 of course weight is there and tree is there? So now so one is over of course zero is over. Don’t worry the zero also over. Because we started from 0 only visited we make it true. Of course. I I’ll integrate with code also, don’t worry now. Three is connected with four and three is connected with zero and yeah, that’s only two so that right now three because two is not at completed so that three is connected with What are the three is collected with choose? I am choosing the red color again. I’m choosing the red color. Yeah choose. next stage since Next we adjacent. So next we age sense means we have that 3 is connected to 4. Three is connected to zero. See it’s a bidirectional one 0 to 3 means 3 2 0 also there is it right? 0 to 3 means 3 to 0 so there is it right or wrong? Hello.

 

>> ANNAPOORANI MUTHUVEERAPPAN: SRS >> PDSA POD: yes, so because the directional one sorry it’s a undirected graph so that 3 2 0 also there comma and next one is three to four is there? It says 70. Yeah, that’s it. So out of this I have to choose minimum, but if I choose a minimum of this this 0 is already marked as visited so I cannot choose that visited true thing. So already visited true thing is there I cannot choose I can choose that which is UN vegetable only in the UN vegetated. We have only one alternative. So what is the alternative in I have to choose that. >> ANNAPOORANI MUTHUVEERAPPAN: Said I have about the we don’t want to append the remaining ones which were not used to before. >> PDSA POD: Yes. 0 to 1 is added. And what? >> ANNAPOORANI MUTHUVEERAPPAN: No in the second Step the zero three eighteen and the one to 20. We’re not no. >> PDSA POD: 0 to 3 1 2 2 1 2 3 See wait wait, >> ANNAPOORANI MUTHUVEERAPPAN: Because first time we upended the remaining one no. >> PDSA POD: Yeah, reminding only already existing 0 to 3 as it is we are coming and for that one to two we are adding this is and one two three six is added.

 

>> ANNAPOORANI MUTHUVEERAPPAN: Yeah like that now we don’t want to append the zero 318 and 1 to 20 for that to choose. >> PDSA POD: You know zero not a zero, two three how it is 3 to 0, please consider 0 to 3 3 to 0. >> ANNAPOORANI MUTHUVEERAPPAN: Okay. >> PDSA POD: even it is 0 to 3 3 2 0 is not a problem because that it’s undirected graph. No. >> ANNAPOORANI MUTHUVEERAPPAN: Okay. >> PDSA POD: 3 2 0 0 to 3. We don’t choose because already visited visited will become true means we don’t visit again. fine >> ANNAPOORANI MUTHUVEERAPPAN: But we don’t we don’t want to >> PDSA POD: Yes. >> ANNAPOORANI MUTHUVEERAPPAN: consider this one to two and >> PDSA POD: yes because it is creating a cycle. It is creating a cycle if you choose that it creates cycle.

 

So we have chosen this Edge. We have chosen this Edge if you choose this Edge what happens it creates cycle? No. >> ANNAPOORANI MUTHUVEERAPPAN: Okay, I’m asking about that previous step. Second one >> PDSA POD: Yes, 0 to 0 to 3 18 is there. >> ANNAPOORANI MUTHUVEERAPPAN: And one to two twenty is there. >> PDSA POD: Okay. >> ANNAPOORANI MUTHUVEERAPPAN: No, we didn’t use that. There are no we don’t want to use that for this choosing. >> PDSA POD: Okay, sorry. Sorry. I’m sorry. I have to use it. I’m sorry. >> ANNAPOORANI MUTHUVEERAPPAN: Yeah. >> PDSA POD: Oh, you’re asking about 1 to 2. Yes. Yes, you supposed to use it definitely supposed to use.

 

>> ANNAPOORANI MUTHUVEERAPPAN: Whatever we are not using the >> PDSA POD: Yes, yes. Yes. Yes. Yes. Yes. >> ANNAPOORANI MUTHUVEERAPPAN: previous step we have to use it for choosing. >> PDSA POD: you’re perfect puff I missed it. Wanted to >> ANNAPOORANI MUTHUVEERAPPAN: Okay. Thank you. >> PDSA POD: Because yeah one to two twenty. Then we have that. Yeah, this is not used and next one is three to four is there? 70 3 to 4 70 Clear, so now three to zero we don’t use it because already it’s a visited one.

 

If you choose it again, it will create a cycle. So I don’t want to choose it between these two which one you selected one to two. Yeah, perfect. Thank you for interrupting me. So this is a perfect one three two four is not a right one. One to two is the right one so that we don’t choose it this part we choose this one. So that 1 2 3 is the right one means we choose this one. So what my te contains is now what my T contains? T contains what? already existing zero and one and one and three and the recent shortest one. This is the recent one to two which is a minimum one comparatively want to to 23 to 470 one is a minimum. So I’ll choose it one two. Two and one to two pathi chosen, so that what happens, you know this path is done. So that is pretty much. So this graph is completely connected. So what you supposed to get it is 0 to 1 so 1 2 3 sorry 1 0 and then one to >> ANNAPOORANI MUTHUVEERAPPAN: We have to look No.

 

>> PDSA POD: wait wait, so this is over then. Two to four two to four we are say okay. Okay. I’m not at choosing this path. I have to choosing. Yes one to two. Yes, one two, two. Let me finish up this one. This is not chosen two to four is not done. So I have to erase this one. Sorry four is not chosen till now. So I have to choose this. one to two also Because we have chosen that 1 to 2. so three edges are done. Now we have that. Okay still it’s there because 2 to 4. Is there three to four is there so that reminding two existence out of it what you have sober to select us, So next existence spending is we have two two four eight is there.

 

And similar way you have that three to four 70 spending. Yes. Of course this 324 and out of these two. these two, we definitely be choose it this minimum one, which is 8 so that this two is connected to Port so let me complete this with weights what weights are there. This is integrated with 10. Sorry associated with 10. This is associated with 20. Okay, one two three associated with six. and this particular 20 to 4 is associated with eight. So here if you consider the total cost of it. It is 28. and 34 and this is 10 44. So total mcst cost is minimum cost spanning tree cost us. 44 so let me check with the code which was given in the lecture. see Yeah, Prem selest. actually, they are using Prince list on primps. Yeah, this one anything. Okay. Yeah. Is it you know, they’re given? Matrix okay. They have used list only. no problem. Please stand this one is not a problem, please look at here.

 

Yeah. This part is here. Yeah. So, please look at here. You can find it here tree edges, of course. I have taken te don’t worry, then the name could be different. Definitely to append it we required that. list So initially what it is, you know. Every visited vertex is made it as a false. All of them visited is false. And what the distance it existed is infinite. they made it infinite, you know default.

 

It is reachabilities infinite. So initially they started from 0 don’t think it’s always from zero, even you try to fix it. Three also you get same. You you try to fix it tree, even you get the trees for two also, it works same same algorithm. It doesn’t change any code. Even you fix that starting vertex is three also, you can choose any one of them. Now the distances are updated see the distances has been updated V and D every time the W list already. I have shown you that 08 vertex is having. a couple of values already said and first value Second value. This is what the list is created, please look at this list. This part of the list. You can see that it Tuple with two values. So from the eye for I we are trying to add a couple with two values the same thing is done.

 

That’s what the thing that trying to extract the values V and d u is already fixed. That is zero eight one first one and keep on getting in the WLS. So in that what we trying to get it is this particular V is updated with distance the distance value. Is there no that distance value is updated. So in earlier infinit is there this Infinity is there no. This Infinity is updated with the distances what you have given the distances you have given. 10 18 that distances are updated once distances has been updated. Yeah. so once distances in updated now that particular repeating the below below process for number of vertices. so in this Initially minimum distance. They are putting it infinite. Next to visiting vertex is none. In this what they did is, please look at here. The visited of you that you must be visited. And adjacent of you must be not visited both conditions must be true. And distance must be less than the minimum distance initially minimum distance is infinite. Definitely it is less than the existing distance. For example, the first distance is there. 10 10 is definitely less than the infinite what happens, you know, the distance is updated the instead of this particular infinite.

 

We are getting with distances. And whatever the next visiting vertex that value of the particle next visiting vertex is updated. And the edges also updated into these three temporary variables these three temporary variables next to visiting. Next stage to be visited and a minimum distance. now they are trying to append it whatever, you know see this Loop is completely repeated after this. if you consider you is having the edges of 1 2 3 7 sorry, I’m sorry. It’s not one two three up to one. It’s only one value, you know. 0 to I’m talking about exchangealist because already you familiar with incense Matrix. You might have a little lambiguity with agency list. So 0 to 1. There is a weight of one. and similar way you have 0 to 2 your weight of 6 2 adjacents are there.

 

Out of this after this complete for Loop is finished. You get the minimum one into the minimum distance. What are the minimum one? you get the minimum distance that is called out of this minimum one is going to be that 0 to 2 because it’s a 6 we don’t select that 0 to 1 because it’s not minimum. So we choose that next stage. Is that which is the minimum because this condition has to be satisfied as and when this condition is satisfied we get a final updated value once all edges of zero is traversed. All incense of zero is Traverse we get the minimum once we get the minimum. We try to append it this one that age we are trying to append it.

 

After that, she still it is still it is the outer loop is not close till you are in the outer loop, please look at sorry. Yes. Wait wait. This sees yeah outermost Loop. Yeah. Yeah it is. Yeah here it is. Outermost Loop. Outermost law, please. Look at 14th line number is outermost Loop. Now what happens? you know another key value we’re taking this one. From this one. We are trying to pick up the minimum one. I hope that 1 to 2 you have that you know weight of 13. And you might have one two three, you might have that weight of 70. So this particular in that we are trying to choose the minimum so that to update that next distance. We have taken this particular, which is and visited. Please make sure it is not visited the V must be again the distance updated. So every key you are selecting. In that key.

 

Whatever adjacent vertices are there in that minimum one. You are selecting that minimum one. We are updating into trages. this is implemented using it but one thing is somebody might got a doubt how this 44 can be acquired. Am I right? Is it right? How this 44 can be acquired. Did you get it? Hello. >> Saurav Kumar: yesterday from the Sun >> PDSA POD: yes.

 

yes, so we got it what what this particular this particular code it will tell you us. It this output if you could look at please check it. Oh already. It’s same 0 to 1 1 2 3 1 2 2 2 4 same thing. We got it. 0 to 1 1 2 2 so then after it output is Yeah, one two three, of course, you know. this way or this way one to two is first one two, three is next is not issue. Don’t worry about it. And next one is last one is two to four but thing is as and one appending process is going on. I supposed to get the cost value also how much it is totally cost.

 

So what I’ll do is simply I’ll put it one Global value a global variable which might be that total cost is zero. symbol Initially, it’s 0. So then every time when the appending is going on see when the appending is going on. This cost also I need to add it. Sorry. Sorry very it should add it is. Yeah, here it is. Yes, when this particular appending is going on at this place? the total cost is existing total cost plus after this completion of these two Loops. We get a minimum cost out of this which one minimum in this zero you get that minimum cost is 6 while you go for one the minimum cost you get 13.

 

So so that what I have to do is I have to add it Min distance. simply while you return it. I should return along with the edges I should return total cast also, so two values, I’ll get it. The first value is what is the path this value? And second value you get 44 also. Just you tried with the local variable, you know top you declare a TC. And as and when it G’s added. Immediately you add the total cost you add it. Just just you return it. So that is what exactly this prim’s please. let me know any clarifications. Yes. because if you would like to see the code execution also, I’ll open my vs code and show you but please tell me any doubts in the concept. hmm >> AMEY KULKARNI: So if there is a little one change if we replace that with 70 with 8, so >> PDSA POD: Very good. Yes. >> AMEY KULKARNI: what would be the change? >> PDSA POD: Yes. So if it is similar evades is there.

 

It might choose any one of them. if first one is chosen, so you like, you know, two minimum values you give it you get one of them only like you try to put one camper simple code, you know python just you standardize with the minimum one. Even you try this one. One of them is selected. Like I have a couple list of top is my screen visible. Okay. Okay. So in this what I’ll do is I’ll make a couple. This is 8. Of course you consider that is 0 status. So and one more is From two to four also you have eight. Let you consider.

 

This is the T is a second row. So in this I’m trying for minimum. so this couple of minimum So you get it? it might be four eight or it might be three eight not issue because that’s the reason you know when you go for questions like these kind of questions is there. What they’ll ask you us whenever similar weights are there then we go Chronicle chronological order chronological order in the sense. We we go the two wire two only we don’t use wire 3 because two is smaller value. So we don’t go via three we go to through that to that’s it simple.

 

Okay. Is it clear? Even even you go with another another, you know another age. which is one wire one also we can go it mean that. So I can go that two to one also, I’m taking the same value. So then it will go for you know. So this couple I’ll try with minimum. So then it will do that. the chronological order of the vertices instead of the distance similar distances.

 

Is that so generally they give this kind of questions in the alphabets like, you know, like instead of 0 1 2 3 they try to give it a b and C and d and of course This one, for example you you might have that why a b to D. You have that eight weight. Is there C to D. Also weight 8 is there they try to choose via be only because it’s alphabetically B is fast. That’s nothing whenever similar weight is there. Yeah. Yeah, pretty simple. Of course this kind of same question. You can get it in your graded assignment or it might be. Yeah any other clarification? Shall I need to execute the code? Because code changes. We want the cost also know. Hello. Or shall I go for concept next concept? Okay. >> Saurav Kumar: you can go for concept >> PDSA POD: Okay. Yeah. now critical is some what easier than the prince. the prince what they did is they tried to put it that. All of the weights existent to wait said sent vertices weights in a less and they try to pick up the minimum one.

 

So for that they are trying to use min. But the crystal is very simple what they simple is. This simply sought the edges. Sorry. Yeah. first basic initiators Sort the edges. based on based on weights this is what interesting fact. They immediately sought it based on the weights. So based on the weights if it is sorted. Can you tell me what is the lowest Edge it is? If you could see that are able to see my graph.

 

>> ANNAPOORANI MUTHUVEERAPPAN: Is it five to six? >> PDSA POD: Yes exactly, of course five to six or six to five is not issue. So five to six is the smallest one. Because it is a file. next one next one >> ANNAPOORANI MUTHUVEERAPPAN: one and two >> PDSA POD: Yes one and two. This is 6. Yeah next. please >> ANNAPOORANI MUTHUVEERAPPAN: zero and one >> PDSA POD: Yeah 0 and 1 is there four and five is that cronologically we go, don’t worry so that so we go that 0 and 1 it’s a 10. next one >> ANNAPOORANI MUTHUVEERAPPAN: four and five >> PDSA POD: Yes, four and five because >> ANNAPOORANI MUTHUVEERAPPAN: and four >> PDSA POD: chronological we are going yeah four and five is 10. and then >> ANNAPOORANI MUTHUVEERAPPAN: and four and six assists in >> PDSA POD: yes, four and six also 10 chronological >> ANNAPOORANI MUTHUVEERAPPAN: then 0 to 2 >> PDSA POD: yeah 0 to 2.

 

Yeah, 0 to 2 is the next because the next one is 20 is there 70 is that so 0 to 2. It’s a 18 next one. >> ANNAPOORANI MUTHUVEERAPPAN: 1 to >> Saurav Kumar: wonderful >> PDSA POD: one to four cool one to four It’s a 20. and then last one is >> Saurav Kumar: two to three >> PDSA POD: two to three It’s a 70. first basically this sought by the third value of the Tuple. your input values. Is there no in this input values we based on the weights. We try to sort it. After sorting very simple. We are selecting each of the Edge In ascending order that means lowest to highest. Whenever you add the date. If it is creating cycle, you avoid it? If it is not creating cycle you continue. For example, I’m going that. Five and six, is it creating any cycle? See I am started creating first identify and six, so I’m creating five to Six, sorry.

 

Five to six is it creating any cycle? Is it creating any cycle? >> ANNAPOORANI MUTHUVEERAPPAN: No, no. >> PDSA POD: No, it’s not creating. one to two is it creating any cycle? one to two six next one 0 to 1. Is it creating any cycle? No, so that 0 to 1 if it’s not creating any cycle just you put it. Four to five. Is it creating any cycle? Because yeah, I am creating four is here. Yes, four to five. So what is this 10? Is it creating any cycle? No problem four to six? Yes.

 

It’s a dangerous one. four to six is creating a cycle so that we avoid it. We avoid it. this is a wider because it is creating cycle. Because already six is already available. From the four you’re trying to reach six me six is already visited simply. It is visited means we don’t do that. next one 0 to 2 0 to 2 it’s a creating cycle so that we avoid it.

 

So we avoid it. next one 124 Is it creating cycle? No, so that it is. 20 next one 1 to 4 is over next one two, two three. Two to three. It’s a new one. No problem. It’s not creating anything 70. Now the total cost we checked. 20 30 40 46 116 161 160 and this is five, you know, so 121. So let me check it what my outputs this is that this is the graph. No. Oh, sorry. I have used a different graph. Okay, okay. Prem’s no. I’m sorry. I’m sorry. Yeah, I have to go for prints. Yeah, wait wait. >> ANNAPOORANI MUTHUVEERAPPAN: for crystal >> PDSA POD: Yeah Crush color. I have to go for Christmas. Yes. this is Yeah, we use the same graph great. I’ve used the same Graphics. Okay then no worries. What my output is. Yeah. It’s 120 pretty much. So let me integrate with the code. >> G HAMSINI: So, can you just show the graph once again? >> PDSA POD: Yes same graph. I use it. Fortunately I use the same graph. Yeah. >> G HAMSINI: For Prince and this the same graph.

 

No, I think it’s >> PDSA POD: No, it’s a different graph. That’s a different. That’s the reason I’ve taken the same example of that lecture only. This is a different >> G HAMSINI: Can you? >> PDSA POD: This is a different graph with six. Sorry 0 to 6 mean 7. Care now, I’ll integrate with code what really happening in the code. Shall I go then? >> G HAMSINI: So just one second as is note down >> PDSA POD: Okay, this is a shared document. No, why should it is? >> G HAMSINI: the graph. >> PDSA POD: Which is shared document if you would like to write it also, okay? This is a shared document in in GitHub. Summary is given no, is it there in the dashboard? >> ANNAPOORANI MUTHUVEERAPPAN: Yes, sir. It is there. >> PDSA POD: Okay. Okay fine. No issues. Yeah now. Shall I go then? Shall I compare with the code now? Shall I go? Okay.

 

>> G HAMSINI: Yeah, yeah. >> PDSA POD: Okay, fine. Yeah, see look at here. So that procedure is implemented or not. We’ll check it. So please again I want to just go over. with whether they converted into it since Lister and since the Matrix so here also agency list is used. They are trying to append it. That trying to append it. So I is nothing but you at J is nothing but we and they are trying to append it essential list is added.

 

So now please look at here. or don’t worry about component component is very pretty simple see before. Before you are you are doing when you are being added zero to one. It looks like independent component like, you know zero to one. If you found one particular rate G’s independent, maybe two to three you found that another independent. This is called component. This is called component each. One of them is called component initially each particular vertex is a one component. So that’s what initially it is a Current is there. Edges is there. And te which is called, you know, 3 edges or spanning tree edges. So then they are trying to pick out the values from the U key, sir. And edges has been extended. With please see this year. Distance we are getting as a first parameter.

 

U and v as a second and third parameter because they want to sort by. weights so this is whatever new edges we are creating what way they want to create it, you know. these taken as a first actually you We and D. But what happened, you know this conversion what it will do us these are first one we sorry you and V is the next one so that when it is sorting it tries to sort it by distance only. if similar distances is there it tries to choose the second value is it right? Chronological order? Is it clear? So, yes, the topple can sort it very easily when you choose a distance as a first so actually what did it is, You know, we have done it. W list key it contains that distance is the second one, but we want to make it the first one so we are selecting V and D using vnd. We try to convert into top edge with three values distance u and v So after that we choose each of them is initially each vertex is a single component.

 

Each of them means initially all of them are disconnected 0 is disconnected one is disconnected to his disconnected 4 is disconnected. All of them are independent. So now the Sorting job is done simply called that. sought it’s a predefined method of you know. python so after sorting now, they started see look at this is what extracting. You know minimum one. Sorry extracting each one. Take it whether cycle is there or not Because you not checking in minimum all of them are in ascending or incremental order. First one second one third one. Keep going in increment order only so we don’t need to choose it again Min function. Simply what I’ll choose it is. Each D and u and v you selected. if it is not creating cycle, this is not creating cycle. When it creates cycle, you know if it creates a cycle you and we are same like already component you and component we same then it creates cycle.

 

If it is not the same simply will update that u and v we are appending it. And component is updated, you know new component is created like, you know, like you and V is connected you and V is connected. Then this entire one is Creator like a new component. This entire one is created like a new component. So after that. again update that component later, either. This can be a leader. Or this can be a leader because I have to pick up that the essence of this. I have to pick out the Ajay sense of this. So that’s the reason again the components have been updated update the component leaders. So once component later is updated again, we try to choose it, you know. So what is the next one whether it’s cycle is creating if cycle is not creating if same later you are selecting. For example, you have that another one. It’s called you know, W, if W is connecting to this the component later is referring already visited one.

 

Simply it is creating a cycle. We don’t want to include this Edge. So we will include whenever. It’s not equal to that. the existing component So then we will include otherwise that simple. So finally see like appending job we do with t, you know, that’s called, you know, three edges the finally we return the three edges. Similar way if you want to find out here also minimum cost same thing. You know, you take us here. critical also you take us here 0 as and when appending job is going on there you do it. PC equal to TC Plus So UV or appending along with the time to pick out that you know.

 

The weight also see each edit contains that you and v d also there so D. We are adding just simply we are adding D because already it is extracted by three different. You know, Tuple values D is a different V is a different that DV added yellow with TV. We supposed written just easy so we get that path we get it. Along with the path we get that. the 121 output also simple This is very easy comparatively when you compare with, you know, Prince the primcies you have to extract every time Min function has to be executed. But here, you know, simply all of them are sorted by weights. We select in the sequence if then the sequence if any cycle is created simply we avoided if no cycle is existed. We keep on doing. So this is pretty much directions about this mcst and two algorithms.

 

So if you have any clarification, please raise it. Otherwise, I’ll go for how to integrate these algorithms like, you know, you lend almost five algorithms in the week 5 so using these five algorithms how to solve this grpa assignments. Just I’ll guide you. Quickly is it right? >> Saurav Kumar: Yes. >> PDSA POD: Yeah. Okay. Yeah, tell me tell me. >> G HAMSINI: Can you just a briefly go through again? like you sorted out in terms of the rates? >> PDSA POD: mmm >> G HAMSINI: and then >> PDSA POD: after sorting we are extracting three values, Whatever the sorted. is there sorted means already we have sorted this particular list, For example, this is this sorted one is there no.

 

Five six ten ten. So here actually I’ve written it right most as a weight. So but here it is, you know five is >> G HAMSINI: mmm >> PDSA POD: going to be the leftmost because you know, the sorting by the weights these nothing but now the sorting by the weights is done means we have to check it YouTube. We are checking. the component is nothing but every component I said. Every particular vertex is a one component like, you know. This is one component. This is one component. This is one component. This is one component. So all these are independent components earlier. see look at all of them are independent company initially. each vertex is one component.

 

clear Okay. >> G HAMSINI: is >> PDSA POD: now U is not equal to V whenever you are trying to move from U to V for example, this can be you this can be is it right? whenever they are not equal then only we are connecting so that we are checking the cyclist existed Rod. So YouTube We you two V.

 

We are connecting. fine So then we are appending this one. For example, this is collected one two two also connected. Not equal but what happens, you know 0 to 2, there is Edge for example 0 to 2 what happens? You know, this is already considered component you and this is already we this is already added into the component this now it is entire three vertices is a one component. So it is matching. This is matching U is matching to this. That means already included in the components once it is included in the components. We don’t want to attach it. Sorry, we don’t want to attached. So that cycle we can check it. This U2 we is not equal then only we append it after appending we update again component.

 

The C is a temporary variable what exactly you know, the updated component is completely updated into C. And leaders are updated leaders in the sense the parent of two one the parent of one zero. so if this is you know complete one the parent of one is 0 the parent of 2 is 1 so that is one, you know lateracy is updated later C is updated means parent of one this is parent of it. So if you are trying to connect again this 2 to 0, you’re trying to update one of the parent so one of the parent if you updated it creates, you know. Cycle is created one cycle is created. So it doesn’t mean that spanning tree so cycle can be avoided.

 

With the help of this part this part using this if condition so one cycle is not there. We append it and similar way complete component parents are updated. The latest means here parents are updated. Who is parent whose parent is that? So that that cycle is been updated. So this is what exactly? So this part is for detecting the Cycles exclusively Cycles if cycle is not there. We append it if cycle is there we don’t append it. Just we avoid that particular. Edge whatever Edge is there that YouTube we are avoiding it. Yeah. Shall I go then? cool See you try with another graph. Actually. I’m taking the similar graph from you know, whatever you and one more thing. I forgot to tell you. Ah spanning trees is it works for directed graphs? what the question. Like, you know Prince or it might be critical. Is it works on directed graphs? Because One Direction no.

 

It’s a question small question for you because you I want to check it your understandable. >> Saurav Kumar: Yes, it can work. >> PDSA POD: But what is the problem? >> Saurav Kumar: for when is crossing like when we are taking the cyclic agent then we are >> PDSA POD: hmm >> Saurav Kumar: not considering any arrow in data, but when there is a director grab then we have to consider the arrow. >> PDSA POD: no, that’s not the issue actually when you might have you know, even you see you look at here under directed graph. one two Three so you you might have Crossing. No problem. No problem. the problem this one can result many varieties of graphs this one also suitable for mcst minimum cost spanning trees But what the issue with directed graphics? Optimal solution is not guaranteed.

 

Is it right? Best solution is not possible why it is best solution is not possible as 0 to 1 so 1 to 2 and then this way it’s there. This way it’s there. and then 0 to 1 is there no so we have three to zero it’s a directed. Please remember it’s a directed. so you might have Three to so what happens, you know? you definitely choose that only one way of Direction. for example if I want to reach that 0 to 3 means Even this cost is tree. This cost is seven. And 2 I have to reach only via way of that 0 to 1 1 2 2 1 2 3 only. I cannot choose that 3 to 0 is it right? Optimal solution is not guaranteed. We we cannot say that best solution it’s a very strict. Strict parts are associated. Is it right then? Hello. I hope you understand. Due to the strict paths, you supposed to follow that path only. So that’s the reason we cannot get optimal solution in terms of that minimum cost. Hope you understand. Hello, that is the issue reminding things is brims and critical minimum cost spanning trees possible for even directed us, but optimal solution is not guaranteed.

 

Yeah. Okay. now we go for the big five grp on. Yeah, so CRP open only. Yes. So are you able to see the question? Hello others, please. Hello. >> SOWBHAGYA SHRI GOPU: it’s it’s >> PDSA POD: see So this is please read the question. Internet service provider company wants to do that. laying that fiber lines connecting to the N cities 0 to n right a function fiberic so it is taking a distance map a distance map is nothing but existence list. They are clearly said about you know. so adjacentialist this essentialistic contains is already we have discussed earlier. It has a couple of two wireless, please you find that first while is distance destination. index. Sorry, I can say that we because I’m using in my lectures also you to be and in the professor lecture also is using you to be when Source index is a you and destination index is a v And distance in kilometers we can say cost a weight or distance or some some particular synonym like in somebody says, you know profit negative profit or positive profit something like that.

 

So in this way from you to other ways agency list is created another you to other way. the function returns that minimum length of fiber required to connect that all n cities all n cities Or here, please. Look at here. What I try to use it is. connecting the all with a minimum with a minimum so they did not tell you that any kind of source. Hope you understand. They did not tell you any kind of source. Hope you understand. No. So let me go with the simple input. The can I take this input and draw the graph? Hello? Because for four matrices know can I draw this graph? Okay. Okay. Yeah, I’m drawing this graph because that input how it is processed.

 

So this input based on it? if you could look at 0 to 1 1 2 2. Yes 0 to 1. It’s a four weight. one to two they said it is for sorry 0 to 1 is 2 no. 0 to 1 is 2 1 2 2 they have given four. And if you could see that. 0 to 3 is 3 and 0 to 2 is 1 so that 0 to and 0 to tools 1 2 to 3 is last one six, I think so Waste Management. Let me check. Yeah, two to three six. fine So this is what exactly it contains your input values, of course it is a list. What? poor Witnesses and his phone so if you draw the graph what it looks like is, you know, zero eight one. So may not be looks like same but it’s almost same. to and three, so if you could look at this one 0 to 1 to 2 is there yes 1 to 2 is there 0 to 1 is there yes. And we have that zero to three also there. And we have two to three also there this is six.

 

And 0 to 2 is there it’s one. And zero to one is there. it’s a two. And 0 to 3 is there. It’s a three. And one to two is there. It’s a four. Is it right graph? Is it right now? Is it right? So I want to find out that the minimum fiber optic wire line or it might be minimum fiber optic length. Which can connect that all of them. so See that particular spanning tree.

 

What it will do is we try to find out the minimum cost. minimum cost because you know we want to connect that all of the but this is all of the ending points with a minimum cost. So in this way if you go Mcst algorithm we try to use it which one you choose it either you can choose. Prince orchestral We choose a simplest one. So what is the simplest one? What is simplest one? Critical is simplest one. No. >> SOWBHAGYA SHRI GOPU: cushions is >> PDSA POD: Crystal is simple simplest one. So in this simplest one if you choose it we try to sort them by the weights. So based on the weights if it is sorted first minimum one is 0 to 1 so that we are connecting.

 

Zero to one next minimum one is next minimum 1 is Yes 0 2 1. next minimum 1 is >> Saurav Kumar: 1 0 2 3 >> PDSA POD: yes 0 to 3. Yes. Any other is it resulting a spanning tree? 0 to 2 is there? And 0 to 1 is there. And 0 to 3. Is there is it a spanning tree? >> KARTHIKEYAN S: Yes. >> PDSA POD: What are the total cost 1 plus 2 plus 3 it’s a total six? So what >> KARTHIKEYAN S: Yes.

 

>> PDSA POD: you supposed to do is just you copy that whatever Prince algorithm. You put it in your grpa one same as it is. Same as it is. clear So inside you are you know this particular function they said you know what my function name. Yeah in this fiber link distance map Is there so inside of this function you might have deaf. Fiber optic what is the name? Yeah fiber link. fiber link Link it’s taking the distance map as a parameter. Of course if you see that, you know the prefixed code definitely you are having the tensionalist. So you have to write. The critical algorithm. Please. just copy another function. So of course, it is another function critical algorithm. So this critical algorithm takes that so let it be it’s a w list. It’s in the list. Same thing whatever it’s their same things we are doing what they asked you the output is. What they ask you the output. Only that 6 they did not ask your partner. They asked you only value so only value.

 

So what I supposed to do is I said it no simply inside the critical you take the total cast. You you try to add the cast which I shown you here. Which is shown? Yes, yes. >> ANNAPOORANI MUTHUVEERAPPAN: are appending in to look. >> PDSA POD: Yes in we don’t return this tea. Just we return total cost. simple easy clear so that this can be solved even you using prims also, but primc is a long procedure. So so you better choose the best algorithm. Because sorting complexity is already taken care by that, you know python existing function.

 

Just you saw it. I hope you know the thought function python complexity. What is the complexity? short function of python >> SOWBHAGYA SHRI GOPU: in login >> PDSA POD: Yes, because they are using maybe you know Med start there might use it. So is it very sad? And login. Yeah a quick start. Yes quick start quick start. They are using quicksat. Yes. So that the Sorting complexity is reduced so that we can do it with Krishna algorithm. That’s what pretty simple when you want to solve the grpa one. Let’s see you do not do much. Just you copy the crystal algorithm then instead of returning the T. We return that total cost. that’s over only one line of code adding and that thing it happens. Yeah. >> ANNAPOORANI MUTHUVEERAPPAN: A synonym in in any case do we have for prims than criskal or >> PDSA POD: No, no, so what one is better than other is two mathematicians has said you know why to choose minimum? The you know if you just you compare the summary.

 

It’s another approach of just a matter. It’s not that only this particular negative way. It’s positive weights directed graph. That thing is not there. See it is is to find out it. Iteratively, it will do it. It is also using greedy method same like, you know. They did not tell you, you know, like crystal is better than this one only for the Simplicity of coding. only other mathematicians added better sorted and then go with it it ascending order instead of doing you know. >> KARTHIKEYAN S: Provide you call it greedy.

 

>> PDSA POD: Yes, so greedy means what, you know current situation. It is a better solution. current situation It’s a better solution in future. We cannot predict it what the feature you know, for example a new particular vertex is added for the current graph. Which might have the smaller weight? So we cannot predict it. That’s the thing. They said even in the lecture also. He said it is it’s a greedy only I think he has given one example, you know burning of vertex. Even you have the optimal path in feature. You can reach it directly reaching from X to Y instead of it. Why are W if you reach it, maybe have shortest one. But that we cannot predict it so current situation. It is the best. If new particular vertex is added for the graph. Maybe you get other optimal solution. Is it right? Hello. greedy is the for the current situation. We say that it’s a best solution. even I said >> Siva Bhaskaran: But he means I think you choose the best possible at this point of that whatever.

 

>> PDSA POD: yes at this point at this point. It’s the best solution. >> Siva Bhaskaran: And then it will move the next appointment. It will choose the best possible at that point of time. >> PDSA POD: Yes. Yes >> Siva Bhaskaran: So it won’t do it won’t take into consideration the whole point so >> PDSA POD: yes. Yes. Yes whole point. We will not be considered even I said one example of you know, the greedy approach of like going to the shopping if you could see that earlier you YT of my lecture I said it is fast initial difference of greedy and dynamic. Then I went to that, you know. >> KARTHIKEYAN S: Maybe better named wise. >> PDSA POD: Hello. >> KARTHIKEYAN S: Better to call it wise >> PDSA POD: Yes. >> KARTHIKEYAN S: current situation test >> PDSA POD: a better to call instead of current >> KARTHIKEYAN S: why is >> PDSA POD: Why is y is okay. Okay instead of current it might be a better word is yes.

 

It might be a wiser >> Siva Bhaskaran: But the thing is it may not be wise. Okay, there are certain algorithms if I’m not sure we really approach will not work out in the long run. >> PDSA POD: current scenario, we can say >> Siva Bhaskaran: In this in this thing about secrecy, so we are good with that. >> PDSA POD: No, no, let me write a word to be used it like, you know, I I said it is current situation current scenario. He said it is wise scenar. Why see why >> Siva Bhaskaran: He is ready. >> PDSA POD: solution wise? He said he said why solution novice >> KARTHIKEYAN S: I’m just saying see taking a decision. >> PDSA POD: why solution >> KARTHIKEYAN S: with the current situation the best decision making is normally we call it wise.

 

>> PDSA POD: yes for >> Siva Bhaskaran: in retrospect >> PDSA POD: for the current situation why solution I think >> Siva Bhaskaran: this is this is just >> PDSA POD: Yeah, yeah integrate these two these two sentences if you integrate it could be better meaning. for the current situation of isolation Is it okay? Hello. Yeah, that’s because I have to integrate these two so that maybe I yeah it is right for the current situation. It’s wise maybe in future. It might be yeah. So let me go for that second problem with the second problem. Yeah, I’m going for second grp, is it okay? others >> ANNAPOORANI MUTHUVEERAPPAN: answer >> PDSA POD: Yeah, this is you know minimum cost walk through.

 

So that’s it. You know they are going with minimum cost walkthrough of w list. Fortunately, they are taking agency lists only so that essentialist is easy to operate and easy to implement comparatively agency Matrix. that accept that which since the list for undirected connected Graphics example grab they have given the function Returns the minimum cost. and walk route in the format of minimum route Yes minimum cost in the walk root of it. Yes walk route is here. two different routes, so that is source to destination Why are we okay, okay. So source to destination. Why are we in the sense? So you you can run. Yes. yeah, it it’s a You you just you recollect that dextras algorithm. see, I’m just recollecting the discuss algorithm because I want to get the same graph.

 

Maybe it’s a bigger graph. Smaller graph is not there. Okay, not issue then so it doesn’t make a problem like you know, so. I’ll recollect that you know dikshas algorithm. Just what I’ll do is so we are trying to pick out. So as per the question. there are s2d and V so what I’ll do is simply what I’ll do is let’s take an example input. So if you consider that example input see look at example input. 7 vertices these are different edges with weights. 0 is the source. And four is a destination. And 5 is a v which is intermediate everyone. So what I’ll do is example if you take about that.

 

Source is zero. at destination is 4 another wire or we can say that another vertex in mediator is called, you know, intermediatory one is called 5. So what I’ll do is very simple. I will call. See same thing the Dexter’s algorithm. Deaf, is there no just you copy and paste whatever, you know, the digestas one is there. With it’s interest. So if you get the version of it just you go with version say I’m going just going for the version. Because anyway you you can just recap and since a list with the text us. This is Bellman Ford. What parameters it’s taking that we think about it? Yes, see look at it is taking from a source. So that we are going with Source. Yeah, that’s fine.

 

I’ll call the same code you copy it you supposed to go over that. same copy we have specifying The Source here. Just just you copy it whatever the code is there. So I’ll call this particular function. Inside your function. Maybe your function is said it is the function name is mincast walk. See I’m writing my Min cost walk just what I’ll do is deaf main cost walk it takes the parameter of W list and S and d and V. So what I’ll do inside us, I will call. distress I will call this discuss algorithm. Same whatever it’s copied one. with w from s what I will get it is I’ll get one shortest distance shortest distance. What I will get it is. S2 shortest distance from S2 Others I’ll get it is it right? Is it right? As to others I’ll get it.

 

No. >> ANNAPOORANI MUTHUVEERAPPAN: guys >> PDSA POD: Yes to others. I’ll get it so s two others I am getting means in that s2d. Also there is it right? >> ANNAPOORANI MUTHUVEERAPPAN: Yeah. >> PDSA POD: Because if you could if you could see the output, please see this one because I want to just >> KARTHIKEYAN S: Yes. >> PDSA POD: show you that what is the output is C look at here.

 

Yes here 0 to 0 is 0 0 to 1 is 10 0 to 2 is 16 0 to 3 is 386 0 to 4 is 30 0 to 5 is 80 0 to 6 is 35. so that from 0 to others because they fixed it zero is a source. This is the source. fine so in that in that D also there so in this others D also there D also there get the value. get the value get the value as D1. This could be a distance one. Is it clear? So that first time I’m calling this is a call number one. Same thing I’ll do second time. What I’ll do is same distress alcohol. But can you tell what is my source now? >> ANNAPOORANI MUTHUVEERAPPAN: we >> PDSA POD: What is my source now? >> ANNAPOORANI MUTHUVEERAPPAN: that midpoint the joining one.

 

>> PDSA POD: Yes, wait. >> ANNAPOORANI MUTHUVEERAPPAN: We know. >> PDSA POD: so Oh, sorry. >> ANNAPOORANI MUTHUVEERAPPAN: Through we are >> PDSA POD: Okay. Okay. Sorry. I’m sorry true. We are going so I have to go for here something mistake. I’ve did it. also included. so that we also included not D. I’m sorry. Yeah.

 

>> ANNAPOORANI MUTHUVEERAPPAN: or we >> PDSA POD: Yes. Yeah. >> ANNAPOORANI MUTHUVEERAPPAN: have to see for we in the first. >> PDSA POD: So what I try to do is S2, we are finding for the shortest. Sorry. S2 V I get a distance 1 is it right? Then I call again again second time. I’m calling. the distance algorithm with same W list Now my source is S2.

 

We got it. No. From V we started from Veena. So from the V means we are getting again shortest distances. Shortest distance as we get it. >> KARTHIKEYAN S: Oh why we have to do it two times. Why first time itself? Why don’t we call >> PDSA POD: No, no, so they said they said via walk through through wire. We they said clearly so S2. We got a distance again V to D. You get a distance. >> KARTHIKEYAN S: Oh, okay. >> PDSA POD: So these two these two distances, we will add it and we’ll return it. so that >> KARTHIKEYAN S: Through with the question is through you.

 

>> PDSA POD: yes. Yes. The question is. They said it is why this root only. So S 2 we have to call it dexterous algorithm again V 2 D. We are getting so that we get a distance values that value addition. We do it and that value we written so that’s what they said it is, you know, the path can be repeat, you know, so while you are going the test to we you might include, you know a particular vertex of three. Again, why are going of v2d also three is included no problem. Yes, yes. >> ANNAPOORANI MUTHUVEERAPPAN: represent in both the single edge >> PDSA POD: Yes, single edge maybe vertex may be present in both the parts, which is not a problem. >> ANNAPOORANI MUTHUVEERAPPAN: Yeah. >> PDSA POD: Because the parties the edges may be repeated twice in the SUVs repeated and v2d also repeat also not issue, But only thing is two times we call it and just will pick out the best one.

 

Sorry, some of these two that’s it. If you go for third one. yeah, it is pretty straightforward and Negative cycle present or not? What should be then? What should be the algorithm? Yes. The flight virtual so let me go for my inputs what my inputs is. Yes. So in this case two graphs, you know if you could look at this graph. Yen with four zero to one zero to two and 0 to 3 and 3 to 2 2 1 Yeah, here it is. Negative is existed. Here. It is non-negative is there. so what what I’ll do is what I’ll do is but small changes have to do in this, you know, the Bellman further. in what changes are required because Belmont Ford it has to detect it. Yeah, let me go for that code how it looks like is it in senseless? Yes, and since it is only we go for that version only. So some changes we have to do it for Belmont Ford. Yes, this is what the Bellman fort. They said it can’t detect the negative Cycles. Yes we go for the version of it. And since the list sorry, it’s a matrix.

 

Yes. This is what the essentialist. Yes, so I have to detect it the negative cycle also. Yes. Pretty easy very easy there. see, I’ll tell you very few lines of code. If you attach that. Your job is simple. See, what are those? You are doing Edge relaxation. Is it right? It’s relaxation. N minus 1 it’s relaxation. No, this is is it right? Because it’s a dynamic, you know.

 

It’s relaxation after this outermost 11th line of code is completed. You supposed to get it. One stabilized distance. Is it right? Then one stabilize the distance you get it? Is it right? >> ANNAPOORANI MUTHUVEERAPPAN: Yeah. >> PDSA POD: After this complete 11th Loop is finished by the 17th line. You supposed to get one distance that one distance is stabilized or not. You have to check it. Is it right? That’s our objective.

 

Is that no? >> ANNAPOORANI MUTHUVEERAPPAN: Yeah, if negative cyclist is not there. It will be stabilized. >> PDSA POD: Yes, how can you ticket is very simple? You try to repeat these two Loops once again, so what I’ll do is again for Loop you I’m repeating see before that. You are returning distance. What I’ll do is Again, one more time don’t again include this outermost. Look. this look again for V Loop inside you check it. a single change like the same condition the distance of view. Still You Are getting less than value. distance of V one more time you are running. No. Just simply you are returning. true Even you find a single change in single iteration. Is it right? This is a one more time one more time Loop.

 

We are running additional code you have to attach only these two Loops. You have to put it just before it. This is not included inside your level. It’s a separate Loops just above the return two different loops. It’s a one more cycle. Is it right? if there is a change you found it still there is a change just you return it true. Otherwise instead of returning this after these two Loops are finished we written. false When we return false, you know all these two Loops these two Loops are there no. This two Loops never met with true condition never met the true condition means all values are stabilized. We don’t get a new update when you don’t get a new update. The values are stabilized so that negative cycle exists Is it clear? Hello. >> ANNAPOORANI MUTHUVEERAPPAN: Yes. >> PDSA POD: so only thing is just this particular version you need to repeat just before the return only thing is inside the if condition don’t update the value just you return true.

 

Out of these two Loops just written false. That’s the reason you can check your inputs here. See what it is, you know interesting way. They did it same graph. Here minus 20 they used it if you kindly Focus the value. because if you draw the particular, you know, I’ll try to draw the graph so that you’re better understand see that I’m drawing the graph which they have values.

 

Same values and try to give it 0 to 1 0 to 2 is same graph. I’m trying. See, I’m drawing the graph so that you can understand better zero to one. 10 is given. and 0 2 0 to 2 minus 5 0 to 2 minus 5 Cat2 is given here. minus 5 it’s a directed graph. Yes, next 0 to 3. They have given it it’s a 2. 0 to 3 they have given it. It’s a two. Positive value only next one I think one two, three, they have given it. 0 to 3 is given three to two is given. So minus 5. three to two minus 5. Yes. this way minus 5 Yes. And then 2 to 1 Dev given it. minus 2 then 1 2 3 they have given it. 10 okay, okay. so >> ANNAPOORANI MUTHUVEERAPPAN: One value was minus 20. No. >> PDSA POD: wait, wait. Okay what the value is minus 20. That is a dangerous one. Yes, two to one is minus 1. Yes. Yes. Minus 1 2 2 1 is yes, this is the resulting negative Cycles, please look at here. 10 at this minus 5 it will become 5.

 

And 5 minus 20 it will become minus 50 so when it is minus 15 here. Again, it will repeat because you know minus 15 and then plus 10 what happens, you know, it will get that minus 5 so minus 5 and plus minus 5 you get that minus 10 so minus 10 and minus 20 again. This will will go off you get that 30. So this cycle never ends. If it is a second version of this input. Intentionally, they did minus 2. If this is minus 2. If this is minus 2 instead of this. Minus 20 if you do it minus 2. minus 2 here Yes minus 2 here. You don’t have negative Cycles, Please carefully observe it. so 10 and then 10 and minus 5 it’s going to be that you know five. at this first cycle after that 5 you get that minus, this is my 3 after the tree you are getting 13. After 13, so you I’m taking you know, three Cycles only because after going for three Cycles, it’s going to be extreme once cycle is finished.

 

Second cycle I’m going now. So 13. So 3 to 10. It’s a 13. 13 minus 2 so you get it as you know eight so that eight is not bigger value than five because the existing sorry. Existing. Oh, sorry, I’m sorry. Yeah. I’m sorry, because let’s assume it is you know. one and three and because I want to check it only here only. I don’t know the ticket other things to and this part is yes only this one This is 10. This is minus 5. This is minus 2. Yeah, that’s it. So let’s let me do the first time so first time when you do that, it’s going to be 10. because 0 plus, you know 10 and this it’s going to be 10 and it’s going to be 5.

 

And then it is going to be 3 is it right? This far cycle is over. Now the second cycle we are repeating. So when you do the second cycle what happens, you know already three is there. So 3 plus 10. It’s 13 13 is not a better value. So we don’t want to do the 10 is a better value. 10 and minus 5 it’s going to be that 5 only is it a better value. No, so existing value is 5 is new value 5 is both are same no better value. Now five minus 2, so it’s going to be that. 3 already 3 is there we don’t have a better value. So second cycle also done. Even you run the third cycle. Also you get same values. Even you run the fourth cycle. Also, you get the same mileage. That’s the reason intentionally. They did it two inputs first input with minus 20 second input minus.

 

So it’s pretty simple only thing is you run one more time and you check it whether you know negative edges are. Negative cycle is framed or not. If one more time if you run it if any time updated value is found you return true. Otherwise end of the loop you return for simply you do that. Whatever Bellman Ford is there just just you copy the same thing. Sorry, you know Floyd Marshall. is there Floyd Marshall is the same thing. You copy? Only thing is just you add one more. Two loops and just using some if condition return true or false.

 

That’s Yeah, yeah any clarification about this Erp? Plug. Yeah. >> KARTHIKEYAN S: We have to use flour martial >> PDSA POD: Yeah Floyd was not Belmont Ford slide of us. Okay. >> ANNAPOORANI MUTHUVEERAPPAN: This Friday. We are going to have live coding or week 6. >> PDSA POD: So is it? Week six session is done or not. Let me I’m not sure actually. >> ROHINI BALKRISHNA CHAUBAL: hmm >> PDSA POD: No, Wednesday schedule is open session. No. >> ANNAPOORANI MUTHUVEERAPPAN: Okay. >> PDSA POD: Madness tomorrow also you have a >> ANNAPOORANI MUTHUVEERAPPAN: awesome >> PDSA POD: session actually this is extra session actually. because >> ROHINI BALKRISHNA CHAUBAL: so >> ANNAPOORANI MUTHUVEERAPPAN: yeah, so >> PDSA POD: that >> ROHINI BALKRISHNA CHAUBAL: You explained this negative cycle thing on building partner.

 

>> PDSA POD: Sorry, actually actually negative >> ROHINI BALKRISHNA CHAUBAL: just >> PDSA POD: is detected. Please look at here. Sorry, maybe the name could be different. Don’t worry. So just >> ROHINI BALKRISHNA CHAUBAL: not that was billmanford. >> PDSA POD: yes. Yes that one. >> ROHINI BALKRISHNA CHAUBAL: That was Billman Ford. >> PDSA POD: Yes Belmont Ford only because >> ROHINI BALKRISHNA CHAUBAL: It was not. >> PDSA POD: you know my mighty multi Source, it’s not no. It’s a multi-source. It’s not the single Source One >> ROHINI BALKRISHNA CHAUBAL: It was not. >> PDSA POD: Yeah, it is. Okay. Yes. yes. It’s not provided version. Okay. Because cycle only after detector. Yeah. Tomorrow we have a session week six that’s in that scheduled even tracker. It’s there. Even you check it in your word, you know.

 

Maybe in the calendar, it’s there. Yeah, you have that session that is week six. And then on Friday, you have a live coding. That is on week six. >> ANNAPOORANI MUTHUVEERAPPAN: Okay. >> PDSA POD: Okay. Yeah. Yeah. >> ROHINI BALKRISHNA CHAUBAL: Thank you. >> PDSA POD: Please my request. please try to do the practice with the different varieties of graphs. Simple graphs you take it and try to input them and try to do that, you know.

 

So regarding practice programming assignments again, we have a session tomorrow. Definitely if you have any some Edge points, which you don’t understand on practice programming assignments initiate What that particular programming assignments first. Then we can quickly go through that week 6 tomorrow. Okay. >> ROHINI BALKRISHNA CHAUBAL: So week six this your session is there tomorrow? >> PDSA POD: No, I’m not sure whether mine or somebody else. So actually week 6 is definitely it’s there tomorrow. to modernization is there week 6 which is are able to see my calendar. >> ROHINI BALKRISHNA CHAUBAL: Yes. >> PDSA POD: Yeah, it is open session is there. But thing is whether mine or somebody else some that has to be you know, because one particular instructor is not meant for only one course. Sometimes you know, there is a requirement which I supposed to move to some other course something like that. >> KARTHIKEYAN S: This extension will be provided for. coffee >> PDSA POD: I don’t understand please speak. Can you tell me? >> KARTHIKEYAN S: of a week five six >> PDSA POD: hmm >> KARTHIKEYAN S: four week six, basically >> PDSA POD: week 6 >> KARTHIKEYAN S: That can extension.

 

>> ROHINI BALKRISHNA CHAUBAL: submissions assignment submission >> PDSA POD: Ah, yes. Yes. I already noted down this particular one. You said it is Sunday? No. because of our dumping, they are asking for an extension. I’ll just ping it once you just you know, we closed the session. I’ll ping that course lead for an extension. No issues. They’ll do it because the quiz one is also done. no recent quiz one is so due to that maybe definitely they’ll do an extension. I last them not issue.

 

By tomorrow >> ROHINI BALKRISHNA CHAUBAL: So when? >> PDSA POD: you will get the by tomorrow you get the update whether extension will be done it or not. >> KARTHIKEYAN S: And it will be better to get it together. we have or not. more help >> PDSA POD: I’ll request from I said. Okay. >> ROHINI BALKRISHNA CHAUBAL: When will the results of the quiz be announced? >> PDSA POD: Now sign-offs are going on. I don’t know within one or two days I think their results will sign offs are signed on because the faculty has to take the score sheets whether it is telling with you know, the centers which have written. So that is all done. >> ROHINI BALKRISHNA CHAUBAL: cylinders the >> PDSA POD: hmm >> ROHINI BALKRISHNA CHAUBAL: the papers on which we solve the problems. Do they go back to IIT?

 

>> PDSA POD: Okay at TCS ion Center what you are asking about? >> ROHINI BALKRISHNA CHAUBAL: cases >> PDSA POD: no, no, they’ll scrap this one and they’ll you know. It’s going to be scrapping. rough sheets known or rough sheets >> ROHINI BALKRISHNA CHAUBAL: Our rough sheets Our rough >> PDSA POD: doesn’t come to the IIT. It doesn’t come. >> ROHINI BALKRISHNA CHAUBAL: But okay. >> PDSA POD: They are still close of like, you know couple of days they’ll deposit until you know, no discriminate is there right? So they’ll just scrap it.

 

That’s okay. the only certain like one or two weeks. They’ll put it there. If no discriminse, is there just they’ll quit out after announcing result. That’s then. Scrap it they don’t send it. Not like yeah. Sure. >> KARTHIKEYAN S: Have a few minutes for this. >> PDSA POD: Sure. I’ll be yes. >> KARTHIKEYAN S: pdsa section I can >> PDSA POD: Yes, you can you can you you can check you can share you I’ll stop sharing you can share. >> KARTHIKEYAN S: share my screen and >> ROHINI BALKRISHNA CHAUBAL: Okay. >> PDSA POD: Okay, okay. >> ROHINI BALKRISHNA CHAUBAL: Thank you. >> PDSA POD: Yes, >> ROHINI BALKRISHNA CHAUBAL: Thank you, sir. Good night. >> SOWBHAGYA SHRI GOPU: Hello, sir. >> PDSA POD: Yes, yes. >> SOWBHAGYA SHRI GOPU: so I have doubt regarding this placement activity >> PDSA POD: That is you know Ops Team. They know that you better text them. To the operations team because I don’t know when the placements how that is, you know.

 

The earlier process. I don’t know what is. >> SOWBHAGYA SHRI GOPU: They mentioned solving 20 easy-level questions from late for but which >> PDSA POD: Okay. >> SOWBHAGYA SHRI GOPU: don’t be cushions? I don’t. >> PDSA POD: okay, that’s kind of a technical question. >> SOWBHAGYA SHRI GOPU: Okay. >> PDSA POD: I can tell you if you go for the lead code. You better go for a problem-solving one. So you have that, you know different kinds of streams are there. >> SOWBHAGYA SHRI GOPU: Link is this one link is there? If you click that link will go to directly the lead code, but there are more than 20 programs there.

 

>> PDSA POD: Okay. >> SOWBHAGYA SHRI GOPU: We shouldn’t be programs. I have to follow. >> PDSA POD: No, no that is not you know the sequence. It has to be solved you solve the first one second one third one, with which you are comfortable. >> SOWBHAGYA SHRI GOPU: Okay. >> PDSA POD: It’s not like one is definite 2 is definite 3 is definite.

 

No no, that thing is not there. You can solve any 20. >> SOWBHAGYA SHRI GOPU: Any 20 among each easy-level questions. >> PDSA POD: Yes. yes, easily level questions any 20 you might have that 100 or thousand questions. >> SOWBHAGYA SHRI GOPU: Yes. >> PDSA POD: Is there Maybe after solving the first question you might go for directly 11th one you better able to solve it if you focus on the 11th, and no problem. >> SOWBHAGYA SHRI GOPU: Okay. >> PDSA POD: That is for you to know. how to solve problem-solving easily to implement the code that speed can increase and accuracy so will be increased by solving. That’s it. Nothing else, not specific questions. Okay. >> SOWBHAGYA SHRI GOPU: Thank you. >> PDSA POD: Okay. Yeah, yeah.

 

Somebody sharing here Karthikeyan. Yeah. >> KARTHIKEYAN S: Yeah, yeah. >> PDSA POD: Tell me Karthikeyan. >> KARTHIKEYAN S: I’m audible, right? >> PDSA POD: an >> KARTHIKEYAN S: This is the question. I’m not too sure. >> PDSA POD: an >> KARTHIKEYAN S: the struggling with this >> PDSA POD: an >> KARTHIKEYAN S: this minimum cause this is using I’m trying this.

 

I’m getting this output. I’m not able to I’m getting this 900. >> PDSA POD: wait >> KARTHIKEYAN S: I’m not getting >> PDSA POD: ed partner >> KARTHIKEYAN S: path >> PDSA POD: Yes, so just yes. >> KARTHIKEYAN S: So I made a visited >> PDSA POD: Mmm, that’s okay. mmm >> KARTHIKEYAN S: okay this turn and then made a cost and I made the Infinity for all the >> PDSA POD: Yes. >> KARTHIKEYAN S: distance Okay, this is just a friend. >> PDSA POD: hmm >> KARTHIKEYAN S: And then distance the first I choose >> PDSA POD: Okay. >> KARTHIKEYAN S: the first one This is the source. and while visiting I am trying to visit all because everywhere it is eight notes. They have given everything >> PDSA POD: Yes.

 

>> KARTHIKEYAN S: and then make the minimum as the >> PDSA POD: Okay. >> KARTHIKEYAN S: infinity and >> PDSA POD: hmm >> KARTHIKEYAN S: This one is okay. This is >> PDSA POD: waited >> KARTHIKEYAN S: and then now I just try to find the node with the minimum >> PDSA POD: mmm >> KARTHIKEYAN S: which is not in the visited. >> PDSA POD: Okay, okay. That’s okay. >> KARTHIKEYAN S: and distance of that I >> PDSA POD: Yes, you are updating. >> KARTHIKEYAN S: and then the minimum distance is >> PDSA POD: But the part sees the cost you are getting the right value visited value or not. is right. See the two values you have written, you know. >> KARTHIKEYAN S: Yeah, cost customer getting 900. here also >> PDSA POD: yes, the path Associated with the 900 you want it? >> KARTHIKEYAN S: he >> PDSA POD: How did you get this 900 this path is zero to seven seven to six. See just does matter a little bit.

 

Yeah, >> KARTHIKEYAN S: here I cannot. >> PDSA POD: it is zero to seven seven to six six to five that path. You want it? Okay, that’s only pending. No. >> KARTHIKEYAN S: Yes. Yes. >> PDSA POD: Find Jessica just go open your code, please. So here is how you look when you are updating. The distance not visited neighbors offered. See you you take one more, you know the list. So that list of what it contains is always updated. Previous header previous, you know the parent. previous parent value also So >> KARTHIKEYAN S: previous parent >> PDSA POD: ah parent so that that the sequence what it is telling so we are moving that zero to six to two something like two to three you are going no. so >> KARTHIKEYAN S: Okay. >> PDSA POD: that 0 to 6 if you go for it immediately zero is updated the six we have reached by a 0.

 

Fine >> KARTHIKEYAN S: but see >> PDSA POD: vegetative pair and parent is there no you have taken parent. Now we have taken parent. >> KARTHIKEYAN S: yes. >> PDSA POD: Okay, so that parent has to be updated. As and when the minimum cost you identified. >> KARTHIKEYAN S: minimum cost I am making it as >> PDSA POD: Yes. >> KARTHIKEYAN S: yeah. >> PDSA POD: Yes immediately. We are appending its current node. >> KARTHIKEYAN S: Current node, and then the distance of the current node. I’m >> PDSA POD: Okay, that’s a cost is not a problem cost is okay.

 

That’s not a cost is not a problem, But once the cost is updated we have to update the parent of the current node also. so that the parent of that is how to identify because mmm >> KARTHIKEYAN S: that I cannot unless because the current node I’m taking it from here, right? >> PDSA POD: wait, wait, it’s >> KARTHIKEYAN S: parent of the current node >> PDSA POD: it’s in the practice.

 

No. >> KARTHIKEYAN S: Yeah, this is the practice. >> PDSA POD: Just a minute. Just give me a one-time. one second. Because I am opening my side just don’t stop sharing just stay there. >> KARTHIKEYAN S: I’m just going. >> PDSA POD: Is it PPA one or two? Okay. >> KARTHIKEYAN S: This is two. >> PDSA POD: okay. >> KARTHIKEYAN S: One I I trusted and then I I didn’t even. Looking at it. >> PDSA POD: right >> KARTHIKEYAN S: I just closed it. >> PDSA POD: wait There should be a parent who has to be updated. When you update the distance? So you have taken parent, you know parent empty this one. >> KARTHIKEYAN S: Yeah, >> PDSA POD: Wait, wait wait. What you are supposed to do is >> KARTHIKEYAN S: Here we need to visit all eight nodes right >> PDSA POD: Yes, yes.

 

Yes. >> KARTHIKEYAN S: then only we will be able to get the >> PDSA POD: mmm >> KARTHIKEYAN S: My problem here is if you can see the output. My problem is I’m going from 0 to 1, >> PDSA POD: Yes, yes. mmm >> KARTHIKEYAN S: right my 1 is always This is my problem. My Oneness thousand because it is taking this part. It is not getting updated via this five two and one. >> PDSA POD: Yes, it’s parent parent. Every time parent has to be updated. That’s what the thing. Yeah. >> KARTHIKEYAN S: But the algorithm itself has to do right? >> PDSA POD: No, no algorithm itself. It doesn’t do algorithms. What it will do is it will directly 0 to 6 means it tries to find out that 0 to 6. So that final result is what you get it only. >> KARTHIKEYAN S: those are what I’m asking here is leave leave of this parent but algorithm.

 

has to find from 0 to all the nodes the minimum distance >> PDSA POD: Yes. >> KARTHIKEYAN S: right my one minimum distance is not a thousand as per this my one minimum distance should be 900. >> PDSA POD: 900 okay. >> KARTHIKEYAN S: 800 >> PDSA POD: Yes, yes. Okay. >> KARTHIKEYAN S: hundred minus 200 >> PDSA POD: okay, see how did you get it this one? >> KARTHIKEYAN S: Why here thousand is there? I am not able to figure it out also. Because this is what is my >> PDSA POD: No, no, actually you are returning to visit one. Once you go with visited one what happens, you know, the visited one is uh updated, you know, every version updated like first version second version.

 

Keep moving so that every Matrix is displayed earlier. It is a thousand. >> KARTHIKEYAN S: This one is this is this is time. I’m doing it using the first digesters which is >> PDSA POD: Yes the extras only just >> KARTHIKEYAN S: there we are not doing that right we are just visited and then updated the distance we chose the >> PDSA POD: Update the distance. Finally. We return only one value. No, no. >> KARTHIKEYAN S: but the algorithm should make from the start mode to all the nodes the menu distance.

 

It should calculate right? >> PDSA POD: distances >> SANTHIYA AJAY: It’s its works with negative cycles and >> PDSA POD: yeah, it doesn’t work with negative Cycles, but >> KARTHIKEYAN S: Oh, okay. You do not work. >> PDSA POD: Is it negative weights are there? >> KARTHIKEYAN S: Thank you. Yeah, it has a negative. >> PDSA POD: Okay. >> KARTHIKEYAN S: It’s thank you. Thank you. >> PDSA POD: Okay, Yes. >> KARTHIKEYAN S: This has a negative 8 so I should not use this algorithm at all then. >> PDSA POD: Yes, yes. Okay. >> KARTHIKEYAN S: Okay, so when I should use Belmont Ford? >> PDSA POD: Yes, Yes, Bellman-Ford is better. Yes. >> KARTHIKEYAN S: We tried with but at least at this point I was not. >> PDSA POD: Yes. Good point. >> KARTHIKEYAN S: Completely forgot thank you. >> PDSA POD: Yes, >> KARTHIKEYAN S: Thank you, sir.

 

>> PDSA POD: yeah. Yeah. Okay. It’s okay. Yeah. >> KARTHIKEYAN S: It’s one person. Help me. Thank you very much. >> PDSA POD: Welcome welcome. Yeah others, please. Yeah, you can you can. >> KARTHIKEYAN S: Okay, let me try myself maybe tomorrow. >> PDSA POD: Sure. >> KARTHIKEYAN S: Thank you. Good night. >> SANTHIYA AJAY: Yes, I would.

As found on YouTube

ᴛʜᴇ ᴅᴇꜱᴛʀᴏʏ ᴅᴇᴘʀᴇꜱꜱɪᴏɴ™ ꜱʏꜱᴛᴇᴍ – ᴄᴜʀᴇ ᴅᴇᴘʀᴇꜱꜱɪᴏɴ ɴᴀᴛᴜʀᴀʟʟʏ $37.⁰⁰ ᴛʜᴇ ᴅᴇꜱᴛʀᴏʏ ᴅᴇᴘʀᴇꜱꜱɪᴏɴ™ ᴛʀᴇᴀᴛᴍᴇɴᴛ ᴘʟᴀɴ ̶$̶7̶4̶ $37.⁰⁰ ᴄʙᴛ ᴡᴏʀᴋʙᴏᴏᴋ ᴀɴᴅ ᴛᴏᴏʟꜱ ̶$̶6̶7̶ ꜰʀᴇᴇ ɢᴏᴀʟ ꜱᴇᴛᴛɪɴɢ ᴡᴏʀᴋꜱʜᴏᴘ ̶$̶2̶9̶ ꜰʀᴇᴇ ᴛʜᴇ ᴅᴇᴘʀᴇꜱꜱɪᴏɴ-ꜰʀᴇᴇ ᴍᴇᴅɪᴛᴇʀʀᴀɴᴇᴀɴ ᴅɪᴇᴛ ̶$̶3̶7̶ ꜰʀᴇᴇ ꜰʀᴇᴇ ʟɪꜰᴇᴛɪᴍᴇ ᴜᴘᴅᴀᴛᴇꜱ ̶$̶1̶4̶7̶ ꜰʀᴇᴇ ʏᴏᴜʀ ᴅᴇᴘʀᴇꜱꜱɪᴏɴ ʜᴀꜱ ʙᴇᴇɴ ɪɴ ᴄᴏɴᴛʀᴏʟ ʟᴏɴɢ ᴇɴᴏᴜɢʜ. ɪᴛ’ꜱ ᴛɪᴍᴇ ᴛᴏ ꜰɪɢʜᴛ ʙᴀᴄᴋ ʟᴇᴛ’ꜱ ɢᴇᴛ ꜱᴛᴀʀᴛᴇᴅ ➫ “ᴛʜɪꜱ ᴅɪᴅɴ’ᴛ ᴊᴜꜱᴛ ᴄʜᴀɴɢᴇ ᴍʏ ʟɪꜰᴇ, ɪᴛ ꜱᴀᴠᴇᴅ ᴍʏ ʟɪꜰᴇ.” “ᵈᵉᵖʳᵉˢˢᶦᵒⁿ ʰᵃᵈ ˢᵘᶜʰ ᵃ ˢᵗʳᵃⁿᵍˡᵉʰᵒˡᵈ ᵒᵛᵉʳ ᵐʸ ᵐᶦⁿᵈ ᵗʰᵃᵗ ᶦ ʷᵃˢ ᵈʳᶦᵛᵉⁿ ᵗᵒ ᵃᵗᵗᵉᵐᵖᵗ ˢᵘᶦᶜᶦᵈᵉ ᶠᵒᵘʳ ᵗᶦᵐᵉˢ. ᵈᵉˢᵗʳᵒʸ ᵈᵉᵖʳᵉˢˢᶦᵒⁿ ʰᵉˡᵖᵉᵈ ᵐᵉ ᵍᵉᵗ ᵇᵉʸᵒⁿᵈ ᵗʰᵉ ᵈᵉᵖʳᵉˢˢᶦᵒⁿ ˢʸᵐᵖᵗᵒᵐˢ ᵗʰᵃᵗ ʷᵉʳᵉ ʰᵒˡᵈᶦⁿᵍ ᵐᵉ ʰᵒˢᵗᵃᵍᵉ. ᵗᵒᵈᵃʸ, ᶦ’ᵐ ᵗᵉᵃᶜʰᶦⁿᵍ ᵒⁿˡᶦⁿᵉ ʸᵒᵍᵃ ᶜˡᵃˢˢᵉˢ, ᵇᵘᶦˡᵈᶦⁿᵍ ᵃ ᵍᵃʳᵈᵉⁿ ᶦⁿ ᵐʸ ᵇᵃᶜᵏʸᵃʳᵈ ᵃⁿᵈ ˢᵖᵉⁿᵈᶦⁿᵍ ᵗᶦᵐᵉ ᵃᵗ ᵗʰᵉ ˡᵃᵏᵉ ʷᶦᵗʰ ᵐʸ ᵈᵒᵍ, ᵉᵈᵈᶦᵉ. ʰᵃᵛᶦⁿᵍ ᵐʸ ᵈᵉᵖʳᵉˢˢᶦᵒⁿ ˢʸᵐᵖᵗᵒᵐˢ ᵉᵛᵃᵖᵒʳᵃᵗᵉ ᵃᶠᵗᵉʳ ᵃ ˡᶦᶠᵉᵗᶦᵐᵉ ᵒᶠ ˢᵗʳᵘᵍᵍˡᵉ ʰᵃˢ ᵇᵉᵉⁿ ᵃᵐᵃᶻᶦⁿᵍ.” ᴇʟᴇɴ ʀ. ᴍɪᴄʜɪɢᴀɴ, ᴜꜱᴀ