So if you need anything, you have any questions, feel free to communicate with the host and panelists in the chat. So my brother, I will be able to see and respond. But before we get started, I wanted to congratulate all of you, very exciting for your excellent performance on the Math Kangaroo. Without further ado, I'll introduce myself. So hi guys, I'm Ms. Haripriya. I completed my bachelor's and master's in four years in electrical and engineering and computer science at MIT. My graduation year was 2020, but because of the pandemic, my graduation ceremony was delayed. So I actually did the graduation walk last weekend in Boston. So I'm also co-founder of MetaPlus, which is an educational organization for middle school and high school students. That's sort of my side hustle. My full-time job is a software engineer at Microsoft, and Math Kangaroo holds a special place in my heart. And I'm really excited to talk to all of you today because I have placed top 10 nationally before. Hi everyone, I'm Bhagirath, I'm Haripriya's brother. I've also participated in Math Kangaroo, placing first place internationally twice with the perfect score. I'm currently pursuing my BS, my bachelor's in electrical engineering and computer science, as well as my master's in computer science, and will be graduating in a week. I'm a co-founder of MetaPlus tutoring as well. And in the past I've interned at Amazon and Microsoft, and I'll be graduating to work as a software engineer and data scientist at a startup. Excited to meet you all. Awesome. So graph theory is our topic today. Graph theory is the study of graphs. Graphs are essentially vertices or nodes connected by edges. So these yellow circles are our vertices and our nodes, and they're also called nodes. And our edges are these green lines between these vertices slash nodes. So vertices, nodes, and edges. A path is when vertices and edges are not repeated in a graph traversal. So an example of a path would be we start at this node, we go to this node, then we go to this node, and then we go to this node. We didn't repeat any of the vertices or the edges, so this is called a path. A cycle is a closed path, on the other hand, where you do repeat the vertex. Your starting vertex is your ending vertex. So let's say we start from this node, we go to this node, then we go to this node. We go back to the node we started from. And since that's a closed path, it's called a cycle. A neighbor is a vertex adjacent to another vertex. So for example, these two nodes are neighbors because they're connected by an edge. These two nodes are neighbors because they're connected by an edge. But these two nodes are not neighbors because there is no edge between them. There has to be this edge, this green line between them. So this is all cool and all, but what are the applications of graph theory? So graph theory, as we're going to talk about today, is used in a variety of fields. Social networks, you know, any sort of social media you're on, the connections between you and your friends. Graph theory is a great way to symbolize that. Lexical semantics, or basically linguistics, you know, how words are related to one another in a sentence. Finding circuits, you know, where do the resistors go, where do the light bulb go? That's all in the realm of graph theory. Finding routes, you know, how to get from point A to point B by looking at a map, trying to find that shortest route. Chemical and biological pathways, you know, trying to map out the chemical reactions happening in the human body. That can also be an application of graph theory. And then timetable scheduling. So if you have a few tasks to do and some tasks are dependent on some other tasks, you know, what order do you do these tasks in? So these are all really cool applications of graph theory. There are three questions that I want you to remember through the course of this presentation, as well as any graph theory problem you do in the future. And I assure you, graph theory will, no matter what major you're in, no matter what your careers, at some point, you know, graph theory will come into your lives. And it might be, if you're on social media accounts, for example, then it's coming into your lives every single day. So there are some questions that you need to remember when you are working with graphs. And that's what do nodes represent? Nodes again, are these nodes or vertices, are these yellow circles, A, B, C, D? What do these edges represent? What do these green lines represent? And how do we traverse this graph? Or simply put, how do we get from point C to point D, for example? So these are the three questions. What do nodes represent? What do edges represent? And how do we traverse the graph? Oh, wow, it's already quiz one time. So see if you can try to answer this quiz. If for some reason, the Zoom quiz function is not working, maybe you're on a Chromebook, please feel free to give the answer in the chat. Mr. Bagheerat will also copy paste the question. And we will count that for the score if you are unable to. But if you can, then please answer the quiz question through Zoom quiz. And so the question is, and you'll have one minute to answer, how are neighboring nodes connected? By a vertex, by a circle, by an edge, or by a cycle? And we are seeing some answers in the chat. So thank you. We will count that. Mr. Bagheerat will paste that in an Excel document, so it'll be easy for me. And I'm really liking the answers so far. So we have five-ish more seconds. And we have like 10 people left. OK. One more second. There's some people still answering. I'll do, oh, there's even more. Okay, I think I'm going to wrap it up. And I'm really, really happy with all the answers. I think every single person got it correct. Awesome. It is by an edge. It is by that green line. Can you see the correct answer on your end, by the way, if you can let me know in the chat? Okay. Oh, some people are saying no. It's not a huge deal. I'll just verbally... Oh, it only shows you. Let me try it again. Let me try again. Share results. Maybe since you did it right, maybe that's why it's showing the same thing. I'm not entirely sure, but I'll verbally say it in case you can. Oh, it works now. Awesome. Okay. The correct answer indeed is by an edge. Cool. So I'm going to stop sharing now and let's continue. Oh, we have a raised hand. If you have any questions, if you can please put in the chat. And I will move on. Oh my, oh my, oh my God. Oh my God. I am so sorry. I hope you guys don't mind if I take this. Hello? Dr. Roo? I'm in the middle of a presentation. I can't... You want the Math Kangaroo students help? Just because you're the Math Kangaroo mascot doesn't mean you can walk in here anywhere and do anything. Fine. Fine. You know what? I mean, I had a great graph theory presentation to give, but you know what? I guess what you want is more important. So yeah, whatever. Yeah, sure. Yeah, okay. I am really sorry, guys. I was so excited, but well, Dr. Roo is this crazy friend of mine, also the Math Kangaroo mascot, and he wants your help. He says he's part of a documentary. He has some videos and he really needs your guys' help because you guys are really smart. So let's just watch that. I'm really sorry, you know, we can't talk about graph theory any longer. Since the dawn of time, man has wondered, where do we come from? What are we? Where are we going? Despite many technological innovations of the 21st century, the mysteries of the universe seem to be as elusive as it did in the Stone Ages. But some in the mathematical community disagree. Mathematician Dr. Roo believes that we are actually farther from the truth than our forefathers were. There is no doubt in my mind that our forefathers had discovered the answer to the ultimate question of life, the universe and everything. And no, it wasn't 42. The truth was simplified in a single mathematical equation, carved on a stone known in popular culture as the MacGuffin Stone. So this stone, where is it? No one knows for sure. It is believed that the stone has been locked up and hidden away because our forefathers worried that if the stone were to get into the wrong hands, it would wreak havoc in the universe. Has anyone come close to finding it? Many have tried and many have failed. Legend has it that anyone who has come close to finding the stone has perished in the intricate booby traps surrounding the stone. That doesn't deter me though. Wow. Knowing that the mission to find the stone has been unfruitful so far, why are you bent on discovering it? There are many people searching for the stone. I believe the stone will eventually fall into the wrong hands if the mathematical community does not get a hold of it before someone else does. Time is running short, my dear friend. Okay. And Dr. Rue has sent me another video as well, explicitly asking for your help. Hello, students. I need your help. I was researching the McGuffin Stone when some old yellowed paper, written in the ancient language of Rothenian, fell out. I do not understand it, but I'm certain it carries the secret of where the stone is and how to get to it. Your mission, should you choose to accept it, is help me find this stone. Your first task is to find Professor Draco Hamilton, an eminent scholar who can translate this text. I do not know the professor personally, so we must make contact through friends. Perhaps Professor Hamilton is a friend of a friend of a friend. Remember, friends, time is running short. Okay. So you all understand the mission, right? We wanna find the shortest path between Dr. Rue and Professor Hamilton, because maybe Dr. Rue has a friend who can make a connection with Professor Hamilton so he can translate this Rothenian ancient scrolls. So Dr. Rue was kind enough to give his social media to META. I don't know if any of you are on it. I hear it's like the coolest social media network. But yeah, this is the network in his sort of friend circle and friends of friends circle. So you can see here, Dr. Rue is friends with me and Ms. Paz. I am friends with Ms. Paz, Ms. Marva, Mr. Benjamin and Dr. Rue and so on and so forth. I am not friends with my brother, of course, because, and I'm seeing some great answers in the chat already. I'm not friends with my brother, of course, because it's very uncool to be friends with your brother. So I guess my question is going back to, and I know some of you already know some of this. So going back to sort of the three main questions I asked at the beginning of the presentation. What are the nodes? What are the edges? And what are we traversing? So before we get to answers, because there are some cool things I'd like to teach you. I'm sure you guys can calculate it yourself, but we'll talk about why there might be better ways. What are the nodes? What are the vertices? Let's first answer that question in the chat. What are the nodes? And this will go faster if people respond in the chat. So, those are the people or the animals or whatever. Yeah, perfect. Yeah, so all of these are nodes, right? It's not just one person. All of these are nodes. And then what would the edges represent if we were to create a graph using this? And I'm really excited that now we can use graph theory on this. Yeah, the friendship connections, the connections between the two people. Perfect. And what's sort of the graph traversal? What's the question here that we wanna answer? Who are we traversing between? And all of you guys have such great answers. Yeah, a chain of friends from the kangaroo to the dragon, exactly, Dr. Roo and Professor Hamilton. So, to save your time, I have created the graph for you. So, here are all the nodes. And then here are the edges, as you can see that it matches with this adjacency list that I had over here. So, Dr. Roo is friends with me and Ms. Paz. And so, you can see that being reflected. And then I'm friends with Ms. Paz, Ms. Marva, Mr. Benjamin, Dr. Roo. And you can see that being reflected here as well. So, Ms. Marva, Ms. Paz, Dr. Roo, Mr. Benjamin. Okay, so now let's get started. We do wanna try to find the shortest path. And some of you have already been giving me the shortest path. But think about real social networks, right? There are hundreds and thousands of nodes. So, trying to sort of just come up with some sort of method by hand is probably not the smartest way of doing it. We would want a computer to solve the problem for us. And what computers need is an algorithm or a process or set of rules to be followed. So, we'll need to use an algorithm for this. And as many of you know already, which is fantastic, the algorithm we are going to use is breadth-first search. If you're not familiar with it, totally okay. That's what we're going to cover. So, for breadth-first search, what we do is we start from a node and we explore all nodes at a certain depth before moving to nodes at the next step. And breadth-first search uses a data structure called queue. And queue works the normal way any queue would work, right? When you're standing in line, the first person who's in the queue is the first person who's out of the queue. And so, that's FIFO, first in, first out. So, let's run breadth-first search on this. We're going to go slow this first round because some of you may not be familiar with it. We're going to start here at Dr. Roo, right? As all of you said, we want to find a path from Dr. Roo to Professor Hamilton. And what I've done here is I made Dr. Roo like the border, like a pink halo around it, which means that it's a visited node. Once we see it, it's visited node. And what we're going to do is we're going to put it into our queue, which you can see on the left-hand side here. So, let's put it onto the queue. We push it into the queue and then we're going to pop it out, right? First in, first out. We pop it out. And now the next thing that you are going to push into the queue are Dr. Roo's neighbors, right? So, Dr. Roo's neighbors are Ms. Haripriya. And, oh, it's already quiz number two time. So, what, let's pull this up. Quiz number two. Okay. So, besides Ms. Haripriya, who's Dr. Roo's neighbors? Okay. And I'll read the answers also. Mr. Benjamin, Professor Hamilton, Ms. Paws, and Dr. Roo. Also, if you already answered the question, I'm curious for the people who know breadth-first search, where you would have learned it. Was it a math class you took in high school or like an outside math, or you just learned it on your own if you already answered the question? Oh, AP Computer Science. Interesting. I did take that class and I wonder if we learned it. The curriculum might've changed, but cool. Oh, someone's dad told them about it. Some course of knowledge, USECO. Oh, okay, fantastic. I guess then I'll ask you more questions since we're already done here. Perfect. We have, I think 100% got it right, including the chat results. Ms. Paws, as you already know, Ms. Haripriya is a neighbor of Dr. Roo as well as Ms. Paws. So, I'm not gonna explain it much more than that because I think you guys get it. Let me close this. Okay. So, now we push both of these into the queue. So, now what happens next? Who is first in the queue? And this is a question you can answer in the chat. Yeah, me, Ms. Haripriya. Perfect. So, oh, oh, it's just creeping on me, these quizzes. Okay, quiz number three. Which vertices are neighbors of Ms. Haripriya and have not been visited yet? Dr. Roo and Ms. Paws, Ms. Paws and Ms. Marwa, Mr. Benjamin and Mr. Begirth, Ms. Marwa and Mr. Benjamin. I'm actually happy because now it's not 100% correct, which I shouldn't be glad, but I'm glad that I'm tripping some of you up now and the questions are getting harder. It's a two-part question, right? Which vertices are neighbors of Ms. Haripriya and which have not been visited? OK, I'm going to end the poll here, and I'll share the results. So we didn't get 100% accuracy. Pretty close. Most of you got it. The other answer some people said was Miss Paws and Miss Marva. So Miss Paws is a neighbor of Miss Haripriya, as is Miss Marva. So you are correct about that. But Miss Paws has already been visited. She has already been added into the queue. So the correct answers are actually Miss Marva and Mr. Benjamin, because you see that there's no pink halo around them, so they haven't been visited. They haven't been put into the queue yet. So those are the things we're going to put into the queue next. OK, awesome. OK, so Miss Marva and Mr. Benjamin. So we're going to put this into our queue next. Now, what's our next step? Who are we popping out of the queue? Who are we pushing in? And this is a chat question. OK, I'm getting, who are we popping? Who are we taking out of the queue? Who's first in the queue? I guess that's my first question. Yeah, I'm seeing. Well, I'm no longer in the queue, right? I've already been kicked out of the queue. I've been popped out, so to speak. So right now, in this queue, and we look from the bottom up, Miss Paws is the first in the queue. So we're going to pop Miss Paws, and we're going to put Mr. Begirith in. OK, because Mr. Begirith is the only unvisited neighbor of Miss Paws, which most of that's what you are saying. So awesome. OK, what next? Quiz time. Quiz time. So let us. Which note do we add to our queue next? Once we pop out Miss Marva. Mr. Viscous, Miss Paws, Miss Ghosty, or Miss Marva? And by the way, if you're finished answering, I'd really like to know, what languages do you already know programming in? If you don't know any, that's perfectly cool. You can let me know that in the chat as well. 15 more seconds. OK, I'm seeing some answers. Oh, Fortran and Assembly, wow, way to go. Python, HTML, CSS, JavaScript, Python, and a smidge of C++. Python, anyone never coded before? 10 seconds. Python, Pascal, C++, Python, Java, HTML, SQL, C, wow. Python and some Java, or HTML, CSS, JS, and Python. Perfect. OK, I'm going to end the poll here. LaTeX, yeah. Python and some Java. I'm going to end the poll here. So most of you did get it correct. You got it wrong, no worries. When Miss Marva pops out, we have to put a neighbor of Miss Marva. And there is only one unvisited neighbor of Miss Marva, and that's Miss Ghosty, because she's connected to Miss Marva by an edge. Mr. Whiskers is not connected to Miss Marva, so we can't put Mr. Whiskers in just quite yet. Um, do we ever keep track of how many edges have already been traversed? So we are keeping track of the vertices that we are visiting. So that kind of shows what edges are being traversed. But I think your question might be, how do we know which edge is being traversed? And that's a great question. Here, I'm just keeping track by making these blue-purple lines, depending on which level they are. But in the code, when I show you the code, you'll see how we are keeping track of these edges. So great question. And if I didn't answer completely your question, please feel free to rephrase it or let me know if that made sense. OK, cool. So yeah, so as we said, oh, no, no, no, what happened? No, OK. We pop out Miss Marva. We put in Miss Ghosty. Now we can answer in the chat. What's next? What do we do next? OK. Yeah, so we pop out Mr. Benjamin. And then what happens? Does Mr. Benjamin have any neighbors, unvisited neighbors? No, he doesn't. So then what do we, who's next in the queue once we have popped Mr. Benjamin out? And I'm seeing a lot of right answers. Yeah, Mr. Bagheerat is there. So now does Mr. Bagheerat, we pop Mr. Bagheerat out, does he have any unvisited neighbors? And yes, I'm seeing the correct answers, Mr. Whiskers. So let's just take a look at that quickly. I think you all are getting the hang of it. So you see Mr. Benjamin being popped, Mr. Bagheerat being popped, and Mr. Whiskers being added in. Now what's next? Tell me the rest of what's going to happen. Who's getting popped? Who's getting pushed in? Tell me all the orders. Yeah, I know some of you are tempted to use the word skip. We aren't really skipping any individuals, right? We're still popping them out. And I know I'm being picky with the verbiage. We aren't skipping them. It's just that they don't have any unvisited neighbors. So then there's nothing else we can do. But we are popping them out. So we're not completely skipping them out, yeah. Which I think you already understand, but just to be clear. Okay, perfect. I'm seeing a lot of right answers. So we pop out Ms. Ghosty, because Ms. Ghosty doesn't have any unvisited neighbors. That's it. Then Mr. Whiskers is next in line. Mr. Whiskers does have an unvisited neighbor, and that's Professor Hamilton. And so now we have reached him. Okay, cool. Great work. And I'm seeing a lot of correct answers in the chat. So I'm really happy. So what I did over here is I collapsed this graph, and I just took these edges that we did traverse, and I put them here. And so as you can see, there's only like one path between any sets of nodes. And so Dr. Roo in this first level, Ms. Haripriya and Ms. Pauls were visited. And what I'm going to do is I'm gonna start the animation on the side. This is basically everything we saw so far, what happened. Dr. Roo gets pushed and then popped, and then Ms. Pauls and me are being pushed. And then once we're being popped, other people are being added. And so this is at each different level. What we call this is a tree structure, where this top part is the root and the bottom part are leaves. It's sort of like an inverse physical tree that you would see outside. Yeah, and it's a binary tree, someone said. So yeah, fantastic. I love all this computer science terminology. So now can someone tell me, looking at this structure, now we've sort of simplified this very ugly looking graph. What is the shortest path between Dr. Roo and Professor Hamilton? Shortest path. Who should Dr. Roo be contacting? Who should be contacting someone else so that we get to Professor Hamilton? Yeah, I'm seeing a lot of right answers. Roo, Pauls, Begirath, Whiskers, and Hamilton. Indeed. So you know what I'm going to do is I am going to, and also I'm getting a lot of correct answers. I'm going to send this list to Dr. Roo. He can start contacting his people. What I wanna show in the meanwhile, while he's trying to make contact is, I wanna show you the breadth-first search code. So let us, let me do a new share here. And please let me know in the chat when you can see this. Can you see the Colab? Yes, okay, cool. There's a question of how do we make sure breadth-first search is optimal? So you are always getting the shortest path. And at the expense of going too much into proofs and all, I'm sure you can prove it, but you are always at each level, you are finding the shortest path. So you know that when you get to Professor Hamilton, it is the shortest path. We are ignoring any longer paths, right? When we are talking about visited nodes, we don't revisit a visited nodes, which is why breadth-first search is optimal. So over here, since you all are computer science geeks, we have an adjacency list. It's very similar to the diagram I showed you where I showed who were whose friends. So you can see Dr. Roo is here, friends with Ms. Haripriya and Ms. Paz, and you can see my friends. So this is what we call an adjacency list. This is what we use for breadth-first search normally. I have a set, and this is in Python, by the way. I'm sure most of you are familiar, but nonetheless, we have a set of visited nodes. You know, the visited in our diagrams, I sort of showed it with that pink hallow, but in Python, we would show it using a set. We have a queue, which is essentially an array. Since it's Python, we don't need to do anything complicated. And a parent dictionary. So one question we had was, you know, how do we keep track of these edges? That's an excellent question. This is sort of what I had created to keep track of that, and that's parent dictionary. So that means that for each node, we will see which is the node it came from. What is the closest node to that that it came from when we were doing breadth-first search? And this is one way to do it. There are multiple breadth-first ways to implement breadth-first search in Python. This is the iterative way. So you see the while loop. First, we add our starting node to the visited set and our queue array, and then we keep on going through this queue. We keep on popping things. And if it's not in our visited set, we push it to our queue. And then we add that to our parent dictionary. So exactly what we were doing, but now in code. And so now, order of visiting nodes. So this was the order we visited them in, and that exactly matches what we had done. You know, we first went to Roo, then Haripriya, then Paul, so on and so forth. And then this last part, of course, is we want to find the shortest path, right? We don't just care about which nodes were visited. And so I used this parent dictionary that I had created up in the top to sort of find the shortest path. And this will give us Roo, Paul, Bagheer, the Whiskers, Hamilton, exactly as one would expect. Cool. Let me know if you have any questions about that. Otherwise, I am going to continue on with the slides. So applications, oh, what's a set? That's a great question. So a set is a data structure. Basically, it's an unordered collection of things. So if, let's say, I created a set of nodes that had me and my brother, the order wouldn't matter. It would just be like, oh, I'm there and my brother is there. How does a dictionary work? A dictionary is basically a key mapped to a value. So let me put this in the chat. Let me give you all an example. So let's say I'm going to write my name and I'm going to say what my T-shirt color is, which is blue, or I'll say gray. I have a gray sweater on, and then I will put my brother's T-shirt color, which I think is blue, here. And so this is what the dictionary would look like, right? I'm mapping me to my clothes color. So there's a key, Haripriya and Bhagiratha are keys, and the colors are the values. So there's this one-to-one mapping, exactly. Okay, cool. And you can map a lot of things, right? It doesn't have to be a string. You can map a list. You can map a lot of things, but this is one example. Okay, breadth-first search applications. So as we see social networks, you have hundreds and thousands of node and trying to traverse all that. Breadth-first search is a great way to do it. It is the optimal way of doing it. Fraud detection. So I have interned and worked in several large tech companies, many of which you would be familiar with and use their products on a daily basis. And what happens in the realm of fraud land, or we call frauds bad actors, what they do is they create a bazillion, like hundreds and thousands of accounts of something. They create it for free, and then they sell it on the black market. They sell it on the black market and they make money, and that's a loss to the company. How do you know that there's only one person has collected a bazillion different accounts? Well, we can see that maybe there's something related, maybe they're using the same credit card number or same phone number. There's something connecting these hundreds and thousands of accounts. So we know it's not hundreds and thousands of people creating it. It's just one bad guy creating all these accounts. And the way we would solve this problem is through breadth-first search, trying to find these connections between different accounts. There's an edge if there is something in common like a credit card or a phone number. If you do have to leave early, I see one question about it. You will be able to see the questions later. The presentation is recorded, so you will be able to access that, and I or Math Kangaroo will share that with you. So yeah, don't worry about it. You won't miss anything. Search engine crawlers is also another way. When Google is trying to, or any other web engine is trying to index different websites, what they see is the hyperlinks in the website and see what these hyperlinks are connected to, like which websites are all connected. So again, that's another application of breadth-first search and graphs. Okay, so I just got a text from Dr. Roo saying that he was able to make contact with Professor Hamilton, and he has another video for us to watch. Okay, so hopefully we understood that, you know, the translated documents have been sent to us by Dr. Rue. So there are two caves, right? One of the cave has the key, the other cave has the treasure chest. And so the first thing we need to do is we need to get to the key. And I don't know if any of you are fans of Indiana Jones, but I am legitimately scared of caves and the booby traps. Like there's boulders running around. There's like stray arrows. So what we want to do is we want to make sure Dr. Rue is not caught in the crossfire of all that. And we want to make sure that we follow these instructions that we have and we get the key. Right. So here are some of the instructions. I won't read all of them, but you can definitely read it to yourself. Lever G must be pulled only if lever G should be pulled only if stone A is pressed. Stone B should be pressed only if lever G is pulled. And there's all these other other rules. And then the last rule is all lever stones blocks must be handled with once and only once. So we have we have the set of rules and we want to find an ordering. Right. So I think this can also be a graph problem. What are the nodes? What are the edges and what are we traversing? And please write that in the chat. What are the nodes? We're trying to get this key. We have all these rules that we have to follow or Dr. Rue gets hurt. So A, B, C, D, H, all these are nodes. Not so much, I think the states, but yeah, basically these blocks, levers, stones, you know, and trying to get to that states will be a little different. We'll talk about what states represent. I think states is more like visited, I think. And then how how are these connected? Like what do that what would the edges represent in such a graph? And I have I see some good questions that, yes, I'm not going to answer it right yet because I'm going to talk about it in the next slide. But, yeah, these rules are the edges that they have to be pulled only if a certain thing is pressed. Right. And then what's what's what are we traversing? Like what's the goal of this? Yeah. And I'm seeing DNA should be connection connected. Get to H is part of it. Right. We need to get the key, but we need to also follow all of these rules. Right. Yeah. Going through all the edges and vertices with no repeats. Right. Exactly. Cool. So we have to make sure we get the key. We make sure we follow all these directions so that each of the levers, stones and blocks are handled with once and only once. Should we work backwards? That's a great question. Someone also said something about directed edges. That's also a great question. So let's talk about that. Directed edges. Here's a new vocab term. So far, we have been working with edges, but I didn't introduce this term. And this means that an edge where you can traverse only in one direction. Right. So far, the edges we were talking about, you can traverse in either direction and it didn't matter. In this case, A, you can only go to B. It's like a one way path, but you can't go the other way around. So that's a great call out. Someone said that. Do we need directed edges for this? We do. Right. The order really does matter. Topological sort is a linear ordering of vertices. You know, what's the first action you do? What's the second action you do? So on and so forth. And you can only have a topological sort on a graph if you're working with directed graphs, meaning it has directed edges and it's a cyclical, meaning there are no cycles. There are only paths. And the algorithm, and please let me know in the chat if you've ever worked with this algorithm before, the algorithm we're going to use for this is depth first search. So let me know if it's new to you or you already are familiar with it. For depth first search, you start from a node and explore a branch as far as possible before backtracking. It uses a data structure called stack, which operates a little differently from Q. Q was what? What was Q? Was it last in, first out, first in, first out? Yeah. FIFO. It was first in, first out. Stack works differently, where it's last in, first out. And then what we're going to do is the topological sort can be obtained from the depth first search once you reverse the order in which the vertices are popped out of the stack. So someone had the question, should we work in reverse? 100%. Exactly. That's what we're going to do here. And again, I'm sure that you can solve this problem by yourself, but let's do it methodically. Because again, if you have hundreds and millions of nodes, as you often do in industry or in research in real life, you would need to use this algorithm. OK, so just to refresh, I've just kept these rules to refresh your memory. And I will create this graph for you so that it saves our time. The graph essentially looks something like this, right? These nodes are each of these lever stones blocks. And there are directed edges that follow these rules, like lever G should be pulled only if stone A is pressed. So you have an arrow between A to G, because G can only happen after A. Stone B should be pressed only if lever G is pulled. And so we see that where you have an arrow between G to B, directed edges only. OK, now let's get started. Remember, we're going to break any ties or do anything alphabetically. That is the standard procedure, because there can be many orderings. But in order to make sure that, you know, if we were all doing this separately, we have a consistent ordering in computer science, we break ties alphabetically. I'm going to start with A because there are no edges coming in, so it's really not dependent on anything. So let's just start with A and let's see. So we put A into our stack. Our stack is on the right hand side. And then we check. We don't pop anything out yet, but we're going to check out what its neighbors are. So what are its neighbors and which one do we put in the stack first if we are working alphabetically? What are we pushing into our stack? Yeah, we're going to first put B. So we put B. Now, what we're going to do is we're going to pop out B, right? Last in, first out. We're going to pop out B. And the reason we're popping out B is because does B have any neighbors? Any unvisited neighbors that you can go with using a directed edge? No, B doesn't have any neighbors that you can visit. There are no outgoing edges from B. And that's why we're going to pop out B. So you only pop something out of a stack once you have exhausted all the possibilities. So we're going to pop out B. And then what we're going to do is we're going to backtrack, right? So what's still remaining in our queue or in our stack? Apologies, stack, stack, stack, stack, stack. A, yeah, A is remaining in our stack. So what I call this action, you know, it's called backtracking. So once you've exhausted the possibilities, go back, you go to A. And does A have any other neighbors? And I'm already seeing the answers. Yeah, A has G. So we're going to go to G. So let's do that. So you can see we popped out B and we put out G. Now, what's next? Does G have any unvisited neighbors when we are having outgoing edges? So I see one, B. B is already visited because it's because I made this orange, right? It already was in the stack. So basically, there's nowhere to go. We're stuck. So what's the what do we do now? Now that there's nowhere to go? I'm doing the fancy my well, yes, some you guys have the right node. But before that, yeah, you backtrack, right? You pop it out, you backtrack and you go back to A. So once you go to A, is there any place to go? And I know you guys are already ahead of me, but I just want to work this step by step. No, there's not. So now you have to go to the next node, which as many of you are saying, I'll give a chance for those of you haven't written in the chat yet. What's the next node? C, exactly. Perfect. Awesome. So now we pop G out, we popped A out and we push in C. Now what's next? Walk me through this. What do we do? Do we pop C out yet or does it have any unvisited neighbors in the outgoing edges? Yeah. We have F, right? Why not H? Why can't I put H in? Or should I? Alphabetical. Perfect. We are breaking ties alphabetically. So we put in F next. So we put in F. Now what's next after F? Perfect. H. So we put in H. And what you saw there is that we popped it out because when we does H have any outgoing edges that are unvisited? No. So we backtrack, right? We backtrack to F. Does F have any outgoing edges that are unvisited? No. Yeah. And then we backtrack and we go to C. C also doesn't have anything. So now it's quiz time. So now that we have popped out H, F, and then C, what is next? So let me launch this quiz. Which element will be added to the stack next? F, E, C, or D? And if you're already done answering, no one answered my previous question of is Depth First Search new to any of you or have you all covered this before? I know breadth first search was something you guys had covered a lot of times. OK. Dad told them only in the context of trees. OK. Part of it, but don't know the specifics. OK, cool. And 15 more seconds. Long time ago. OK, so this I think we're getting newer stuff. And I think hopefully fingers crossed the next algorithm will cover that will be completely new. OK, and I will end the poll here. OK, and I'll share the results. Most of you got it. It's fine if you didn't. So, yes. So which element will be added to the stack next? The answer is D. F we already added to the stack, right? When you're visiting nodes, we're not going to re-add them. So what happened with H is when we popped out H, we backtracked to F. We popped out F after backtracking, and then we backtracked to C. And so we popped C out. So now there's only two nodes essentially that are unvisited. And alphabetically we go. So that's why D is the answer. If you didn't understand that, then let me know in the chat and I can explain it again. Cool. No, I'm sorry. I had a question about what is the algorithmic complexity? The algorithmic complexity, I wasn't planning to cover this, but it's because I'm sure not everyone knows, but it is just vertices plus edges is the algorithmic complexity. Yeah, cool. So you know what? I am going to, sorry, we're not done yet. I'm just like, woo, we're done. You guys are doing such a great job. I'm just like, we're done. But D, and then after D, what do we do? We pop D out because there's no other outgoing edges. Yeah. And thank you, Mr. Bagheera. For BFS and DFS, it is both similar, both same. It's the vertices plus edges. If you don't know what the algorithmic complexity is, don't worry about it. But after we pop out D, what's next? Are we done or is there anything more? Yeah, we push an E and we pop an E and we're done. Cool. So now we have visited all our nodes. And so this is just a quick animation. And so each time I pop it out, I have written it down like HFCDE. OK, and if you pop it, if you write it down every time you pop out a node, this was the order we popped nodes out and B, G, A, H, F, C, D, E. So is that the order in which we visit the node? No. Right. Which order do we visit the node? I don't know why I'm dancing. Yeah. Reverse backwards. Yeah, exactly opposite. So we'll go E, then D, then C, then F, then H, and A, and G, and B. OK? So I'm going to send that to Dr. Roo so he can get on a plane to Zakopane. That shouldn't work either. Can you mention to me why it shouldn't work? While you write down that description, I'll show the code. Yes, I can definitely share the code with you after the thing, because I will have your email addresses. So I can share the code if you are interested. But let me do a new share. And I'll explain this. And maybe if there's any confusion, we can understand. The computer does agree with me, so maybe that's a good thing. But then again, I did write the code, so can you really believe it? Anyway, this is the adjacency list again. There needs to be the order A to G to B. Let me go back to the PowerPoint if you want to see the rules again. A to G to B. Oh, so it says that that's what we are doing, A to G to the B, right? Because we're starting from the end, E, D, C, F, H, A, G, B. So you are correct. We are following that order. Does that make sense for the person who asked that question? Oh, how did we get this order? OK, perfect. Yeah, I can explain that again. So if you look at this animation, and actually it's going really fast, so let me just go back again. Note which nodes are being popped out, right? So I'm going to play this again. B gets popped up, then G, then A. Then H, F, C, D, E. And so that's exactly, this is the order. And now we just reverse that, and that's the order we visit. OK, perfect. So I think we understand that now. Let me go to the code. So this is our adjacency list, right? A is connected to B and G. B is not connected to anything. You'll notice that there are no repeats, right? A is to B, then B is not to A. And why is that? What are these edges called? This is pop quiz time. You can write in the chat. Yeah, these are directed edges. So you'll see that this adjacency list is a little different from the one we worked before, because this is directed edges. Very similarly, we have a visited set of nodes. Order doesn't matter. It's like a bag of stuff, kind of. And we have a stack, which, again, since it's Python, we're just going to use an array, a list to mention that. And we're going to have an order, so we can keep track of the order that we are popping stuff. OK, so there are two ways to do both breadth-first search and depth-first search. For breadth-first search, I just showed you one way, and that was the iterative way. Here, there is an iterative way, and there is a recursive way. This first way I'm showing you is iterative. And the reason I'm showing you is because there is a separate stack data structure. And you can kind of follow along, because that's similar to what we did. So basically, you have a node. You pop it out, and then you add it to your visited section. Then you add more nodes. And then you append what is popped. And it's kind of complicated, but essentially, you get your topological sort of EDC, FHA, GB, and that matches. I have reversed it. The other way you can do, and this is sort of an easier way, but is the recursive way. And what recursive means, and maybe some of you are already familiar with this terminology, is that you are calling a function within a function. So this is DFS, and you're calling this function, again, within the function. And so you keep on recursing. So this is another way of recursive, and you will get the exact same topological sort. Oh, what does iterative mean? Yeah, iterative means you go one, then two, then three, four. If you're familiar with while loops, that achieves that iteration, where you're going one step, and next step, and third step. Whereas recursive is you call the same function within the function. Why does the order of popping give us the right ordering? That's sort of how topological sort works. I'm just trying to see how I can explain this, like how I can prove this to you. And Mr. Bhagirath, if you have any good ways to prove that this is indeed how it works. But essentially, the whole, there are proofs, and you can do it. And obviously, we don't have time to do the whole proof and stuff. But topological sort, essentially, if you're familiar with induction, it's sort of like induction, where your property keeps on staying the same. And so when we are working with topological sort, we're working with directed acyclic graphs. And we have a student in the chat sort of explaining it also a different way, that nodes are popped before all nodes that depend on them are popped. So yeah, that's a really good way to explain it. We can sort of see that from the slide. So I'll stop sharing the code, if that's OK. If we look at this, B was sort of the last thing, and there was nothing else dependent on it, and then G, and then A. It sort of matches what we're doing here. I don't know if that's a little confusing, but I did like the student's explanation of nodes being popped before all nodes that depend on them are popped. But all of this breadth-first search or depth-first search, I think we had a similar question for breadth-first search, is that it all relies on induction, meaning that you kind of go to your base principles, and you see if that's true, and then you sort of expand on it. And so every time you are trying to find this, in the breadth-first search case, it was the shortest path. In depth-first search, that's true. But in topological sort specifically, it's about this order that B can only happen after G happens. And you keep on building on that. But that's a good question. You can always look up proofs of depth-first search and stuff, and you can try to look at that and see how that works. And that would sort of answer your question. Two things I can mention here are that, first of all, topological sort isn't necessarily completely unique. And so you might be thinking, well, if we started BFS from another node, maybe we would get a different result. And yeah, you would probably. But it would still be topologically sorted. Question, why is it not unique? Or how did we deterministically achieve the same thing every time if you or I were to do it? What was that one rule we said that we were going to follow in terms of the ordering? Do we remember? What was that? Alphabetical, exactly. Exactly. Sorry, Mr. McGeer, feel free to continue. And then the other thing is that when you're going through BFS, it basically picks out different connected components of the graph. So you can actually figure out, OK, hey, this group of friends are all friends with each other. And it'll probably hit them all around the same time with BFS, the same thing for another group of nodes. And so what it does is it separates out the components that have connections to each other. And then we're just cycling through those components in reverse. And so that's kind of what's giving you that topological sort. Because again, as someone mentioned in the chat, now within that group of nodes, the node that everything depends on is pop last, is pop before that. Yeah. And then the question in the chat of, shouldn't H be last since it depends on everything else? Yeah, that's another node that could have been last. But again, we are doing everything alphabetically. So I started with A because that didn't have any incoming nodes. But neither does H. So there are definitely other orderings which you can do for sure. And yeah, and feel free to, if you want to do after this, if you want to take a screenshot of this graph and come up with other orderings if you are not going to follow that alphabetical constraint. Do you have to start with something without an incoming node? Yeah, you have to start with something without that incoming edge for sure. And obviously, sort of related to that, that when you are working with topological sort, it has to be a directed acyclic graph. If you are seeing cycles in the graph, right, whereas A is dependent on B, which is dependent on C, which is dependent on A again, that's not going to work. There is no topological sort for this graph. So hopefully, that makes sense. If you guys want any more resources or something, I can definitely share with you. I know everyone in this lecture isn't necessarily the same amount of computer science knowledge. So I'm a little nervous of going way too much into the proofs and in the weeds. But for sure, I'm happy to send some resources. Or I can also create YouTube videos on that if that's something of interest to you. Cool. So I did send all of this to Dr. Roo. And let's see. OK, I'm so nervous. I don't know if anyone else is nervous. You know, booby traps. And hopefully, we have the right ordering. OK. OK. Dr. Roo is out. That was like the scariest 15 seconds of my life. He's safely out with the key. Of course, he's not done yet. But before we go on to the next cave, I wanted to share with you some depth-first search applications. So depth-first search applications include solving puzzles with one-solution mazes. So you have already used this method if you've ever gone in one of those fancy corn mazes or even solved it with paper and pencil. You keep on going until you sort of have a dead end. And then you backtrack, right? And you go another way. And scheduling, which is what we talked about in sort of computer world, which computer do you run some program on out of a bunch of computers, especially if there are dependencies that something must happen before another thing. Yeah, so now we're on to the last sort of mission, last cave, where we have the chest. Inside it is the Mecca Finstone. I think we can use graph theory for this as well. This is sort of what the map looks like inside the cave to get to the chest. So can someone tell me what the nodes, what the edges, and what sort of graph traversal we are going to do? What's the objective? And you can write it in the chat. OK, excellent. Nodes is the letters, or more specifically, the intersections. I like the word intersections. And the path is sort of just the roads between these different things. So I'm not sure if many of you have actually walked into a cave. But you can maybe think about trying to look at Google Maps and trying to get to the beach or something like that, and trying to find this. First, before I go too far, what is the objective of this? What's the objective here? What's the graph traversal we need to do? Yeah, the shortest path. Shortest path between which two nodes? The chest, right? Shortest path from A, where he's going to start out, to F. So now let's think about you going to the beach and trying to find the shortest path to the beach. Do you just take any roads? Or what information you might need more to know the shortest path? What sorts of things would you need to know for shortest path? Distances. Cool, that's a great one. That's a very important one. We need the distances. What other things might impact which path you will take? Distances, for sure, one. Traffic, yes. That's a huge one, right? Even if it normally takes you five minutes, if it's congested, you don't want to take the highway. Road quality. Yeah, the time it takes to travel is a sort of metric of these other things, right? Of the path length, traffic, road quality, all these things. Perfect. Cool. So I created this graph for you. So again, it's faster. You have all these nodes, and you have the edges connecting them. So since we did talk about maybe trying to codify maybe these distances or traffic in some sort of way, I'll have to introduce a new terminology here. Weighted edges, right? And weighted edges, an edge which has some sort of cost associated with it. So between A to B, it's a cost of five, right? It can mean anything. It can mean maybe there's five feet between A to B, or it can be sort of an artificial number you created to represent traffic. So that's a weighted edge, and I believe it is quiz time. So let us go to quiz six here. What would a weighted directed graph look like? A, edges that go in one direction with no cost. B, edges that start and end at the same node. Edges that go in both directions with the cost. And D, edges that go in one direction with a cost. We did directed graph look like. Okay, so I will end the poll there. So we were pretty, we're kind of split for this, you know. So I'm glad this was a harder question and no worries if you got it wrong. But the answer indeed is edges that go in one direction with the cost. So the weighted we just talked about is something that has a cost. Directed, if you remember from our depth-first search, we talked about directed edges, right? One-way street. So it only goes in one direction. It's not bidirectional, it's directed, okay? Hopefully that made sense, why that's deep. If you have any questions, let me know in the chat. Let's continue. And how are we doing with time? Okay, we have lots of it. Cool. So I asked Dr. Roo to give these pathlines and any other information. So we have these costs. So this is kind of what these pathlines look like. So this hopefully is helpful, like seven, 25, 24, 12. Oh, and we are already, I thought this would be a new algorithm, but apparently not for some of you, but that's cool. That's awesome that you guys can identify. But it's not as easy because see, we are in a cave and there are creepy corollas all over. So it turns out that we're gonna add plus 100 because there are venomous snakes. Dr. Roo is not a huge fan. Plus 50 for killer bees, plus 60 for scorpions, plus 10 for stalactites, stalagmites, inconvenient, but okay. Plus five for these cute little bats that might carry diseases. And plus 70 for these venomous spiders, tarantulas, or I don't know what they are. Okay, so you know what? We're gonna use Dijkstra's algorithm to try to find the shortest path as some of you have already said, awesome. And then the way Dijkstra's algorithm works is you visit the node with the lowest cost in each step. Okay, so we're gonna start out at A. Okay, and now what we're gonna do is, since we don't know the distance between any of these other nodes, we're gonna set the path between A to A is zero, but the path between any of these other ones, we're gonna set to infinity, right? Arbitrarily large number because we don't know what the distance is yet. But now that we started A, we can figure out what the paths between its neighboring nodes are, right? So B would be 20, C would be what, and D would be what? Correct, 21 and 129, right? All I did was add zero to 20, zero to 129 and zero to 21. So I have these three now, 21, 29 and 21. Now what we're gonna see, these are tentative weights, right? It doesn't mean that this is the shortest cost path between A and this node, but this is so far, this is whatever knowledge we have, this is what we think that these lengths might be. So now what we do is we go on to the next node that has the shortest length. So which one has the shortest? Is it either of these infinities, 129, 20 or 21? Which node has the shortest length? And if I see someone has a question, feel free to write in the chat. Yeah, it's B. So we're gonna go here to B. And what we're gonna do is we're gonna maintain like we have maintained before, sort of this parent dictionary. Who is B's parents? So that we remember where the shortest is coming from, the shortest length. Okay, so we know that A is the parent, we know B is this is indeed like now it's sort of fixed that 20 is that shortest path length between B and A. So now what's next? So we have to update its neighbors. So who is B's neighbors? And what do we update the new cost to? And we only update it if it's smaller, we don't update it if it's bigger. Yeah, we update B to 91, because so far we had thought 129 was the shortest path, but it's not. So we're gonna update it to 91. Had it been less than 91, we would not be updating it because that indeed would be the shortest path. So let's update it here. And before we go on, so now we go on to the next node, which has the lowest cost. So which one of these nodes have the lowest cost? Yeah, C. And C because it has 21. So you are comparing 21, 91 and all these infinities, so 21. So now we know 21 is indeed the shortest path, we locked that in. And now we have to update these other nodes. So who are C's neighbors and what do we update? And we only update nodes that we haven't already visited, right? So which nodes are we updating? Yeah, it's kind of similar to BFS. It's kind of similar to these other algorithms, but it's not exactly the same because the difference is when you work with BFS or DFS, you don't have edge weights, right? There are ways and in college, they'll ask you hard questions where like some of the edges will have a weight of one, others will have a weight of two and they'll still make you do DFS and BFS and you have to modify it a little bit. But for the most case, DFS and BFS, if you have edge weights, you really can do anything with it. For Dijkstra, that is good for edge weights. So the thought process is similar and I think the reason you're finding it similar is because again, it's sort of that induction thing that I'm trying to drill down here where you start with the bare minimum assumption and you keep on having that assumption and you sort of expand on it. So at any given point, you're always having the shortest path. So we are going to update D and E as many of you have said, what would be the new weight of D and what would be the new weight of E? And some people are saying it's a lot like A star. These are all graph theory algorithms. So they are all going to be very fairly, fairly similar. Cool, so we are gonna update D and we're gonna update E, 21 plus 20. And so let us first put this as a parent cause this is the shortest path here. And we're gonna update D because 21 plus 20 is 41. And then we are going to update this one. So 21 plus 72 is 93, which is indeed less than infinity. Okay, so now we go on to the next smallest node. So that's which one? And I keep on giving it away, my bad. Yeah, it's D because this is 41, this is 93 infinity. So we go to D. And D we came from C, so we write that as the parent. Okay, quiz seven time. Okay, which is the next vortex? So this path length will be updated. And what is that updated path length? E, 75, F, 123, E, 93 and F, 77. 20 more seconds. Is Dijkstra new to some people? I know some people already predicted it was Dijkstra, but okay, it is new to some people. Awesome, that's cool. And hopefully it's a good review for people who already knew it, or they're learning something new by looking at the code. Someone knew it from an XKCD, nice. Okay, so we are all over the place here, which I'm kind of happy about. I feel like I shouldn't wish for bad things on you, but also I'm really happy with myself when I can ask tricky questions. Okay, the correct answer is E75. Okay, so how do we think about this? So E75 was the one that most people said, but we did have other answers as well. So the next thing that we have to update is, well, alphabetically, if we were to do, first we do 41 plus 34, so that's 75. So that's why this is 75. 93 is already its weight, right? 93, if you do 41 plus 34, you can get a shorter path than the 93, right? 41 plus 34 is 75, which is less than 93. So we can update that. But let's just still look at D and F. 41 plus 77 is 128. So I actually didn't give you any of those numbers anyway. Yes, we do this alphabetically, but I also did, I wasn't tricky, you know. If I had given you F128, you might have considered that. And because we do things alphabetically, that wouldn't have been technically, technically correct, but that would have still been okay. But F cannot be 123. I am just looking at the graph. If maybe, if you are still confused, if you can let me know how you came to F123, then that would be awesome. Oh, I'm guessing you added the 93 plus 30. So we can't update anything yet from here, right? Because we're still on this node. So we can only update these neighbors, which is E and F. So those are the only two we would be updating if they require an update. And then F77. So yeah, this is pretty common when people say it's F77. The thing is that the distance between A to D is not zero, right? That's 41. So you have to do 41 plus 77. And so that's 120, sorry, 118. My bad, if I said 128 before, it's 118. Does that make sense? This one is the most distributed, I think, answer we got. Is everyone on the same page or is someone confused? And I'm happy to answer any questions. Does it make sense so far? To summarize, the node that we are on, we update its neighbors, right? Only if they need an update, right? So this 41 plus 34 is less than 93. So we need an update here. 41 plus 77 is less than infinity. So we need an update there. Cool, I think everyone hopefully understands it now. So I'm gonna stop sharing and let's continue. So now 93 and then 118, right? 41 plus 77 is 118. So which one of these are smaller in weight? Which one can we, which node do we go to next? E, right? 75 smaller than 118. So let's go to E. So 75, now we have locked it in. That is the shortest path between A to E. And now we see, if we add the E weight to the 30, is it less than what F is currently or not? So should we be updating this and what should we be updating to if we do need to update it or do we already have the shortest path? Okay, I am seeing some, yes, we need to update it. And what do we update it to? Some of you are giving me correct answers. I'd like to see some more. Yeah, so it's not 77 because again, this is not zero, right? This is 41, so it's 41 plus 77. So right now it's 118, but the path between A to E so far is 75. If you add 75 to 30, you get 105. 105 is less than 118. So indeed there's a shortest path from E to F rather than D to F because 41 plus 77 is 118. And that's just, that's more than 105. Does that make sense? Because some of you got this wrong. Let me know if, okay, cool. Perfect. Yeah, I can send the slides in code afterwards for sure. So E, we said that this is its parent and then we go to F, F, E is its parent. And yeah, perfect. So now that is the shortest path. And I constructed that using this parent dictionary we had like that. Okay, cool. So quickly, I want to show you the code because we are five more minutes. Dijkstra, here I use something called an adjacency matrix. Up till now, I was using an adjacency list. So in this adjacency matrix, basically, you had to look at this as A, B, C, D, E, F and A, B, C, D, E, F, excuse me, columns and rows. So here, for example, your distance between A to B is 20 as well as B to A is 20. And so that's how I filled in this adjacency matrix. And then I just have a graph mapping so that we know A represents what node. So it's zero, zero is A and A. And then I calculate this min distance. This is sort of our equivalent to infinity. I picked a really large arbitrary, large number. And I just checked if we needed that update or not. And we do here in Dijkstra, we just keep on going and we keep on updating stuff. This is not the most efficient way of implementing it. You can implement if you are familiar with Fibonacci heaps and stuff like that. And I think it's something like E plus V log V or it might be the opposite of Mr. Bagheer's if you can check me and write it in the chat what the algorithmic complexity is. And then I use this sort of parent mapping list and I create the same thing of A to C to D to E to F. Okay. Wait, was I sharing the Dijkstra code or? No. Okay. My bad. This is how it looks like. E plus V log V exactly. So my bad. Now, can you see the Dijkstra code? Yes. Okay. This is what I was talking about with adjacency matrix and the graph mapping and trying to update the weights and Dijkstra and yeah, and list. Okay. This is the adjacency matrix. That was the most important takeaway of how this is different where A goes to A is zero and A goes to B is 20. And that matches with the graph. Okay. Two more minutes. We can do this. So, and Dr. Wu was able to open the chest. So I'm really excited for him. Oh, I lost him now. Okay. Dijkstra's algorithm applications very quickly. You can use it for Google Maps, telephone networks, IP routing, you know, anything with phones and computers. You can use it for that as well. Any sorts of connections and trying to find these shortest path lengths. Okay. Now we have a bunch of quizzes. If you have to leave, feel free to do so. But we do have a bunch of quizzes and then I would like to sort of launch this. I sort of like to talk about the price. Which one of the, and please answer quickly so that, you know, we can get through these. Which one of the following data structures are used in breadth-first search stack, queue, pack, or topological store? I'll give you 30 seconds for each. I'm gonna be meaner. Okay, I'm closing it. And if you're in the chat and you don't have enough time, feel free to write A, B, C, or D. Okay, Q, the correct answer is Q. That was 100%, awesome. DFS uses stack. Let's do quiz nine quickly. How does a stack work? First in, last out, last in, first out, first in, first out, last in, last out. If you're in the chat, feel free to do A, B, C, or D. This is a stack we're talking about. 15 more seconds. Okay, I'm going to close it. Stack is what we use for depth-first search. So that one is actually last in, first out. First in, first out is breadth-first search. We use a Q, okay? Just a memorization thing, no big deal. Quiz number 10, if we use a graph to determine the shortest flight path between two airports that passengers can take, what would the edges and vertices of that graph be? Passengers, airports, flight paths, passengers, airports, flight paths, flight path, airport. Feel free to use A, B, C, or D. If you are writing in the chat, you have 15 more seconds. I'm going to close the poll in two, three, second, okay, there. I'm going to close it. Okay. And indeed, it's FlightPats Airports. I think only a few of you did the Airports FlightPats. It's just the ordering of the question. I said edges and vertices, so the vertices are at the airport and the FlightPats are the edges. That's all the quiz questions. I just want to quickly have your name and your email. I won't be using it for any nefarious purposes. This is just so that we can contact you for a price because we will be calculating it after this session. Feel free to write in the chat or in the poll quiz very quickly. Oh, don't worry. We have our email is going to be the next question. So, don't worry about that. Five more seconds for the poll quiz people. And thank you for those of you who put the name and email in chat. I'm going to close it, but if you didn't have time to put your name or email, feel free to put it in the chat. And then email question, I'm going to launch that. So, make sure to put your email in there. If my email goes to spam, try to check for your emails in spam in the next week, because you will get an email from me. So, just in case. I will be sending everyone scores, so everyone will be getting an email. And then you'll get a separate email if you qualify for the prizes. I think a lot of people did really, really well. So, we'll probably have to raffle out the top three prizes. I'm going to close this email question. Feel free to put it again in the chat if you aren't done yet. Okay. And that's it for our performance. I'd like to thank Dr. Roof and my green screen, which is a 2008 Math Kangaroo t-shirt. Don't try to calculate my age. I'm not going to be happy, but yes, that is when I participated in Math Kangaroo. And then the prize is a fully paid And then the prize is a fully paid first spot for our AI and visual arts camp that Math Kangaroo and us are jointly sponsoring. Basically, it's going to be one week, and we're going to learn about application of AI and visual art domain, and you're going to participate in a mock art and AI startup pitch. We also have applications open up for the AI machine learning research bootcamp, which is a six-week bootcamp where you get to work with professors and do machine learning projects with them. So, please do check us out. Mr. Bagheerat, if you can put our site in the chat, and please be on the lookout for an email from me. If you want to learn more about graph theory, then we do have a YouTube channel. Mr. Bagheerat, if you can put that in as well, or I can maybe, I don't know if I can put it, but yeah, Ms. Paz and friends, you're already familiar with Ms. Paz. We have a YouTube channel. There are some graph theory videos that goes very much in complex. So, some of you are asking about algorithmic complexity and proofs and stuff like that. That's where we cover it in our YouTube channel. I have made only a few videos so far. I will be making more videos on graph theory after the summer, but the videos I made so far, it doesn't really overlap with our discussion today. So, there's a lot to learn. So, please subscribe to it so you know when new videos are up. If you want more videos on a certain topic, feel free to email me. You'll have my email. I can also put it in the chat. Actually, Mr. Bagheerat, if you can put the email in the chat, info at MetaPlus, and you will get a recorded version. But yeah, let me know if you want me to cover something in the YouTube videos. And that is pretty much it. So, thank you all for joining us. It was really exciting to present to you all, and hopefully all of you learned something new. And we will be in touch with the scores and stuff. Thank you all for coming.

graph theory

Ms. Haripriya

MetaPlus

Bhagirath

algorithms

Breadth-First Search

Depth-First Search

Dijkstra's algorithm

Python

AI camp

interactive challenges

educational resources