Welcome to our Math++ production, The Quest for the Mac Duffin Stone, A Lesson in Graph Theory. I wanna first of all congratulate all the Math Kangaroo winners. That's very exciting. Let's give a round of applause for the Math Kangaroo winners. That's fantastic. I'm really happy that you all did so well and that you love math as much as my brother and I do. Thank you for the clap, claps in the comments. Okay. I'm Harithria Mehta. I will be the host for this presentation and main lecturer. I graduated from MIT in four years with a bachelor's and master's in electrical engineering and computer science and a minor in music. I'm co-founder of Metaflux, which is an educational organization for middle school students and high school students. That's more of my side hustle. My full-time job is software engineer at Microsoft. And I have a personal connection to Math Kangaroo. I was ranked top 10 nationally when I was younger. Bhagirath, if you would like to introduce yourself. Hi, I'm Bhagirath. I will be earning my BS in electrical engineering and computer science and my MS in computer science at the end of this quarter. So two more weeks in class of 2020. Two more weeks in class of 2022 at Stanford. I'm also a co-founder of Metaflux. I've interned at Amazon once, Microsoft twice, and will be working at a startup in Palo Alto. And also I have a personal connection to Math Kangaroo, having placed first place internationally twice with a perfect score and top 10 nationally also multiple times. And Mr. Bhagirath, if you're done, if you can give me a thumbs up because I can't unfortunately hear you. Oh, can anyone else hear me? Yeah, I still can't hear. I'm not sure what's the deal, but if everyone else heard, that's fantastic. Okay, everyone else can hear. So yeah, I don't know. Everything was working this morning and of course everything that can go wrong will go wrong. So yeah, let's jump right in. Graph theory is the study of graphs. Graphs are defined by vertices or nodes connected by edges. So here we have our yellow circles, which is our vertices or nodes, and they're connected by edges, which are these green lines. I'm going to share a couple of more vocabulary words. So a path is when vertices and edges are not repeated in a graph traversal. So a path for this graph would look something We aren't repeating any vertices and we aren't repeating any edges. And a graph traversal is essentially going from point A to point B. A cycle is a closed path. So a cycle would be these three nodes sort of form a triangular shape because we can start from this node, go to this node, then go to this node, and then go to this node. And we are starting at the node where we are ending. So it's a closed path. So it's a cycle. A neighbor is when you have a vertex adjacent to another vertex. So for example, these two nodes are neighbors because there's an edge connecting the two of them. These two nodes are neighbors because there's an edge connecting the two of them. But these two nodes aren't neighbors. So applications of graph theory. Now, all of this sounds interesting, but where is it actually used? So it's used in several different places. Even if you don't end up being a computer scientist like I am, you will likely deal with graph theory in the future. And in fact, all of us do from day to day. For example, if you are on social media, the social network is based on graph theory. Lexical semantics, how words are related to each other in sentences comes under the field of graph theory. Designing circuits, where those resistors are, those light bulbs are, that's all trying to map that out is under graph theory. Or finding a route, what's the closest, what's the fastest way to get to the beach? Chemical and biological pathways, trying to map out how things work in our body, that can come under graph theory. And then timetable scheduling, like your regular everyday schedules, like what activity should I do first, what activity I should do second, third, so on and so forth. So all of this comes under graph theory. What I want you to think about today is about graph representation and three questions specifically, all throughout today. What do the nodes represent? What do the edges represent? And how do we traverse this graph, right? And just as a reminder, the nodes are these yellow circles, these edges are these green lines. And how do we traverse this graph is a question that's like, how do I get from point C to point D? Oh, and it's already quiz time. Okay, so let us bring this quiz up. And like I said, we are going to have prizes, so try to do your best, you know. Let's see. And I'll give you one minute, okay? Okay, how are neighboring nodes connected? A, by a vertex. B, by a circle. C, by an edge. D, by a cycle. Oh, and make sure to answer the poll. If you give me the answer, if you chat it to me, then it won't count for points. So make sure, yeah, to give it in the poll. If you're having any issues, oh, there's no poll. You don't see the poll, okay. Yeah, okay, so I'm gonna give you a minute. Um, yeah, okay, so, okay, fine. You can chat it if you can't see the poll. Can I get the options written? Yes. So, okay, some people can see the poll. For those of you who can't see the poll, can you let me know what device you're on? I can type the options, yes. Let's see. Oh, Chromebook, okay, I see a lot of Chromebooks. Okay, I will try to, oh, thank you. Mr. Bagheer, yeah, that would be very helpful. And let me actually send you the whole list of questions, Mr. Bagheer, so I can, so it'll be easier for you. I know we're going a little over time for this first question. That's perfectly fine. We wanna make sure everyone has a chance, chance to answer the question. If you have a chance to change your device, if you have another one, then that would be great too. Otherwise, I will try to save this chat results. And Mr. Bagheer, I'm sending you the list of questions. Okay. So are we all good now? I see 23 of 33 have participated, and my guess with that is, my guess with that is the best 10 of you have answered in the chat, and I'm really liking the answers. I think you all are understanding. So I'm gonna end the poll, and I'm going to share the results. And so C, as most of you said, by an edge. And remember, all our quiz questions are sort of related, so make sure you understand this. Yeah, if you can't see the poll, don't worry. The answer was C, by an edge. Neighboring nodes are connected by an edge, and you can see from this graph, right? And so hopefully you all saw your poll results. I'm going to stop sharing, or did I show correct answers to all? Here, if you can not see it, then hopefully you can see it. But I'm going to stop sharing right now, and I'm going to, I'm going to show you what this means in this graph, right? These are two nodes. They are neighboring nodes, and they're neighboring because they're connected by this edge. So hopefully all of you have understood it right now. If you got it wrong, no worries. You have plenty of other opportunities to make up for the points. So let's move on. Oh, can you? Oh my gosh, it's my phone, right? I'm so sorry. I should have totally put my phone on silent, but I really need to get this. Yeah, Dr. Wu? I'm in the middle of a Math Kangaroo presentation. You want the Math Kangaroo winners. Just because you're the Math Kangaroo mascot doesn't mean you can just call me whenever. Okay, fine. No, I'm really sorry, guys. I wanted to teach you graph theory, but Dr. Wu, I'm sorry. I wanted to teach you graph theory, but Dr. Wu has bigger plans for you. And you know what? Let's just listen to him. He says he has a documentary he's going to show it to you all. But let's just do that. I'm really sorry. 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. Wu 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. OK. And he has another video for us to watch as well. Hello, students. I need your help. I was researching the MacGuffin 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. OK. So Dr. Roo sent me his social network. He's on this cool thing called Meta. I don't know if any of you are on it, but he did send his social network, and I think we can sneak in graph theory. What do you all think? So what is it we want to try to find out, right? Essentially, we want to find the shortest path between Dr. Roo and Mr. Hamilton. So maybe Dr. Roo's friends, friends, friends, friend, friend is Professor Hamilton. So now, remember those three questions I asked in the beginning, right? What are the, the chat's funny right now. What are the nodes and what are the edges if we were to create a graph like this? Anyone have any guesses? And you can put it in the chat, and I can read it out loud. OK, I see the people. Beautiful, beautiful. I am getting a lot of great answers. Perfect. Wow. Yeah, perfect. All of you are on the right track, but the nodes are people and the edges if they are friends. Perfect. So here we have the nodes, and I'm going to help you out here, and I'm going to, and all of these are nodes, right? It's not just one person or another person. It's all of these people who are in our social network are nodes, and then the edges are the friends, friendships. So I will help you out here, and I'm going to create a graph for you so that we don't spend a lot of time on that. The graph will look something like this, right? Dr. Roo, if we check back to this chart, Dr. Roo's friends with me and Ms. Paz. I'm friends with Ms. Paz, Ms. Marva, Mr. Benjamin, and Dr. Roo. And so you see that reflected in a graph, right? Dr. Roo is connected with me and Ms. Paz, and then I'm connected with Dr. Roo, Ms. Paz, Mr. Benjamin, and Ms. Marva. So hopefully that makes sense. And we need to try to find the shortest path between Dr. Roo and Professor Hamilton. Now, I'm sure all of you can just probably figure it out right now, but we need to think about social networks in real life, right? If you're on social media, you might have thousands of friends, and there are millions of people on this network. So if we just try to come up and devise some sort of method, it might not work for a lot of number of nodes accurately every single time. So we need to come up with an algorithm. An algorithm is a process or set of rules to be followed. Breadth-first search is an example of an algorithm that we are going to use for this problem. And what breadth-first search does is it starts from a node, and it explores all the nodes at a certain depth before moving to nodes at the next step. If this doesn't make sense so far, no worries. We're going to walk through an example. It also uses a data structure called queue. And the way queue works is the way normal queues or lines work, right? The first person who gets into the queue is the first person who gets out. OK. So here's what our graph looks like right now. We want to start at Dr. Roo, right? Because we want to see the shortest path from Dr. Roo. If you notice, there is a pink halo around Dr. Roo, and that means that Dr. Roo is visited. That's the first node we're visiting. And what we're going to do here is look at my left-hand screen. There's a queue. And we're going to put him into the queue, and then we're going to go to Dr. Roo. Put him into the queue, and then we're going to pop him out. So let's look at that. OK. Now what we're going to do is after popping him out, we're going to put all his neighbors into the queue. So let's check out his neighbors. Ms. Hericria is one of the neighbors. Notice that now I have a pink halo around me because I'm visited. The way breadth-first search works is once you visit a node, you don't want to revisit it because we have already found the shortest path between Dr. Roo and that individual. OK. And now he has another neighbor. Oh, it's already quiz number two time. OK. Let us launch it. So quiz number two. And Mr. Begirth, if you can put it in the chat. And I will read this out loud as well besides Ms. Hripriya, who's Dr. Rue's neighbor? Mr. Benjamin, Professor Hamilton, Ms. Paz, or Dr. Rue? 20 more seconds. I think most of you would have responded by now but just in case, and I'm really liking the responses, I think you're really understanding this stuff. Okay, let's end poll and let's share the results. And indeed, you are all correct. Ms. Paz is the other neighbor of Dr. Rue. So let's continue. So we're going to put me and Ms. Paz into the queue. Okay, now queue again is first in, first out. So who was first in the queue and who's going to be first out? Feel free to type in the chat. Who is right now first in the queue? And the queue, if you can look, it starts in the bottom. Okay, so I'm seeing some mixed answers. Most of them are correct, but then there are some confusion. So I'm glad I asked this question. So whoever said that I'm first in the queue is correct. I know some people mentioned Dr. Rue or Ms. Paz. So Dr. Rue is no longer in the queue. So when we talk about the queue, it's about at a given moment. So right now I'm first in the queue. And the reason I'm first, yes, it looks weird because you might be thinking that this is the top and this is the bottom. But if we can go back here, if you see this, I'm getting pushed into this queue first. So the queue actually, you have to start from the bottom and look up. But hopefully that makes sense now. So I'm going to be popped out next. That's a very weird construction, but yes, apparently. Okay. And, oh, oh, quiz number three. They're just, whew, it's getting intense. Let's do quiz number three now. Oh, and I, sorry, I never stopped sharing the quiz two results, my bad. Quiz three, let's launch. Okay. And Mr. Bagheer, if you can put it in the chat, I will read it out loud. Which vertices are neighbors of Ms. Kharipriya and have not been visited? A, Dr. Roo and Ms. Paws. B, Ms. Paws and Ms. Marva. C, Mr. Benjamin and Mr. Bagheer. Or D, Ms. Marva and Mr. Benjamin. I'm liking the answers. We have a few more people who still need to answer the question, and we have 20 more seconds. And Mr. Bagheer, do you know what would be nice is if you can actually, while the quizzes are going on, if you can record the answers of the people that have the answer correct from our page question. Then hopefully, towards the end of the presentation, we can get a final tally. Okay, so I'm going to end the poll right there. Thank you, Luca. Luca asked a very important question. How come you're not friends with your brother? Thank you, Luca. I forgot to mention. Yeah, I'm not friends with my brother because it's kind of uncool to friend your siblings on social media. So yeah, I am not friends with my brother. No, okay, which vertices are neighbors of Ms. Haripriyan have not been visited? The answer is... Ms. Marva and Mr. Benjamin. So, the other answer I got right was Ms. Paz and Ms. Marva. You all are half correct and what that means is that Ms. Marva and Ms. Paz are my neighbors because we are connected by an edge. But Ms. Paz has already been visited, right? If you remember the queue picture, she's in the queue, and there's a pink halo. The pink halo means that she's visited. And in breadth-first search, you don't want to revisit anything you've already visited. So, Ms. Marva and Mr. Benjamin are the correct answers. Okay, and I'll stop sharing. Let's continue. Okay, so Ms. Marva and Mr. Benjamin, just as you all said. And you can see how it entered the queue. Okay, now, currently, what is first in the queue? Hopefully, you all will get this answer correct, and you can put this in the chat. Ms. Paz. Perfect. Oh, excuse me. Most of you are saying Ms. Paz. Yep, she's right here. First in, first out. So, we had a pop Ms. Paz here. And Mr. Bagheerat gets in, right? Because he is the only neighbor that has been unvisited. Okay, so now, what's first in the queue, and who should be popped, and who's going to enter the queue? There's like three questions in there. Who's currently first in the queue? Who's going to be popped? And who's going to enter the queue? Who are we going to push into the queue? Perfect. And I am seeing a lot of correct answers. Oh, popped. Okay, great question. So, someone asked what does pop mean? Pop means we're going to kick them out of the queue. It means first out. And that's a computer science term. When I say pop and push, those are computer science terms. Pop means you, that person exits the queue, and push means that person enters the queue. So, yeah, thank you for the question. So, mostly we are correct. There are some little few different answers. So, let's talk about it. So, you are indeed correct that Ms. Marva, she's first in the queue because she's at the bottom, and she's going to be popped out. She's going to be kicked out. And then Ms. Marva has only one neighbor that is not visited. So, there's a question here, how do you decide who gets in? So, how do we decide who gets in? Well, we look at Ms. Marva's neighbors, right? Ms. Marva has me, Ms. Paws, and Ms. Ghosty. But me and Ms. Paws are already visited. Ms. Ghosty doesn't have that pink halo, so she's not visited. So, Ms. Ghosty is going to enter the queue. Okay, and hopefully that makes sense. Someone wrote Mr. Benjamin. Mr. Benjamin is already visited because he has the pink halo, and he's also not a neighbor of Ms. Marva. So, he's not going to be popped or pushed quite just yet, but let's look up quiz number four. Okay. And I have inevitably already perhaps given the answer to the quiz. Yay me. But hey, that's a three point. Maybe this is just a text who's listening. Which node do we add to our queue next? Oh, so I'm still seeing some confusions. Okay. So, I'm glad that we have this question. At the very next, which is the first one? So, there's some confusion. Which is the very first next one, if that makes sense, that we're going to add to the queue? Because yes, we do have a lot of unvisited nodes, but which is the first one we're going to add once we pop Ms. Marva? For the people who are confused in the chat, does that make a little more sense? Okay, I think we are less confused now. That was one minute. So, let me end the poll. So, the confusion we had here was, is it Mr. Whiskers or Ms. Ghosty, right? Well, Ms. Marva is first on this list, so we had to pop her out first. And then what we put inside is, if Ms. Marva has any neighbors that are not visited yet. So, is Mr. Whiskers a neighbor of Ms. Marva? So, I'm seeing a lot of nos, right? Ms. Marva and Mr. Whiskers are neighbors. They aren't friends, unfortunately. Okay, and so now, yeah, I think everyone understands. Now, if you don't totally ask me questions, it's fine. This is college level material, so it will take some time to settle in. But yeah, Ms. Ghosty is the only neighbor that's not been visited by Ms. Marva. So, let's continue. Okay. And so, we saw that Ms. Marva got popped, and then Ms. Ghosty gets pushed in. Then, then what happens? So, if someone can walk me through, you kind of saw the next slide, but someone can walk me through what happens next, exactly, when we're talking about the QMAP. Now, what's going to happen? Who's first in the queue? Who gets popped out? Who gets pushed in? Okay, so first, who's getting popped out? Okay, I'm seeing some right answers. Well, who's first, right? Mr. Bagheerat isn't first yet. Right now, Mr. Benjamin is first, but just as some of you said correctly, Mr. Benjamin doesn't have any more friends that are not visiting. So, we can pop Mr. Benjamin out. Makes sense so far? Let me know if it doesn't. Yes, Mr. Benjamin will get popped and replaced by nobody. That's written very well. Thank you. Then, Mr. Bagheerat is first in the queue. Then, Mr. Bagheerat's only unvisited contact, Mr. Whiskers, goes in and Mr. Bagheerat gets popped. Perfect. Thank you. I don't want to call out anyone. I feel bad, but thank you so much to the person writing in the chat. You're saying it so well. Doesn't Mr. Benjamin have Mr. Whiskers? So, yeah, is Mr. Benjamin, is he connected by an edge to Mr. Whiskers? Are they friends? No, he's not connected directly. Exactly. You have to be connected directly. You have to be neighbors. So, Mr. Benjamin, unfortunately, doesn't have any more friends. Oh, it looks like it, though. Can you maybe tell me what the confusion is? Why it looks like it? Is it because he's connected through other friends? We should make him some more friends. I agree. Oh, it's sort of in a straight line. I see. No, you can't really get influenced by how the graph looks. You have to just see, is there an edge between two people? And if there is, then they are connected. If not, they're not. You know, don't worry about the edges. I could have made a curvy line and it doesn't matter. Okay, cool. So, now we understand that Mr. Benjamin has no more friends. We pop him out. Mr. Begirith is first in the queue. Mr. Begirith has one other friend that has not been visited. That's Mr. Whiskers. So, we put him in. So, let's watch that. Okay, so now Mr. Whiskers is in. Now what? What happens? Now, walking through the end, what's going to happen? Ghostie gets popped out. Okay, and then what happens? Does Ghostie have any more friends that are not visited? Okay, so she gets popped out and now no one gets pushed in. Then what? And then Mr. Whiskers is popped and Professor Hamilton finally gets in. Perfect. All of you are understanding this so well. Thank you. Awesome. So, Mr. Ghostie gets popped out. Mr. Whiskers gets popped out and Professor Hamilton is pushed in. And that's pretty much it. Then we can pop out Professor Hamilton. If anyone has any questions, now would be the time to ask because we just did one iteration of breadth-first search or one problem of breadth-first search. Okay, now remember this graph and remember these lines. Remember these lines. There's a reason I colored them differently. These were the lines that when we, if we visited through that path, then I bolded them. These lines we didn't visit through the path. Now I'm going to orient this graph in a different way. A breadth-first search, once you, once you do the breadth-first search in a graph, you can make this graph into a tree. So let's go back here. You have blue lines, you have purple lines, brown lines, green lines, you know, maybe see the first couple like Dr. Roos connects to me in this plaza. My shortest path is Ms. Haripriya to Benjamin and me to Ms. Marva. And so that's what the tree looks like here. So hopefully, yeah, some sort of hierarchy. Sure. I guess the computer science word would be tree. This is essentially a tree-like structure. Because we don't have these multiple connections that normal graphs do. We're just taking the bare minimum and what this is giving us as at each level, so we call these levels, at each level or at each depth, what is the shortest path between Dr. Roo and that individual, right? So could there be a path between Dr. Roo and then to me that's longer? Yeah, definitely. You know, we could go something like Dr. Roo to Ms. Pause to me, but that's so much longer than it has to be. You know, I am it's, I am Dr. Roo's first favor. So this is what it looks like. Let's just play the animation here, just so that we can sort of cement how this worked, right? We first had Dr. Roo, then we had its neighbors. In this sort of scenario, we could also call these children, children nodes, because you are sort of emanating from this parent node and you are the parent node. I am not Dr. Roo's child. I will tell you that regularly, but in a breadth-first search, I am. Yeah, I'm not half-kidding you. Okay, so now let me know in the chat, how many, how should I ask this question nicely, I guess? Without it being too confusing, but I guess, okay, I'll ask this. What is the path we need to take to get to Dr. Hamilton? Let me know that in the chat. Advancing some right answers, lovely. Oh, I don't have their names. That is true. I don't have their names. I don't have their names. I don't have their names. Lovely. Oh, I don't have their names. That is true. You can just tell me by, like, girl kitten, male kitten, my brother, dragon. I'm sorry, I should have put names here. Some of you also remember these names, which is quite amazing. I'm quite surprised. Okay, cool. All of you are having the right answers. So essentially the shortest path is Dr. Root to Miss Paws to Mr. Bagheera to Mr. Whispers to Professor Hamilton. I love these other, the names that other people are making wrong. Dragon. Okay, cool. So now we know the shortest path. How are we doing on time? Okay, so let's rush it up a little bit. I want to quickly show you the breadth-first search code. If you don't know Python, if you have never coded in your life, no worries. I just wanted to show you how this looks. The way we would do it in coding is, oh, and I'm just keeping on talking and I'm not even sharing my screen. This is how it looks like in coding. This is an adjacency list where you have the different connections. You can see that Roo is friends with Ms. Hericria and Ms. Paws. Then we have visited and we have our queue, and we keep on adding it, and we check this condition. If it's not a visited node, then what do we do? Essentially, we get the exact same answer. If you didn't trust me, trust the code. Just kidding. Don't, because I wrote the code as well. I'm just kidding. You should trust everything. That's the order. Roo, Paws, Kabir, Ms. Hamilton. I just wanted to show you a different sort of way of how we would do it in real life when we have hundreds and thousands of nodes, because we can't actually just write it down and do it. Okay. Let us give this information. Oh, would the BFS function be universal in the Python language? That's a great question. Let me address that when we do our next algorithm. There are many ways to write it, and I will show you. And some of you have, this is a dictionary. Okay. If there is more than one path, why doesn't the tree show them? So, that's a great question. We have the shortest path. We show the shortest path. Can there be multiple shortest paths? Yes, there can be. Let's address that question in depth for search. This one was kind of a fun one where I have the nodes. But essentially, usually, we represent nodes by letters, and we go through them alphabetically. But we will revisit that for our next algorithm. Yeah, and it would be miles long, someone mentioned, if there are many, many nodes, and that's true. So, let's do a share screen again. Okay. So, applications of breadth-first search. And by the way, I am messaging Dr. Wu. I'm asking him to contact Professor Amos-Otundi. He's doing that while we are going over this other material. Applications, social networking. This is what we went through, essentially, the social media. Fraud detection. This is something I have done in major tech companies. What people like to do, bad actors or frauds, as we call them. These fraudulent actors, they make several different accounts, hundreds and thousands of accounts. And there's really no way to connect them except maybe they use the same credit card number, they use the same phone number. And the duty of the software engineers like me is trying to find these huge clusters and then closing them all at once. Because what they mostly have done is they have created these accounts for free and then they're selling them on the black market. So, it's pretty cool. I have done this for an internship. It's fun. Would you be able to implement this into machine learning AI? AI is sort of separate. I'm sure that there are some connections, but we'll talk about AI and our prices soon enough. Search engine crawlers. So, for example, how does Google index Google or any search engine index the pages? These different pages are connected by hyperlinks. So, let's say I have created a website and my website is linked to your website. Then, you know, now you can suddenly see a graph forming in your head that how are all these websites connected? There are machine learning diagrams and graphs. Graphs are used in multiple things, but we are talking specifically about graph traversal. I think what you're thinking about, whoever's asking in the chat, is neural networks and that's completely separate. But, yeah, I guess in some ways that is a graph as well. Yes. So, yeah, that's a great connection. No, we don't use graph traversal algorithms. And today's topic specifically more than graph theories, graph traversal. Good question. Okay. Oh, another video from Dr. Rue. Let's look at this one. Thank you for your help. I was able to connect with Professor Hamilton and he translated the papers for me. The paper says that the MacGuffin stone is in a cave in Zakopane. There are two entrances to the cave. The second entrance holds a treasure chest in which the stone lies. The first entrance holds the key to the treasure chest. In order to first get to the key, I must follow the instructions in the order prescribed or else I will perish in the cave's booby traps. In order to get to the chest, I must take the shortest path available or else I will run out of oxygen inside the cave. I am sending you more information by email. Okay, perfect. Thank you. So, what were the symbols above the chest? So, yeah, let's go over it. Let's see what Dr. Rue is saying. So, there are two caves, right? One cave has the key. One cave has the chest. There's all this stuff written in the ancient language of Ruthenian, but Professor Hamilton has translated for us. So, here are some of the translations. Yeah, that was Ruthenian, apparently. That's what I've been told. Yeah. So, in the first cave to get to the key, we have several sort of rules, right? Lever G should be pulled only if stone A is pressed. Stone B should be pressed only if lever G is pulled and so on and so forth. And make sure we look at this last rule that all lever stones blocks must be handled with once and only once. And I don't know if any of you have seen Indiana Jones, but I know enough. I have seen enough of Indiana Jones movies to know not to mess this up because otherwise those big boulders will come rolling on Dr. Rue or he will be destroyed by a bunch of arrows. That's what I've seen. I don't know to believe that's like a real life thing, but maybe. Some people have binge watched, so they probably know more of this terrain. So, it's imperative we get this right, right? So, let me give you one more vocab word, directed edges. Directed edges is an edge where you can traverse only in one direction. So, essentially, it's a one-way road, right? You can go from A to B, but you cannot go from B to A. This is different from the edges we normally talked about where you could go both ways, if you think about a breadth-first search example. Yeah, directed graphs. Topological sort. Topological sort is a linear ordering of vertices and you can have a sorting only for directed acyclic graphs. That means graphs that have directed edges and don't have cycles in them. So, we're going to talk about more what the sorting is later, but essentially, it's this problem, right? Where you have to do one thing, then you have to do another thing, and you have to make sure that they are in order because there are dependencies. Okay. The way we're going to do topological sort is with the depth-first search. So, what we're going to do is we're going to start from a node and explore a branch as far as possible before backtracking. Think about when you're in a maze, you know, one of those core mazes that I always get lost in. You take a branch, you go all the way, and then you realize there's a dead end and you go back. That's exactly what depth-first search is. Depth-first search uses a different data structure called a stack, and a stack is last in, first out. And the way you get a topological sort is when you run this depth-first search algorithm, you're going to reverse the order in which those vertices are popped out of the stack, and that is our ordering. That is our sorted ordering. Okay. So, just to remind you, these are the rules, right? If we were to make a graph of the rules, what would the nodes be, what would the edges be, and what would the sort of overall goal be? Nodes, edges, and what's the goal? Please write it in the chat. Yeah, and I'm still on this picture. I will move out of it in a bit, but... Okay. Yes, I am seeing a lot of great answers. Nodes are the levers, stones, and blocks. Edges are basically the rules, like what can you do after what? If this, then that. I love it the way you guys are deconstructing this problem, essentially, and then the goal is try to get the key, try to touch each of these levers, stones, blocks, make sure you have this correct order, this topological sort. Yeah, overall goal is to interact with everything. Okay. So, let's start out. I am going to start with node A. This is sort of what I was mentioning to you before, is that there can be many different correct orderings. There can be a lot of things, but the way we do it in computer science, just so that everyone sort of has the similar type of answers, we always break ties alphabetically. So, what I want to do is I'm going to start here with A, not only because it's the first letter of the alphabet, but because there are no incoming edges. So, let's start here. Start with A, and we push it into a stack. Remember, this is called a stack. This is the first search. This is not a queue. This is a stack, and now it's last in, first out. Okay. Now, what are its neighboring nodes? G and B. So, which one do we go next? Do we go to B or do we go to G? I'm seeing both. Remember, alphabetically is how we break ties. So, now everyone's like, yeah, it's me. And we don't pop out A yet. Okay. So, we put in B. Now, does B have any outgoing edges? No. Yeah. So, there's not much we can do here. So, we're going to pop it out, and then we're going to go to G. So, let's just go back here for a second. We're going to pop we pop out B, and then what we do is we backtrack. So, we went from A to B. We realize B is a sort of a dead end type of thing. You know, there's no outgoing edges. So, we go back to A. That's called backtracking. And essentially, and I see some people are coming up with solutions, but we do remember that we need to have a way that's, you know, very robust, that even if we had a million nodes, we could still come up with good solutions. So, there are multiple ways. There are multiple orderings, for sure, because I know a lot of people say, why not this? Why not that? There are multiple ways to do this, for sure. But we're going to do this to topological sort and specifically alphabetically. So, here we go to B, and then B, we pop it out, and then we backtrack to A, and we check who are A's neighbors. And so, as you all said, G. So, that's what we're doing in the stack here. We pop out B, and we put G into the stack. Now, does G have any neighbors? It does have a neighbor, but is it visited? Visited in this case is if it's orange, right? Yeah. If it's visited, just like in breadth-first search, we don't want to revisit it. So, now, does it have any nodes that are neighbors that are not visited? No. So, that's pretty much it for G. So, we had to pop out G. Then what do we do? We backtrack. Where are we backtracking to? To what node? What node came before G? A. Perfect. Does A have any other unvisited neighbors? No. I've seen a lot of no's. So, now, what node do we think we go with next? So, we pop out A. Perfect. Yeah. C is the next one alphabetically that we have. Perfect. You guys are getting this. Awesome. So, we pop out G, A, and then we push in C. Now, tell me what happens next. Which are C's unvisited neighbors? Yeah. There's two neighbors. So, which one do we go with? Yeah. We go with F first. So, we're gonna push F in. Perfect. And now, we're at F. Who are F's neighbors that are unvisited? Yeah. So, yeah. F has two neighbors, right? It has two edges coming out, H and B. Two outgoing edges. But B is already visited. So, it's only going to be H's, all of you have said. Perfect. Okay. And now, what happens next? And I believe this might be quiz time. Yes, it is. Let us do quiz. Perfect. Thank you. As someone pointed out, you backtrack, right? You backtrack, H doesn't have any neighbors, then you go to F, F doesn't have any other unvisited neighbors, then you go to C, C doesn't have, so now what happens next? And yes, we have a question in the chat, feel free to ask the question. Yeah, okay, so one direction, yes. It matters what direction, so it has to be an outgoing edge, otherwise it doesn't count. Does that answer your question? Okay. Okay, I'm seeing, so H is not a neighbor of E, not in this case, yeah. H doesn't have an outgoing edge to E, yes. Okay, okay, great. And I'm gonna end both, we have a few conflicting answers. Most of you had the correct answer, and the correct answer was D, so let me walk you through it, and if someone's, whoever wrote F or E or C, if you have some confusion, feel free to ask in the chat, but I'm gonna try to address it right now. So what happens is we have, we have, we go, we went to H, right? Does H have any outgoing edges? No, so then what do we do? What's the fancy word I keep on using? And I'm kind of weirdly demonstrating. Yeah, we backtrack to F. According to the problem, aren't you done because you got to H the key? Well, we need to touch everything, right? That was one of the rules. We need to make sure we touch all the level stones blocks once, otherwise, to Dr. Lu, that was very gruesome. Okay, we go back to F, right? And then what happens next? I know some of you have already answered this in the chat. Yeah, we backtrack because there are no unvisited neighbors. So now we are back to C. Does C have any unvisited neighbors? No, and so then you go to the next node, which is alphabetically, and that, as all of you said, was D. Anyone have any questions? If you didn't get this question right, feel free to ask in the chat. This is an easy stuff, so totally okay. Maybe some of you said F or C or something because you are backtracking, and that's true, but you don't push it into the stack. Once it's already in the stack, you don't push it in. And E could have been another choice, but we are breaking ties alphabetically. How can you backtrack? Okay, that's a great question. Backtrack essentially means, let's say we are at H, right? H doesn't have any outgoing edges, so we backtrack and we go back to F, right? And then F, F has, H has an outgoing edge in B, but B is already visited, so we're done with F and we go back. In our stack, when I do the animations, the backtrack is essentially just, you pop that node out and you worry about whatever else is in the stack. Last in, first out, right? So you pop it out and then you look at the stack. Okay, does that answer your question for how can you backtrack? Okay, I didn't stop sharing, yeah, okay. So it's D, does D have any neighbors that are not visiting? Not visiting, and I'm already seeing good answers, so what do we do next? Yeah, we pop it out and we put in E, perfect. So now, so let's just quickly see this animation. So we are B, popping out G, A, popping out H, F, C, D, E, and that's it. So these are the pop out order, and what that means for a topological sort is, so this is the order we popped out, B, G, A, H, F, C, D, E. You look at these rules and this topological sort, the topological sort is the, you have to reverse this order of the popping. So essentially the first thing you're gonna do is E, then you're gonna do C, sorry, E, D, C, F, H, A, G, D, order E, right, reverse. Make sense? And you can, I put the rules here again, so you can just check it out if what we're saying here matches the rules, and we don't send out the rule to an untimely death or something. Okay. I love the question, I'm just gonna read it off. If this has been here for a long time, then how do we know that the traps have not been triggered or the items pressed by animals or other people? That's a wonderful question. I think we just, let's just roll with it. Let's just roll with it. I think Dr. Wu is on a plane to Zakopane. How did you press E without doing F? We are doing F first, because this is the reverse order. So we start with E, then we do D, C, F. This order that I have in the screen, that's the order of popping. We have to go with the opposite order. Yeah, yeah, it's reverse. Cool. Let's just roll with it, and hopefully Dr. Wu is in one piece. Oh, and someone has a theory that I believe that the ancients who built the traps take the time to restock it every now and then. That's possible, you never know. Okay. Let's quickly see the depth-first search code example. Let me share the correct screen. Where are we? I am confused. You're not sharing, by the way. Are we all seeing the right thing? No, we're not. We're not seeing it. Let me share and stop sharing. Wait. It's raining out here. Oh, we are pretty split. Now I'm asking you all the tricky questions, because I'm now pulling information and material from the beginning of the lecture. I'm in Chicago. Yeah, it's raining there. We have six more seconds before I close this. That's it. So we were pretty split. We were pretty split. A weighted graph, I think all of you got that part. It's one with the cost. The slide's up there. We got that. A directed graph is when an edge goes in one direction. It's like the one-way streets we were talking about. That's directed. So it only goes in one direction. It doesn't go in both. Does that make sense? I know this one was tricky. This is my bad. I was being tricky. But I think we're all awake enough to answer tricky questions. So let's move on. And let's look more at this cave. OK, so Dr. Rube sent us the things that were written in Ruthenian of all these, like the path lengths. So we have the path lengths. But there's a catch. We aren't only worried about how short these lengths are. We're also worried about what's in the cave. So it turns out from A to D, we're going to add an extra 100 because there are killer venomous snakes. Dr. Rube is not a fan of that. We have killer bees from B to D. So we're going to add a 50. Not as bad as the snakes, but the bees are a bit inconvenient. Scorpions, plus 60, worse than the bees. Is there a thing as weighted nodes? We usually assign weights to edges only, yeah. There's probably things we could do, but it's usually edges, I guess. Stalactites, stalagmites, we're going to add a plus 10. Oh, bats, they're cute, but still inconvenient. We're going to add a plus 5. So I'm going to move out of this slide because this scares me. There's one last thing, I think, maybe. Yes, the spiders, plus 70, not a fan. So now let's see what's the shortest path we need to take. Well, we have another algorithm. This is called Dijkstra's algorithm. And Dijkstra's algorithm is visit the node with the lowest cost in each step. And I think some of you have already calculated this. Maybe you used a similar method, but again, let's think about if you have hundreds and thousands of nodes, what are you going to do? OK, so we have this graph. OK, and we start at A. We already talked about, we start at A. And the shortest path from A to A is just the node itself, so it's 0. That path length is 0. Normally, we do use computers, yes. We are doing this by hand. In Polish classes, we don't do it by hand. And what I found is that everyone gets super confused about the algorithm. So we're doing each of these by hand. So we actually understand how these algorithms work, because you can only code it when you understand how it works. OK, so from A to A, it's 0. But all the other nodes, we haven't explored any of the edges yet. So we're going to label them all as infinity, right? But now we're going to look at what are the neighbors of A. Now we're going to kind of look at what the edges are. We're going to look at the neighbors. So who are A's neighbors? Yeah, B, C, D. And so B, if you add 0 plus 20 is what? And so you can give me that for B, C, D, what should be the shortest, sort of the smallest, tentatively the smallest width. B is 20, 1, 29, 21. And again, we'll do alphabetically, so 20, 21, 1, 29, 21, and 1, 28. Perfect. So now we go to the thing that has the smallest width so far. So which one has the smallest width? I know people are already saying this in the chat. It's B, perfect. So let's go to B. And what we're going to do is we're going to store so that we know where we are coming from, we're going to store this sort of parent map here. So we'll say, OK, B, the shortest path from A is just going from A itself. Now what's next? Who are B's neighbors? And what are updated things? You only update the weight if it's shorter, if it's smaller than what it was before. So for D, yeah. Yeah, only D's a neighbor. And should we update this weight? And what should we update to if that's the case? So I'm seeing some nos. So you update the weight if you add this value to this value and it's smaller than this value. Yeah, we update to 91. We wouldn't update it if it added to 130. But indeed, if you go from A to B to D, that's a shorter path than going from A to D directly. So let's back. So now, out of all the nodes, which one has the smallest weight? We have F with infinity, E with infinity, D with 91, and C with 21. Yeah, C. So we go to C. Now do we update these weights? Some people have already been giving me answers. That's fantastic. Do we update D? Do we update E? Do we update F? And what do you update it as? Yes. I'm seeing yeses. Oh, well, I guess in the next step, can we update them? Yeah, so I'm seeing some answers that we can possibly update D to 41. So let's see. And I added it by the weight to the parent because C, the shortest distance, is from A also. So D is updated. Then let's see E. Obviously, 21 plus 72 is less than infinity. So that is 93. We can't update F because C and F are not neighbors. OK, and then we are on D because that is the smallest one left, 41, 93, infinity. Quiz 7, and my brother warned me because I was about to give away this answer as well. So thank you. What's the next WordTexas Pathline? Will we update it? And what is that outdated Pathline? Thank you. So five more seconds, three, two, one. Okay. So most of us had the correct answer. Some of us were answering also the other one. So let me explain this. The next vertex whose path length will be updated and what is that updated path length. So it will be E, just alphabetically, E and F are both gonna be updated, but also F, I have not given you any right choices for the update, right? When you get E, you have to add 41 plus 34 and then you have to see if that gets updated, if that's smaller or not. 41 plus 34 is 75, which is smaller than 93. So this one will get updated. F, what it will be updated to is 41 plus 77. So some of you have said it was 77. That's not quite correct because you need to see this, the sum total up to that point. It's not, this is not zero. The distance between A to D is 41, like the cost. So then from D to F, it will be 41 plus 77. So the answer is E, 75. Okay. And so let's do that E and then D is 41 plus 77, which is 118. Which one is the smallest one? Which one do we go to next? E, yeah, E, 75. Perfect. Now F, okay. Can we update the weight or not? Yeah, F becomes 105, which is the shortest. And that's essentially our thing. We have our parent. And this one, if you kind of go through this parent map at the left-hand side, this is the shortest path that we get. Which some of you already said in the beginning in the chat, which is fantastic. But this is how you would do if you were using Dijkstra. Can you show us all the traps like the scorpions? Sure. Or I think I remember from the tippy top of my head, I think we went to stalactites, stalagmites. There was nothing here. And then this was bats. And then this one, I do not remember if there was anything there. Yes. Because it will take me a long time to move the slides and we are kind of getting towards the end of our time. So we can look at it after the presentation. Oh, mice and bats. Okay. Probably something like that. So yeah, not the best, but not the worst thing either. So let me just quickly share this now, Dr. Roo and Dijkstra. This is not an adjacency list. It's an adjacency matrix. And the matrix represents this first row is everything from A. So A to B is 20, A to C is 21, A to D is 129. The reason I use this more complicated structure is because we have weighted edges. And essentially we have this minimum distance, infinity, I've represented 10 to the seventh. And yeah, we basically just iterate and we try to find the shortest path and we get that shortest path, A, C, D, E, F. Okay. Now let's go back to our presentation. Okay. Now let's see if maybe Dr. Roo can tell us if we get the term. Oh, he got it. He got it. Nice job, guys. Dr. Roo? I hope he's fine. I'm not sure. Let's just continue on. Let's go with business as usual. Hopefully he's fine. Dijkstra's algorithm applications, Google Maps, telephone network, IP routing. Google Maps, when you are going from point A to point B, Dijkstra has used their telephone networking, IP routing for phones and computers, trying to take the path that has the smallest bandwidth that's as fast as possible, also uses those types of maps. We have some theories in the chat that maybe the scorpions got Dr. Roo. I'm not sure, I hope not. And we have more quizzes. We have quiz 8, 9, 10, and we have main email. We are not gonna use your email for anything. It's just so that we can tally up the marks and connect all the people and also email you if you are winning one of the prizes. So let me show that, and then I will try to figure out where Dr. Roo is. Hopefully you guys can focus on the quiz. I know I'm kind of scared. How would I code it if I had a hundred nodes exactly the same way? Our adjacency metrics would be just bigger. So I remember when I said I did breadth-first search at an internship, actually I had to use fancier technology, like it's called PySpark. And my breadth-first search was actually structured a little bit differently because I was working with millions and millions of nodes. So it does get a little different, but the overall concept is still the same. You have 30 more seconds for quiz number eight. It does take a long time. My code, I remember, used to take several hours and that was like the fastest possible. So yeah, when you work with big data, it takes a long time, but it's cool. Okay, you all have 10 seconds left. Don't worry if you joined late, at least from the answers that we have, we will still tally them up. Okay, that's one minute. So I'm going to end in five, four, three, two, one, and pull. Now I'm going to give you quiz number nine. Sorry, quiz eight, let me just show you the results quickly. The answer indeed is Q for breadth-first search. So I'm going to stop things. Stack is for depth-first search. Let me show quiz number nine here. Okay, so I'm going to give you five minutes to do this. I'm going to give you five minutes to do this. How does the stack work? First in, last out. Last in, first out. First in, first out and last in, last out. Don't let that confuse you. Yeah, when I read it out loud, it does sound confusing. You have 10 more seconds. Okay, 10, 4, 1, 2, 3. It indeed is last in, first out. First in, first out is for queues, which we use for breadth-first search. This we are using for depth-first search. That one's not confusing. Okay, last question of the day, other than asking for your name and email. Let's do quiz number 10. Chat answers will count. I believe my brother is tracking them. Likely, we won't be able to announce the winners at the end of this. Only maybe for the Zoom quizzes who got the highest marks, maybe. Or we might just email it out later. We'll talk with Ms. Joanna. There's number 10, we have 30 more seconds. Thank you for typing your name and email in the chat. We will talk about the price in just a second. That is one minute. I'll give you three more seconds. Three, two, one. The correct answer is Flightpads Airport. When we are creating this graph, we are trying to keep these nodes as airports and then try to connect these airports with these flightpads. Okay. Yes. And let me quickly ask you name question and email question. Please do this as quickly as possible because we have three minutes. I also want to talk about what the prices are. Thank you for everyone who's writing in the chat. And I will close in three. Oh no, there are more people. No, I won't be sending any emails to those who didn't win prizes. Did you want emails to know your score or something or? Okay, I will end this poll right now. If you didn't get a chance, feel free to put your name in the chat. And it's possible that many of you might have been top scorers. We are giving out only three prizes, so we might do a raffle. But in that case, we will likely still alert you. You got the great marks on the quiz. Oh, you'd like to see an email. Okay. Yeah, we can try to maybe do that. I will be traveling next week, so it might take me a while to get back, but I will for sure. The score is actually from the beginning. If you joined late, I am so sorry, but it is from the beginning. Because we don't know when you joined, we don't have that info and the questions. Just an answer in one year. Okay. Three more seconds. If you don't have a chance to write in the poll quiz, you can put it in the chat. And that's it. I just got a text, by the way. Dr. Lu is fine. He's out with the MacGuffin Stone. Everything's all good. And see. I want to thank my cast of characters other than me and my brother. There's Dr. Lu here with his green screen. That is a Mac Kingdom in USA 2008 t-shirt that I have won, or it's my brother's. I'm not sure. Please don't calculate our age, because I understand that many of you might have been born around 2008. Adam, don't worry about it. You can still send your answer. If you guys weren't able to type it in before I finished, you can still send it and we'll accept it. Prizes. We're giving out three prizes to our AI and visual arts camp. I know some of you were trying to draw parallels between AI. We are running two camps this summer. We have a machine learning research camp and a visual arts camp. Please do check them out. The visual arts camp is what we are co-sponsoring and giving you prizes for that. It will be an AI machine learning summer. If you like my instruction, I will be the head instructor for both of these camps. You can check our website. If you are interested in graph theory, can you put Metaplos's website, Mr. Bagheer? If you want to learn more about graph theory, Ms. Paz, who you are all very well acquainted with, she's a cat from MIT who loves to learn and loves to teach. She has her own YouTube channel. Ms. Paz has been quite busy lately, so all the graph theory videos aren't up yet. The videos that are up, there's a whole playlist. They are very difficult. If you are interested more in graph theory, you can definitely start watching that. Make sure to subscribe to that channel so that you can watch the videos more. She might put some more videos up in the fall. We got our quiz results. We don't have them yet, but I'm sure we can send those in later. Maybe if my brother can quickly do it, if you guys want to stick around, maybe he can quickly tabulate them. I had to write code for calculating the quiz results because it's not easy to do in Zoom. How do you get quiz results? Let me send you those. If you have to leave, feel free to head out. We really enjoyed this opportunity. Thank you for spending this Saturday morning with us. It's always great to connect with MET fingers winners. If you like this, when you do get a survey, please do say that you liked it. It means a lot. Thank you. Thanks so much for coming, everyone.

graph theory

Mac Duffin Stone

nodes

edges

BFS

DFS

Dijkstra's algorithm

social networks

semantic web

network routing

math lecture

interactive examples