Transcript
All right. Well, welcome to problem session five of 6.006. It's a pleasure to see all your smiling faces here today. With this week, we're going to cover some problems in graph theory related to depth-first search and breadth-first search, which were roughly the topics that I guess we covered in the last couple lectures and what's going to be on your homework. And I believe this is basically the homework from from last year with a few revisions based on some some typos we had. Oh, and I caught a spelling mistake that I'll bother our instructor about later. Okay. So, without further ado, let's get started.
I guess we'll just do them in order for lack of creativity here. The very first problem has to do with some measurements on a graph, which is actually a really interesting one to me. So, it turns out that in a lot of research in for some reason in computer science, there's graph theory research and then there's network research and these are two different communities for weird historical reasons that I don't totally understand. But people in the network science literature often measure things like the radius of a graph and some other kind of measures that are trying to tell you something about like is a graph a long spread out thing like a line graph or something super compact like a star and so on.
And so, this problem is kind of digging into the algorithmic aspects of how we might compute one of the measurements that I believe is is fairly common in in in that community. So, let's kind of go through these problems. As usual in 6.006, we like to take actually relatively straightforward computational problems and then dress them up with a lot of language to make it annoying for you guys to parse. And indeed, this problem is no exception to that. So, in this problem, we're given an undirected graph. And as usual, we will call him G. Uh and we define a particular number that we're trying to measure in this in in this problem, right?
So, uh in particular, uh right, if we given a given a vertex V, uh then we can define something called the eccentricity of V, uh which is the distance to the farthest away uh thing. So, in particular, um we can define um is going to be given by uh the following, which is the max over all the possible uh I'll try to make sure my notation Oops, I've already Oh, that's okay. Uh uh over all the other vertices of the distance from uh V to W, right? Uh so, I'm like standing at a point on a graph and now I like, you know, make a loud noise, and the last person to hear me, uh the distance to him would be uh the the eccentricity of of that vertex.
And so, uh this is some kind of notion of like radius or diameter, uh but sort of planted at a point. Uh and then if we want to learn a property not of a vertex, but of the entire graph, uh one thing we can do is define the radius. And that is given by R of G is uh the min over all of the different vertices U of the eccentricity of U. Okay, so I think this is one of these definitions that's really annoying to parse and think about. So, we should like draw a little bit of a schematic and see what's what's going on here cuz uh especially as a geometry professor, this one's kind of nice cuz it translates directly to uh what you might do in metric geometry.
So, um let's say that I have a circle here, and I I the world's most complicated way of defining its radius. Okay? So, for any given point there's a point in a circle. That's a circle in case you're wondering. You know, there are those internet contests where like they have people that just walk up to the board and draw perfect circles and then leave. I unfortunately am not an expert at this matter. Um but anyway, so if if we think of a point like a circle as some analog of our graph, and then I draw a point, which might be the analog of a vertex, right? Then what is the eccentricity? Well, it's the distance to the farthest away point.
Right? So, for this guy, it might be the length of of this line, roughly. Uh because that's the distance to the farthest away thing. Right? So, for every different point that I draw, you know, each point has its own farthest away point in the circle. Uh so, there's some positive number that's assigned to every single point in this domain. And if I take the minimum of that positive number, where do you think I end up? Center of the circle. That's right, Jason. I end up in the center of the circle because if I think about it, the distance to the farthest away point in this domain, um one thing you can convince yourself is that that's sort of as small as possible.
So, this is what we might call a minimax problem in in optimization cuz we are minimizing the maximum distance. Yeah? Um it also shows up in game theory, all all kinds of different places that solve this stuff. But thankfully, in this particular problem, we're not going to need all that. Okay. So, uh right. So, this homework problem has two parts. Um the first is to give an algorithm for computing the uh the radius of a graph. And then the second one is to give an algorithm for approximating the radius of the graph uh really quickly. Or more quickly than the first part. Um I actually don't know if there's a a lower bound there, but uh come back to that later.
Okay. So, in part A, right? We're given G. Uh and moreover, we're given one additional piece of information which we actually do need in this problem. I think it's one of those words that kind of slips past us when we read graph theory problems, but it's important to pay attention, of course, and that is we're given G and it's connected. I suppose really it should be given connected G, but that's okay. Um now what we want is to compute the radius of G in time that looks like the product of the vertices, the number of vertices, oops, times the number of edges, or the number of edges times the number of vertices.
Your instructor struggles to speak and write at the same time, but it's a skill that I'm working on. And frankly, handwriting is much easier with this little chalk. Okay. So, essentially, you know, I used to have a math professor in college that used this phrase all the time that you know, this is like it's important not to think here. Um you know, the the the problem asks you to compute the radius of a graph, and in some sense there's an algorithm that just like writes itself for computing the radius, right? Because the radius is the min over all the vertices of the eccentricity. The eccentricity is the max distance.
So, what would be the simplest thing to do here? Well, in some sense it would be to loop over all the vertices, compute their distance to all the other vertices, and and and and and take the max for each one of those, and then the min over all of the guys in the outer loop. Since I just said a sentence that I'm realizing doesn't parse particularly well, uh let's let's sort of write down what I mean. Um which is to say we're going to think of there being an outer That's why we don't use this chalk. An outer for loop, uh which is computing this min, right? So, right? Well, what are we going to do?
We can, you know, compute the uh the shortest path distance to all of the other W in in my graph, you know, take the max of W of the distance from V to all the other W's. Obviously, we can kind of do these two at the same time. Uh And then if this number is bigger than my current max, keep it. And or Oh, yikes. If it's smaller than the current estimate I have of the the radius, then I keep it. And if it's not, then I throw it away. Right? So, maybe I initialize, you know, my radius at infinity. Uh and now let's call this number, I don't know, little R. If little R is less than big R, then just keep it around.
Right? And so, if we think about it, I I don't think it's terribly hard to prove that this algorithm is correct cuz it's sort of just taking our definition of what the radius of a graph is and translating it into um a brain-dead algorithm. Um so, I think really the the the challenge here uh is is is proving the the run time uh in in this particular algorithm. So, what does our run time look like? So, we have a loop over vertices. Right? So, I kind of incur a factor of mod V here. Uh and then uh well, our graph is unweighted, so one strategy for computing the shortest path distance would be uh breadth-first search.
I think that's what's in my notes. Yep. Uh and in general, breadth-first search, if you recall from lecture, takes mod V plus mod E time. So, the question is, okay, so if I multiply these things together, what do I get? I get O of V times V plus E like that time. But like uh-oh, that's not the time that my homework problem wanted. Right? Because the homework problem asked you to solve this in just mod V times E time. And somehow we've incurred an extra factor. And now we have to figure out why this is actually okay. Or we have to fix our algorithm. But in this case it turns out that that this run time is just inaccurate.
Okay. Um What's our intuition here? Well, I kind of underlined it for you here. Our graph is connected. In particular, there's going to be a nice property of of connected graphs, which is that the number of edges dwarfs the number of vertices here. So really, if we have V plus E, you know, and sometimes this is going to look like a constant factor times E plus another E here. So this whole thing is going to be V times E time. Yeah, so let's let's make that argument a tiny bit more formal here. So, in particular, we know that G is connected. Um right. And every vertex So in particular, what what can happen here is Okay, unless my graph consists of one vertex, which is a case you could dispose of pretty quickly, what I can't have is a graph that looks like this.
Like one vertex and then an edge floating around there. Everything has to be connected together. Connected together. Okay. So, in particular, what this means is that every vertex is adjacent to at least one edge. Again, except I guess technically the one vertex case, but I think we can give this ourselves that for any graph of constant size we're we're we're we're not terribly worried about it, right? It's just the asymptotics that matter in this problem. Okay. So, if every vertex is adjacent to one edge, well, and remember that every edge, kind of by definition of an edge, is adjacent to two vertices, then what we can conclude is that the number of vertices is less than or equal to the number of edges divided by two.
This is a conservative estimate. And so, in particular, what does that mean? It means that V is big O of E. This is a case where we have to be quite careful about big O being an upper bound. Right? In this case, typically V is much less than E. Well, depends how many edges, like if you have really dense graph or not. Um but in this case, what does that mean? That means that mod V plus mod E is really just big O of mod E. Right? Because this is big O of mod E plus big O of mod E. Uh and that means that our problem really runs in V times E time, uh which is what we wanted in our problem. Are there any questions from our audience on part part A here?
Cool. I don't understand why where you went from the first statement to the second statement there. Every vertex one edge implies V is less than or equal to E over 2. Oh, yeah. So, I guess I guess there's sort of two things that matter here, right? Every vertex is adjacent to one edge at most, and every edge uh Yikes. Uh every edge is adjacent to two vertices. Um I guess actually it's the second one that matters. So, so you can never have a vertex just floating by itself. So, one way that I can count my number of vertices by looking at the number of edges and saying that well, every edge can touch exactly two vertices.
Every vertex has to touch exactly well, at least one edge. Um so, if you put those together, you can convince yourself that that this bound has to be true. If you want to be conservative about it, you can just get rid of the divided by two here, I guess. It doesn't really matter. Any other questions from our audience? Cool. All right. So, now uh let's take a look at part B. Uh so, in in in part B here, uh they ask us to basically do the some version of the same thing, right? They want us to now approximate the radius, but we're given a smaller uh budget of time. So, now what we want in uh number B here is uh compute an R star such that uh I got yelled at in my textbook that ST apparently should always be subject to.
I got an angry review of the textbook I wrote because of that, which was puzzling to me. But, amazon.com is not a great source of useful data. Uh but, in any event, uh we want R star uh which is sandwiched between the radius of G and two times the radius of G um like that. Now, notice So, in other words, we want to The first thing to notice we want to upper bound the radius of our graph. And already this should suggest us how we might solve this problem. Right? Because if we take a look back at our definition of radius over here, notice that the radius is a min. Right? So, what's going to happen if I returned epsilon of some other vertex?
Well, it's lower bounded by the radius because the radius is the smallest possible epsilon over any vertex. That makes sense? Now, when I was doing this problem, um because uh you know, I'm I'm the the dumb instructor of the three, I I said, "Well, okay, but like you know, maybe I need to be like somehow judicious about what vertex I choose. Like, you know, well, in some sense, what this suggests is that maybe I choose some other vertex and compute its its uh radius and return that as our approximation." Um but, of course, the problem wants me to sandwich a between two values here. So, in addition to uh you know, upper bounding R, I want to be less than two times R.
In other words, my approximation is within a constant factor. Um I tried some some weird stuff, like farthest point sampling and so on. Then I realized that you you actually don't really need to do any of that. Um one thing you can do is literally choose any vertex, return its uh uh eccentricity, and that's actually good enough. Yeah? So, here's our algorithm. Um Great. Let me go back to my notes here. I don't know why I'm following my notes. I can actually do this off the top of my head, but they they make me feel better uh if I'm looking at them at the same time. Uh so, in particular, what I'm going to do is choose a U in V.
Let me be clear here. Any U in V. So, if I'm using some data structure to store all my vertices, I just take the first one, whatever. And two, uh I'm going to return R star is equal to epsilon of U. Um now, of course, this isn't really an algorithm. If you do this on your homework, you'll lose points. And the reason is that I haven't told you how to compute this value here. So, if you were to write out your answer for this problem, of course, you should tell us that like really to compute epsilon, what do I do? I use breadth-first search to compute the shortest path from U to all the other vertices, and then I guess I take the the the max value here.
Okay, so I think you guys can fill in the uh the of the algorithm. The bigger challenge is going to be to prove that this is actually a good bound. Right? And so in other words, what we need to prove here I don't know, like there's a claim, there's a proposition, there's a theorem, so we're like somewhere on that axis. I'm going to call this one a claim. I'm going to downgrade it. And that is that the radius of my graph is less than or equal to R star which is less than or equal to two times the radius of my graph. Okay. So, let's let's prove this this thing. I'm managing to use all of my boards on one problem here.
Okay, so in particular, to prove this claim, I need to prove two inequalities. This is like two homework problems in one. So, let's number those off. There's one, there's two. Okay. So, let's do inequality one. I think we can squeeze him into a relatively small space. So, remember, what is the radius of my graph? Well, just by definition, right? We know that it's the min over all possible U of epsilon of U. So, in particular, what's the nice property about the minimum of something is that it's less than everything else or equal. So, this maybe let's call this U not just to distinguish between that and the notation I have on the left hand side.
This is less than or equal to epsilon of U because I don't know, because min. Yeah. So, that actually already and of course this is exactly what we chose to be our star. So, our Uh, first part of our proof is done here. Yep, so this is the easy part. And sometimes like this is sort of what inspired our algorithm. So we expect this bound to be kind of straightforward. Okay, but the other half of the problem is a little more tricky. Uh, and actually there there's a solution in the notes and then I decided just to make it a little more inaccurate to write up my own. Um, so uh, but actually I have I have an ulterior motive which is I noticed in this class we don't tend to use a tiny piece of notation that I like.
Uh, so for my convenience in future problem sessions I thought I'd I'd introduce it now. So, we're solving a minimization problem. The nice thing is that in this class everything we do is finite. If you take my graduate course, that's not going to be the case. In fact, actually in lecture two we're going to do like variational calculus, but uh, in in this course, uh, what does that mean? That means if I minimize a function, there's actually a vertex in my graph that achieves that minimum. Right? This is different than like for example, if I then I'll shut up, but like if I wanted to minimize, you know, here's f of x = 1 over x and I ask you for the minimum value.
Well, it's you know, over all x greater than or equal to zero. Well, the minimum value is zero, right? If I take x off to infinity, but it never quite crosses zero, right? So you're kind of in this weird universe. If you remember Jason's lecture, he talked about infs and sups as opposed to mins and maxes, but this can't happen in our problem because when we compute a min, there's actually a vertex that achieves it. And that vertex we call argmin. Okay? Uh, and so this arg here stands for for argument. So one thing that I can do is say, "Okay, so remember that my radius is the min the min over all u of uh, epsilon of u that I'm going to define a vertex u naught to be the argmin over U of epsilon of U.
And this is just fancy notation for saying, "Give me the actual vertex that makes this value as small as possible." Yep. Uh the nice thing about this problem is that we're not worried yet about algorithmic runtime, so I can construct this kind of thing and not worry about how I actually found it, right? Okay. So, let's say that we did that. So, this is find me the vertex um that actually gives me the radius, right? So, in other words, I find that vertex and then I find his or her farthest away vertex and measure the distance, and that distance is the radius of my graph. Okay? Um so, let's actually do that.
So, in particular, uh then I can define a second vertex V naught Well, how does the radius algorithm work? I find the central guy and then I find the one that's farthest away. So, we're going to make him the argmax over all V in my graph of the distance starting at U to any V. Right? So, if I think about my circle, it's a circle, right? Then U naught is like that center of my circle, and then V naught is like that far away point. This is a schematic, right? My circle is really a graph in this problem, but I think I think the analogy actually works. Okay. But, in reality, my algorithm was brain dead.
I didn't actually compute U naught. I computed I just randomly drew Sorry, I shouldn't use that word. I arbitrarily drew a vertex U and then computed you know, the farthest away distance from that guy. Uh and of course, what we have to check is that that thing is within a factor of two of what I wanted. So, okay. Uh if I have U, then I'm additionally going to define one more thing called V, and that uh Mhm. Uh Oh boy. Uh okay. So, I'm noticing I'm saying one thing and I'm writing another. U naught is the center of my graph. I just I think I said it. I just forgot to write it. And then uh this V is the farthest away guy from him.
So, basically the subscript zero here means like is the platonic ideal of what I wanted in my problem and no subscript is going to mean the other one. So, now um I compute the farthest away thing from the U that I actually chose in my algorithm. That's some V bar. Right? So, again, remember my algorithm just says, "Okay, I'm going to like choose some other point V and then return V's distance to some farthest away point." Uh oh, sorry. Choose another Oh boy. Choose a point U and return his distance to some far away point V. I think I've managed to lose everybody uh in knotting together using these here.
Okay. So, why did I introduce all of this notation? Um cuz this is what's going on in this problem, right? To actually compute the radius, I want to find the most central point U naught and its distance to its farthest away thing V naught. In reality, I arbitrarily chose a point U and I returned uh U's distance to some point V and I want to show that those two things are within a factor of two of each other. Okay, that summary makes sense even if I talked in circles for a while. Okay, so let's actually do that. So, remember the uh the thing that I'm going to actually return is R star and that is equal to distance from U to V now cuz I just made all these definitions.
And now I get to uh use my favorite inequality. Um in fact, this is sort of the only inequality we know in this class so far, I think, uh which is the triangle inequality, uh which says that of course this is less than or equal to the distance from U to U naught plus the distance from U Uo to V. Right? So, in other words, this is saying the shortest path from U to V is always upper bounded from the length of the shortest path from U to Uo and then Uo to V. Right? This is drawing a triangle. Aha! But, take a look. What is the actual radius of my graph? Well, in my notation, the radius of my graph is exactly the distance from Uo to Vo.
And this thing is bigger than the distance from Uo to anything else by definition. For all of V, right? So, if I flip this inequality backward, well, take a look. This is the distance from Uo to something. This is the distance from Uo to something. So, I incur two factors of the radius. And I get the bound that I wanted. Yep. Uh and so, this is a a slightly more formal little proof of of of exactly the same thing that's in the homework notes. Okay, so the one thing that's remaining is to actually show that our our algorithm runs in a reasonable amount of time. So, I think they give us a budget of order E uh time.
But, notice that argument is precisely the argument that we just made right here uh just minus the V factor. Uh and the V factor just came from looping over all the vertices in in part A. Uh so, now I think we're we're we're done with problem one. As usual, I've wasted too much time on the easy problem. All right, any questions about uh about this one? Excellent. Well, now that I've written too much, uh let's uh do the rest of it. I spent time on this problem cuz I like it. It looks like a geometry problem. Okay. So, now uh let's see. In problem two, which I I notice that this homework is kind of full of prototypical 6006/graph theory problems in general.
Like they just go down the list of things that people typically do in graph theory that are like useful tricks to know. Um so I would suggest the students in this class even if it's pass fail uh look very closely at this homework before doing uh the current one. I think the ordering works out that they can do that. Um because I think you'll get some good hints for how to solve all the the the the current homework. Uh see here you heard you heard you heard it here first, guys. Okay. So in problem two uh we're talking about internet investigation. Uh so in particular uh MIT has a bunch of different routers that are connected by cables uh to one another.
And essentially uh what are we given? We're given a bunch of different routers and we're given the length of the cable in between them. And the latency unsurprisingly is proportional to the length of the cable. That in my abstract understanding of how computers work kind of makes sense to me. I'm not sure that's actually true, but um that's sort of immaterial for 6006. I assume our department has a networks class if you're interested in that kind of thing. Uh and essentially uh what we're trying to do is sum up the latency over all of the uh the routers. So let's let's write down a little bit of notation here while I continue to dance all over the room here.
Keep losing uh losing my chalk. Need like a holster. I feel like that would be useful for for the chalk bucket. Okay. So now we're going to do problem uh two here. So we're given R routers. Uh and uh some of them are marked as uh entry points. Uh and now we have a bunch of bi-directional wires. WI, each of which has length LI and that's positive integer value here. Yep. And actually because of this, so technically I think a lot of students in this class have encountered weighted graphs before, but if you think about the narrative of of this course, I think for the version of this homework we haven't really encountered weighted graphs yet, but a better way of putting it rather than psychologically diagnosing your instructors is that what we're going to find is that they're often problems that look like they're weighted graph problems, but they really aren't and and and this is a nice example where that's the case.
Okay. So we define the latency as follows that it's at least proportional to the shortest path to an entry point. And now we have two additional assumptions that we need. Right? One is that the total latency or at least the latency of every vertex which is the same thing, latency, is less than infinity. What is this really saying by the way? Like when would the latency be infinity? It would only be infinity if I like took a pair of scissors and and cut a wire and would just connected from the rest of the network. Yes. Every router is connected to some entry point. That's exactly like there's some path from every router to some entry point.
Doesn't necessarily mean the entire graph is connected I guess, but at least that you can always get to an an point. And then moreover, uh, and this one's the the real kicker here, uh, that there's uh, at most 100 R uh, feet of wire. Incidentally, R stands for routers. I had like the problem the previous problem that I had and was thinking radius for a long time. Um, so don't be like your instructor and actually read the entire problem before getting hung up on it. Uh, but in any event, um, the thing that you're trying to uh, do is to compute the sum over all of the uh, routers uh, I don't know, R, whatever, of the latency of of that router.
Okay, so that's our our our problem here. Incidentally, this little goofy exercise I just did of taking this paragraph problem and kind of writing it in bullet points, I find helps me a lot when I'm trying to solve these algorithms problems cuz I think it's really easy to just get like thrown off by a wall of text here. Okay. So this problem is screaming out graph theory. Like we're practically like using the terms here. We are using the terms, right? Like you've got nodes that are kind of like routers and maybe edges are kind of like wires, but there's a bit of a catch, which is that your run time, right?
At the at the end of the day, I think you want order R run time. That's where things get a little funky initially. Um, and so we have to think a little bit carefully about how to do it. And here's going to be the uh, the trick. So this is starting to look like a shortest path problem, but what would you maybe not want to do would be to iterate over every single router or or every single vertex and every single router and compute the shortest path between every single pair. Because if you did that, oh boy, I'm I'm I'm confusing my terminology. There are entry points, which is the thing that I need to compute the distance to.
Uh, and I need to iterate over every single router and compute its distance maybe to all the entry points and then take the min or something like that. But if I had a double for loop, then I'm probably not going to get order R time, right? Because somehow you expect it to look like something squared or like the product of two terms. It's going to be a little more sneaky than that. And then we're going to use a sort of a canonical trick in graph theory. Okay. So, let's let's follow the the Toucan Sam approach here. We're going to follow our nose and say that okay, there's basically a graph that's staring us in the face in this problem.
But then we're going to have to make a little bit of an edit because we'd like to use the kind of linear looking time search that that BFS affords us, but it looks like we have edge weights in our graph, right? Because the wires are associated to lengths, right? Different wires have different sizes. But we have this nice fun fact, which is that the total amount of wire in our whole universe is less than 100 R. I guess the units of this 100 are kind of weird, right? It's like feet per router or something, but whatever. Okay. So, in particular, I'm going to make a graph with a node per router. Right?
So, like here maybe here's a router. Here's another router. Here's router one and router two. But since I want to use the sort of linear time advantages of breadth-first search when I'm when I'm computing distances I can be a little bit sneaky about this, which is to say instead of having like 10 ft of wires, I'm going to have 10 1-ft wires. Yeah? Except now I'm additionally going to have, you know, little chains. So, here maybe the length L12 is equal to three, right? So, I'm going to put three edges in between. So, in other words, And going to I'm going to connect them with chains of L I uh edges for each wire.
Does that make sense? So, essentially, I'm going to take my weighted graph problem and make it unweighted by just like repeating a bunch of Well, not really repeating, but chaining together a bunch of edges uh so that the total length of this thing uh is equal to the distance from one router to another. Okay. Um one thing we might as well do is balance the number of vertices and edges in our graph when we do that. So, first of all, let's think about the number of vertices. And we can be totally lazy and upper bound this stuff. It doesn't matter. Well, for one thing, uh I have one node per router, so we incur one factor of R there.
And now, notice that we're we're kind of laying down cable one little piece at a time here in our chains. And now, I always uh tend to have a fence post style headache about exactly what the constant factor is here, but if we're conservative about it, uh you know, we incur uh most a factor of 100 R kind of additional edges because those are all the different pieces that we could lay together. It's actually less than that because of the end points, but whatever, uh because R plus 100 R is big O of R. All right, so the number of vertices in my graph here is big O of R. Similarly, what's the number of edges?
Well, this is exactly the amount of cable uh that's inside of my network, I believe. Yep. Right? So, this is exactly 100 R. Well, I guess the way the problem is written, it's it's uh upper bounded by a 100 R, but whatever. Um so, this again is big O of R. This is kind of convenient. So, now we have one number that rules them all, The which is R, which tells you both the number of vertices and the number of edges up to a constant factor, right? So, one thing I can convince myself is if I do BFS on my graph, that's sort of okay. Remember that's vertices plus edges time, uh but in this case uh those are the same.
Okay. So, uh right. So, remember at the end of the day I'm trying to compute the latency. This is like the length of the shortest path uh to the entry point nodes. So, here would be a brain dead algorithm, which is to say for all routers for all entry points you know, compute I don't know, let's call the router on I the entry point J. I compute distance IJ like using breadth-first search or something. Uh and then I, you know, uh you know, take them the min of these values. Um and add them all together, right? So, I compute for every router I look at every possible entry point. I compute its distance to the entry point.
I take the min over all these things, and now I I add that to my running sum. There's a problem here, which is I haven't told you the relative number of entry points to the total number of routers. So, at least the way that I've I've I've I've written this algorithm here how much time would this take? Well, there's two different for loops. And in the worst possible case, at least in my brain dead algorithm, I don't notice that, you know, if I am an entry point, then I don't need to compute distances. Well, this would take order R squared. Whoa. Uh R squared time, right? Um at least, right? Actually, shouldn't even write big O.
I I write uh what's lower bound? Oh god, I'm a terrible algorithm professor. Omega of r squared time cuz I haven't even accounted for the amount of time that it takes to compute the distance. Right? Uh and this is a problem because I've only given you a budget of linear time for your algorithm, right? So So this is this is frowny face. I tried drawing the turd emoji on my notes and it really it didn't work. Okay. So uh we need a better trick. Uh and this is actually sort of one of these prototypical uh uh tricks which is uh to do the following. So let's construct a graph. I'm going to draw my graph in a particular way, but notice that there's nothing about my algorithm that cares about the way that I drew it.
This is just to make my life easier. Which is I'm going to put all the entry points on the left and all the just the remaining non-entry point routers on the right because I can. Uh and so this is what my graph looks like. So these are like my entry points. You know, here are my other routers. My graph doesn't have to be bipartite. Like it could be that my routers are connected to each other, whatever. Um and then there's some some, you know, edges that go from my entry points to the routers in the graph. Trying to make sure that my graph is connected. Okay. Right? And so essentially what this problem is asking you to do is to say, "Okay, for every single node in my graph, I need to compute the the distance to the closest entry point and then sum all those things together." Right?
That's that's the schematic we can have in mind. So in some sense, what we want to do is think about the set of entry points as like one giant node, right? Because it doesn't matter which of these guys I choose for my shortest path to an entry point. I just need to find one. Yeah? And so here's the basic trick, and this is one that appears all over graph theory, which is I'm going to introduce one additional node to my graph, and I'm going to put him on the left-hand side. He's really big because he is a supernode. Which is a term of art. This this term shows up a lot. And I'm going to connect it to every entry point in in my my network of routers.
Does that make sense, class? Okay. So, here's the here's the kind of cool thing. So, first of all, for every entry point, what's the the shortest path from the entry point to the supernode? Well, obviously it has length one, right? I I drew it for you here. Now, here's the thing. Let's take the shortest path from the supernode to any of the routers on the right-hand side. What do I know? Well, clearly, like maybe I choose this guy here. Well, what is my shortest path? It goes here and then there. There's one property that matters here, which is that it has to pass through one of these entry nodes.
Which one does it have to pass through? Shrug. For shame. Well, remember the Justin's favorite inequality is the triangle inequality. And what does it say? It says that if I compute the shortest path from the supernode to any node in my graph, then every sort of sub piece of that shortest path is also a shortest path. That sentence was hard to parse. Let's try that again. So, in particular, if I have a graph from the supernode to some router over here, well, we've convinced ourselves it has to pass through one of the entry nodes. Which one does it have to pass through? Is it ever something that is farther than the closest entry node?
Well, no, because I could compute a shorter path in that case by choosing the closest entry node and then going to the supernode. So, this is a complicated way of saying that essentially what we really want is for every router the distance from that router, let's call it I, to the supernode S. Is that quite right? Is that the distance to the closest entry point? You went You went one more edge too far. I went one edge too far, right? Because I went to the closest entry point and then I took an additional edge. So, we want to do minus one. Okay. So, what does this mean? Well, that means that I don't actually have to have this inner for loop over all the possible entry points.
I just need to construct this new special graph with one additional node. Notice this is not going to affect my run time. And compute the shortest distance from the supernode to every other node in my graph. And then use that as my output, yeah? So, in other words, what is my algorithm going to look like? Well, first, I'm going to construct my graph, right? So, what do I need to do? I have uh If I were to write this out on my homework, I'd have to talk about how I've got these chains of edges between different pairs of routers. In addition to that, I'm going to make one additional supernode, uh and and insert an edge from that to every entry point.
Uh notice that adding the uh entry point here just adds a one to the number of vertices and at most, I guess, an R to the number of edges, which doesn't affect uh asymptotically the size of either of these two sets. So, that's a good thing. Now, I'm going to do uh I'm going to use uh BFS to do uh single source shortest path from my supernode to all other vertices. And how much time does this take? Well, remember that a general BFS takes V plus E time. In this case, V plus E are both you know, look like R. So, this is order R time. Okay. Uh and then finally I'm going to sum over routers um I uh the value of the distance from the super node to the router I minus one to account for that that additional edge that I added.
Okay, and that's the solution to our our problem. Okay. Any questions about uh number two here? Excellent. Go team. Okay. So, now uh let's move on to problem three. Am I Yeah, we're about halfway. Uh okay. So, in problem three Right. So, we're doing um Potter Harder and three wizard friends. The number three here, I believe is actually irrelevant. Um Although, like anytime you see a specific number in a problem, like you should, you know, cache that in your bag of things to remember. And in this case, that was a that was a red herring. Um Potter Harder and um her three wizard friends uh are tasked with searching around a labyrinth.
Yeah? Uh and and in particular, uh there's some some some nice things to know about uh the labyrinth in Potter Harder world. Uh this is really throwing off my dyslexia here. Uh which is the following. Um Right. So, uh what do we know? We know that there are N rooms uh in my labyrinth. Uh and that each of my rooms uh has at most four doors. Okay? Um so, in other words, uh if I think of building a graph out of my rooms, which is like I don't think I'm giving much away about about this problem by like jumping to the solution a little bit. Uh what do we know about the degree of any vertex assuming my vertices are rooms in the labyrinth?
It's at most four. So, that's kind of nice. Uh okay. Right. Uh and all the doors start closed. So, that seems like a useful piece of information to remember. Um but, we have this kind of weird thing, which is that some doors are enchanted. And apparently, uh Po- Po- Oh, my. Uh Potry Harder uh can open up uh certain doors for free, which are not the enchanted doors, and then other ones they have to like, you know, do the the blessing and the holy water and whatever it is the the the happens in in the in in this universe, uh and then opens up that door. Um but, that costs them materials and and um heartache, right?
And so, we want to minimize that. Right? And so, what they're given is basically a map, right? And this includes all of the different rooms, how they're connected to one another, and which of the doors are enchanted, and uh what I want is the minimum number of doors that they have to disenchant. Okay? Now, this problem is like kind of sneaky. Uh and and and the reason why is that there's like the the network that's obvious to build, uh and that turns out to be not quite the right one, and then you can start thinking about adding weights on your graph and going crazy with that, but that turns out not to be the right direction.
And in fact, in Patri harder world, um apparently we're not worried about their physical fitness. In other words, like shortest paths are actually irrelevant in this problem. Do you see that? Because like let's say that I have a really complicated uh annoying problem. So like, you know, maybe I have you know, here's my labyrinth. And um No, we don't even talk about the entry point, like where they actually go in. But just for for fiction purposes, let's say that they enter my labyrinth here. Uh and uh just to be annoying the two doors that are enchanted, remember we could make a graph where all the vertices are rooms and the edges are doors.
Are like at these two end points of the T. So I have a giant T and I enter right in the middle. Now, what is what is Patri harder to do here? Well, obviously there's like since this graph is a tree, there's only so much they can do, right? They Maybe they they they enter here, they walk over all the way to the end to disenchant the door over here. Uh and then they turn around go out to the other end, they they disenchant uh that guy. Yeah? Uh and now they they can reach other rooms. Um Yeah, cuz that's their goal. It's to visit every room. Sorry, I think I skipped that step. Now, there's a few things to notice about this example, which make it a little bit different from the typical graph theory thing, which is once they disenchant this door, right?
They We walk over here and they open it. Well, now they walk over to this other room just to you know, it's like you know those gym exercises you like run to the other side of the room, you like touch the floor and then you run back. That's kind of what they did here, right? They ran to the this room, they tap that vertex, another one to turn around and walk to the other side. They don't pay money again on their way out. Right? So once they open that door, it stays open. Right? And and that's actually quite important. Um cuz it's uh what it does is it makes this problem not look like a traveling salesman problem, which wouldn't be so great.
Um okay. So, right. And moreover, does the fact that there's like maybe I subdivided these edges, I have a bunch of edges here that are all non-enchanted? Does that matter? Like if I had like 5 billion edges here? No, right? Because they only ask in this problem for the minimum uh number of doors that you have to disenchant. Yeah? So, it might be the the the Harry Harry harder walks really far along my graph, but as long as they don't walk through an enchanted door, it costs them nothing. So, what does that mean? Well, that means that like in some sense, the second that I enter a room, I might as well walk to every other room that is connected to through unenchanted doors, and that doesn't cost me anything.
Right? So, sort of as a policy, uh I I should do that, right? I I enter a room, and then I kind of just search around and enter every possible door that I can that doesn't cost me an enchantment uh because the those are free, and and my goal is to visit every room. Yeah? Okay. So, here's going to be the sneaky trick. Like, what does that starting to smell like? Right? I open a door, and I want to explore all the other rooms that are that are connected to that one. Yeah, connected component. Yeah, maybe a connected component. But there's a problem. Is it a connected component in this graph? Well, no, like this whole graph is one giant connected component.
So, the sneaky trick is we're actually going to remove the enchanted doors. That was supposed to erase, and it didn't happen. Um but the uh the point is that if we remove the connected doors, these are like the chunks of my map that I can visit without incurring any cost. Right? So, if I think of my graph, maybe there's like a bunch of vertices over here, and then there's an enchanted door, and there's a bunch of vertices over here, and then like two more enchanted doors like that. And like what goes on in here? Like if this is like a giant triangle or something, is actually irrelevant cuz once I touch any one of these, I can now touch all the rest of them.
So, that suggests an algorithm. So, our first step is going to be construct a graph G where the nodes are the rooms. are the rooms. And what should the edges be? Well, if I'm just trying to find these like little clumps of rooms that I can visit for free if I get to any one of them, then the edges are the non-enchanted doors. Okay? And so now, uh in step two, I'm going to compute my number my connected components, which we covered in lecture. Uh the connected components of my graph G. How much time does that take? Well, remember that there are two different algorithms we mentioned that can do this.
Uh this is full BFS or DFS. And both of them are going to take the same amount of time. Right? What is that time? Linear in the size of the graph. Linear in the size of the graph. Okay. So, initially, right? That could be problematic cuz I want order N. Remember there uh N rooms here. But thanks to our degree bound, thanks to knowing that every room has at most four doors, uh you can convince yourself that both the number of vertices and the number of edges are are order N. Which I should probably rush through cuz as usual, I'm I'm going slowly. Okay. So now, what do I have? I have a list of all the connected components in my graph.
And each one is potentially connected to some other ones by enchanted doors. So, in some sense, I could think about This is not to say it's a solution to the problem, but I could think about modeling my problem as making some new graph where like I put a giant vertex in every connected component and maybe I connect them by enchanted doors and I want a path that touches every one of these rooms. But, that's not quite the right way to go. Uh and and and And this is what what catches me by surprise cuz this starts sounding scary, right? Like you've heard of the traveling salesman problem, it like kind of smells like that.
But, that's not actually correct here uh for two reasons. One is that once I open an enchanted door, I can go back through it. Like I can like hopscotch back and forth through that door as many times I want and it doesn't cost me anything. Only costs me something the first time I open it. Yeah? Uh and moreover, I didn't ask you to actually compute me that path. If you read the problem closely, it just asks for the minimum number of doors you have to open. So, this is really sneaky problem uh cuz it turns out there's additional one line of code that solves this problem. That's step three, which I'm going to write before steps one and two just to keep you confused.
Uh and that is to return this number of connected components um minus one. That seems sneaky. Why why is that? Well, what's going on here uh is the following um which is the Let's say that I walk along Remember that my graph is connected. So, what I know is that I can always get from any one connected component to any other. Right? And so, let's just take whatever ordering Notice that the problem hasn't actually actually asked me how to return an efficient path. It just asked me for the minimum number of doors I have to open. So, all I have to do is convince myself there exists a path with this many doors I have to open.
I don't have to actually return it. If I did, it would be wildly more annoying to think about. Okay. So, my graph is connected. So, one thing that I could do is make the world's like Well, uh how do I want to do this? Well, uh let's see here. I guess I could I could come up with an an ordering um that looks like depth-first search of my graph. That should do it. Okay. So, maybe I start at this guy. I just started some arbitrary vertex. I'm going to do depth-first search, but rather than on the full graph, on this kind of meta graph where I've clumped together rooms that I can get to with no cost, right?
So, what I'm going to do? I'm going to start walking outward toward this guy, and then it does first search, backtracking, and then going back down. And if you think about it, remember that you know, in depth-first search I have this property I never need to revisit a clump once I've I've got to it once. Well, the total number of doors that I'm going to open is exactly the number of connected components minus one, cuz as soon as I've done that, my my depth-first search is is is done here. Yeah? Uh in other words, that's the number of of nodes in my graph. So, if I took What would be a better way to to So, I'm noticing that in my head this was easier to articulate than in words.
Um Here would be a way to do it uh would be uh Maybe add some more enchanted doors to the Maybe add some more enchanted doors. Yeah, that's true. Actually, my problem's a little too easy. So, as long as my back my my depth-first search backtracks along the paths it's already found, then for every reaching out into this tentacle, and then reaching back, and then reaching to a new place, I'm not going to traverse an enchanted door that I don't need to uh cuz I've already I've already seen the location. Um So, you're traversing the tree with Yeah, yeah. So, there's a I've I've got a shortest path tree that's going on here.
Actually, I guess a breadth-first search would be a better example. Um In fact, here's Okay, let's be concrete about it. I'm sorry, you're I I I should have thought about this more carefully than I did at home yesterday. Um one thing I could do would be to compute a shortest path tree from one vertex in this graph to all the other ones. In particular, that gives me the the shortest path. And I could traverse that tree to one node and then traverse it all the way back and then traverse it to a new node and then traverse it traverse it all the way back and so on. This is not an efficient path from a walking perspective, but from a door opening perspective, it's extremely efficient because it's a tree, right?
Uh and remember that the number of edges uh in a spanning tree of my graph is exactly number of of of of uh vertices in my graph minus one, uh which is exactly the the property we have here. Sweating for a second there. Okay. So, now in our remaining uh 30 minutes here, uh we got two more problems, which is more than enough time. Uh especially cuz the last problem is is is more of a combinatorial and less algorithmic, so I I think it's okay to focus maybe talk about that at a high level um and show a fun plot. Okay, so for problem four, uh we have an airline uh Purity Atlantic. Uh that's that's cute uh Jason, really?
Um and it's owned by Bri- Brichard Ransom. Did I get that right? Uh and Purity Atlantic uh has a cute uh sale. This is not like a cute angle, I suppose. Um which is uh essentially the following, which is that you can book an itinerary where you have your home city and then you choose, I believe, three other cities that you want to visit. And then Purity Atlantic, um you know, maybe you're on your honeymoon and you're not concerned with price, uh but rather just the efficiency cuz you don't want to spend your whole time in an airplane. That's particularly true this month. Uh then uh what do you want to do?
You want to minimize your total number of connections, right? Cuz as we all know in um spring 2020, we don't want to spend very much time in airports, yeah? Uh so right. Uh so how do we do that? Well, you know, we make a website where you tell Purity Atlantic the cities that you want to visit and your home city, and they give you back an efficient itinerary that minimizes the number of connections. Okay. And the question uh is how do you actually do that, right? How do you um compute the the best itinerary uh that minimizes the number of flights he has to take. So what are our variables? And sometimes it feels like the variables are all the different permutations of the cities you could visit, right?
I could like go to I don't know, Cambridge uh Boston and then Cambridge, the UK. Maybe you're doing like a university thing and then you I don't know, Budapest and some other place. Or you could do those in any other order. Um and that feels like it should be factorial, which would be bad news. But this is one of these problems which um I suppose a computer science theorist might call fixed parameter tractable, but that's sort of an overkill uh term here. But essentially, as long as you ignore all the factors that make this problem hard, then it's then it's easy. Um a different way to put it is that uh okay, if I'm only visiting three cities, what's the total number of possible orderings of my my my three cities?
Class? So I have city A, B, C. I could do BCA. I could do BAC. Yeah, fine. Jason. Uh I'll do that. So this is what we call direct proof mathematically, uh which are all the possible ways um to visit three cities. And now by my direct uh proof, I claim there are no other ways to visit three cities. Uh and in particular, there are 1 2 3 4 5 6 uh different orderings of the cities that I can visit. Notice that this is a constant in my problem. I am not asking you to make a website that takes like the total set of cities that you want to visit as a couple and order them. It's specifically three. You might also notice that six is three factorial, uh which is perhaps a more efficient way to get to that same bound.
Okay. So, right. So, there's there's six different orderings of the cities. And in each case, uh what am I going to have to do? I'm going to have to compute the sum of going from my source city to city the first one, from the first one to the second one, from the second one to the third one, to the third one back to the first one. Okay? So, what do I need? Well, I need in some sense, if I want to be conservative about it, just the cost of flying from every city to every other city, but that's not quite right. I only need the cost of flying from every city that you have specified as a city you're interested in to every other city that you specified that you're interested in.
Yeah? Okay. So, in particular, I go to my new one. Um right. So, in this problem, we have C cities and F flights. Yeah? Um okay. And initially, it might seem that we have to compute a ton of shortest paths, but like if I want to go from Boston to Budapest to London to I'm running out of cities, Paris and back to Boston or whatever ordering I prefer, do I need to worry about the shortest path from you you you Nebraska to California? Potentially not, right? Like that could be irrelevant. The only ones that I care about are those four cities that I've identified. Okay? Um so there's there's three factorial possible permutations.
And at the end of the day, well, there's 2 * 4 choose 2. Um if you're wondering, this is 12 or big O of 1 pairs of cities. Um meaning that like uh uh for uh itinerary purposes. itinerary Okay. Meaning that uh if I always enter an airport in one of city A, B, C, or my hometown, and always exit through another one, so then there's four possible cities. I choose them two at a time. Um notice that flights might not be ordered. Like I might be able to get from one city to another, but then maybe the airplane has a connection or something, so going back is a different cost. But totally, there there's there's 2 * 4 choose 2 uh different pairs of cities that I could enter or exit from.
Okay. So now uh what am I going to do? Uh well, so I can compute the 12 different shortest paths that matter in my my graph. So when I say shortest path, what do I mean? Well, I'm going to construct a graph G with one vertex per city, right? And one edge per flight. And notice the the number of connections that I need to make, the minimum number between any city and any other city, is equal to the shortest path, the length of the shortest path minus one. Right? So, like maybe I have, you know, like here's Boston, here's London, here's Paris. B L P for short. Right? Then the length of my shortest path is two.
And the number of connections I have to make is one cuz I stop through London, you know? So, what am I going to do? Well, for every pair of cities um in in this uh oops Uh no, that's okay. Uh in the set of the source city and the three cities you want to visit, I'm going to compute the shortest the length of the shortest path. Right? So, this is the min the minimum number of connections I need to get from any one of these to any other one uh in my graph G. Well, how much time does this take? Well, there's 12 such pairs. We already argued that. Right? And how much time uh uh does it take to uh actually do uh shortest path say using breadth-first search?
Linear time in the size of the graph. Linear time in the size of the graph. I think Jason actually has a t-shirt that says that. Um well, in this case, remember that's big O of the number of edges plus the number of vertices. But just to make your life a little more annoying, the number of vertices is the number of cities, the number of edges is the number of flights. Right? So, this takes 12 * O uh C plus F time, which of course is just O of C plus F time. Notice, this is one of these things where we're being sneaky. We told you that you specifically visit three places, and that's where this number 12 came from.
Right? If we'd said that you wanted to visit M cities, then this would be a very different homework problem. This is one of those things you got to remember, right? Where uh we've given you a few constants and you should use them. Okay. So now uh what can I do? I can iterate over every permutation of A B C right? So this is like saying I go from my source to city one to city two to city three back to my source. Right? I add together and compute the cost. The cost of that trip. And remember cost in this case is is equal to the minimum number of connections. And then I return the minimizer. So I say like is it cheaper for me to go Boston, Budapest, Paris, Boston, Paris, Budapest, and so on.
So I have a four loop over permutations, which generally is frowned upon. But in this case, because we told you you're visiting precisely three places, how many steps are going to happen in that four loop? Well, we actually wrote them all out over here on our board. It's exactly three factorial or six steps. Right? 3 * 2 * 1. Which is six. Okay? So right. So at the end of the day, this uh four loop is going to take well, order six time. Uh which of course uh is just order one, so it doesn't really contribute to our run time at all. And our entire algorithm runs in C plus F time. Okay. So uh right.
So this is one of those problems where you're really taking advantage of the constants that we gave you. We said you're visiting three cities, so use it. Incidentally, as a computer science theorist, if I said you're visiting exactly 17 cities, well, what would be our our our our numbers now? I mean, they would be 17 factorial and then like 17 choose two. Those are big numbers, but they're still constants. So, for purposes of this class, that would be okay. But, the second that I gave it a name like M, then I got to think about those factorial uh things a little more carefully. All right. Um so, that's this problem.
So, so the basic trick here um was that like, yeah, it looks like all pairs shortest path, but it's not quite. It's all pairs of things that you're actually going to travel between shortest path. And since that number of pairs is finite, it's just 12, uh that's that's an okay thing to do. Okay. How we doing? Ah, 15 minutes. Perfect. And want to do the last problem, and I think I've managed to uh get myself in exactly that position. Okay. So, the the very last problem on this homework, which again, this homework really follows the prototypical 6006 breadth-first search, depth-first search homework.
I I feel like they all fall into a similar pattern. Again, we all these resources are available to you guys. Should you you should look at them. The uh you know, we're not trying to hide anything. Um this problem involves uh solving a pocket cube, which is like a little mini Rubik's Cube, which is 2 by 2. Um and and it looks like this. Uh Ah, there's chalk. Actually. Here we go. Right. So, here's my Rubik's Cube. Looks like a cube, which I'm having some trouble drawing. Uh uh and and in particular, it's 2 by 2, uh which makes it a little easier than your typical Rubik's Cube. Okay. Um and in particular, we're going to mark uh some faces.
Sneakily, they used a little geometry term here, which is Q. So, here's face F0. I'm sorry, you can't quite see that, but the top face is F0, in case you're wondering. Uh the left face is F1. And the front-facing face here F2. Notice that we've identified these by like vectors that point 90° out from the face. These are called normal vectors. If you want to define those rigorously, you can take my uh my grad level class. Uh but for Rubik's Cube, it's not terribly difficult. Uh but in any event, um I can talk about flipping this Rubik's Cube in a pretty easy way, right? Which is that I like I'm going to fix one corner of my cube.
So, this is like the corner that I'm holding onto with my hands. And now, I can grab what? The top, the side, or the front of my cube, and I can rotate it clockwise or counterclockwise. You can convince yourself those are all the possible ways that I could uh sort of mess with the state of my cube after fixing one corner. Okay? Uh right. And so, this problem basically is involving um sort of a very typical trick. In fact, a lot of the history of these different search algorithms, breadth-first search, depth-first search, A*, which I guess we won't really cover here. Um date back to what, 20, 30 years ago we would have called artificial intelligence.
Um these days, that has a very different meaning. Um but back in the day, AI was all about like solving board games and, you know, Rubik's Cubes and and all these kinds of things uh using algorithms, right? And the way that they would do that is by searching different spaces of configurations, right? And so now, uh if we think of every face of this cube as painted with a color right? Then there are different configurations of my graph that I get by like flipping the the three sides, right? So, if we think of there being a vertex for each state of my cube. Um, where state here means like the coloring of every face on my my Rubik's Cube, um, then there's an edge for every move.
And in this problem we encoded a move as a pair J {comma} S where it's saying that I'm going to rotate face FJ, where J is between I guess 0, 1, and 2, um, in direction uh, S, and we can just index that as like plus or minus one to kind of say counterclockwise or clockwise. Right? And so this is kind of a a cute thing, right? Where your graph has a bunch of vertices, which were all Rubik's Cubes. That's cube. Uh, and then there edges if I can get from one to another by doing one of these moves. Uh, and this is a nice abstraction because if I want to solve a Rubik's Cube, uh, in the the most efficient way possible, one way to do that is to compute the shortest path from my current configuration to the, you know, the Platonic Rubik's Cube, right?
Where all the colors are constant on the different, uh, faces of my cube. Uh, and so that's like a a sort of basic, uh, identification that happens all over the place in search strategies. Where like I'm going to think of every vertex of my graph as being the state of some system and every edge as being a transition from one to another. Uh, and then paths in this thing are kind of like different ways of solving my puzzle, right? So like a different one would be, you know, I don't know, every vertex is a chessboard with the pieces the chess pieces scattered on the chessboard and every edge is one chess move by one player or the other.
In that case you have to be a little careful because you want player one or player two to go back and forth from each other, but I'll let you think about the reduction there. Okay. So, uh right. This problem I think largely is mostly just fun like combinatorics rather than algorithms, but there's a little bit of algorithms hiding in here. Um so, they want you to argue that the number of distinct configurations of this Rubik's Cube, this 2 by 2 guy, uh is less than 12 million. This is nice cuz 12 million is a number that computers can actually cope with. Um and so, there's a pretty straightforward uh argument there.
Right. Uh so, in particular, um here's a cube. How many corners are in a cube? Eight. Eight. Thanks. I I hid one back here, in case you're wondering. So, uh let's say that I I fix a corner of the cube, like we've done that. Right? Then, every time that I rotate one of the faces of my cube clockwise or counterclockwise, I'm essentially like taking one corner of my cube and like sticking it in another place. Right? So, in all, seven corners of my cube can move. And if I'm not worried about like, you know, it could be that like some of these permutations are not actually achievable by a set of steps, like maybe I'd have to break my Rubik's Cube and glue it back together.
Um but, if I'm being conservative about it, there's of course less than or equal to seven factorial different configurations of the corners. Right? So, in other words, every time I rotate my face, one of the corners ends up in a different place. So, there's seven factorial different ways that that could have happened. Okay. So, that's part of my bound. Remember that I'm trying to bound the total number of configurations here. And essentially, what I've done so far is I said, "Okay. Well, there's a bunch of cubes in my 2 by 2 Rubik's Cube. So, I'm going to like unglue this entire cube, take just this corner, and stick it up here.
And there's like 7! different ways that I could do that." But I still have to account for the fact that I pull this piece off, I stick it on the top, but I have to figure out its orientation. I can still rotate it about this corner. And in fact, there are three different ways that I could rotate it. Right? You can kind of You can see it, right? 1 2 3. Yeah? So, in all uh so, each corner can rotate um three ways. So, that means that I have 3 * 7! uh different configurations as an upper bound. And this number is, wait for it, 1 1 0 2 2 4 8 0. Um the problem asks you to argue that your upper bound is upper bounded by 12 million, and indeed it is less than or equal to 12 million.
Is that 3 * 7! or Oh, I'm sorry. Um right, cuz there are seven corners, each of which can rotate three different ways. So, actually 3 to the seventh power times 7! Thank you, student. Um Okay. Right. So, uh let's see here. Really quickly moving here. The next problem says state the maximum and minimum degree of any vertex in my graph. First of all, do I expect vertices to have different degrees? This is kind of a goofy problem. Like, what would it mean to have a vertex uh the the somehow has lower degree than another vertex? It would mean that there's some configuration of this cube for which there are fewer moves that I could do to change it than a different configuration of this cube.
And that's like obviously not the case, right? Because when I when I flip one of the the faces of my cube, all I'm doing is I'm moving the colors around. I haven't like somehow changed the physics of how Rubik's Cube works. Right? And so uh I think this was just intended to be annoying by your instructors. The the the min degree is equal to the max degree. Uh and in fact, the degree of every node in my graph is constant here. The one thing that's worth noting here, what I haven't argued, it turns out I think to be true, but what what I haven't argued is that like I couldn't rotate a face and actually end up in the same configuration.
Like maybe for some reason I have like red all the way around the outside, so when I rotate it, nothing changed. That obviously isn't true, but I I haven't argued it carefully. Um but as long as I don't worry about my graph being simple, like I'm okay with self loops, uh then the degree is certainly uh constant. Yeah? Okay. And in fact, I don't think that can that can happen in a typical Rubik's Cube. Well, I think the point is to say how what the degree was. Oh, yeah, indeed. The So, we haven't computed the degree, but we've we've argued that they're equal to one another. Okay, so now I have to have to compute what that degree is.
Um and here's how to do it. So, of course uh well, this I think is actually even easier than than than than the first part. Essentially, remember you have three different options for faces that I can rotate. I can rotate the top, the front, or the side here, right? So, there's uh three faces that we could rotate. Uh okay, and how many different ways can I rotate them? I can rotate them counterclockwise or clockwise. So, there's two directions. So, in all there's degree six for every vertex, right? There's six different ways in or out of of a a vertex here. Okay, so the next part of the problem gives you a piece of code and then does breadth-first search on this this graph and it's super super slow to give me the distance to all the other configurations.
And Jason conveniently has run it on his laptop here. I don't I'm nervous to touch your laptop. I I don't care so much but I don't you know, I I don't want to infect you. Yeah. Right. So, we have a piece of code that explores the graph of all the configurations of our cube by by breadth-first search and then sort of gives me the shortest path I think from the base cube where all the faces are constant to all the other configurations that are reachable. And generates a plot. Right. And so what they ask is to um figure out the total number of configurations that explores. One thing that you'll find out um center down.
Uh is that it explores pretty much a third, in fact exactly a third of all the possible configurations of my cube. I think we can see that here. Um so I guess it runs this whole thing. You sum them all together. Um Right. Oops. That's okay. Um and so in fact the kind of fun fact that you can learn about the 2 by 2 by 2 Rubik's Cube is that there's actually three connected components in this graph. So, in other words, there's sort of like three different Rubik's Cubes you can make modulo all the different flips that you can do to the uh to the faces and those correspond to three corner rotations of of one of the corners of the thing.
Okay, so uh uh Right, so then the um the next part of the problem asks you to state the maximum number of moves needed to uh solve any Rubik's Cube. And you can see it in this plot. So, what this plot is showing you is the size of the level set of this uh this distance uh function for for every distance. So, I think technically it looks like zero, but there's actually this is at a one here. We should say there's there's one uh vertex at distance zero, which is the source. Right? And as we move farther and farther out, our tree is expanding and we're seeing more and more vertices. Apparently, most vertices are approximately distance What is that?
11 or 12? Uh 11 away from the original. Then eventually, I explore the entire graph and I'm done. And you can see that the farthest away vertex uh is 14 away, meaning that the most annoying Rubik's Cube to solve can be solved in 14 steps for the 2 by 2 by 2 uh pocket cube. I'm sure that Jason probably knows that the the equivalent of this number for the 3 by 3 by 3, but I have no idea what it is. Um I'm impressed if he can calculate in his head like he looks like he was about to try. Uh but I digress. Uh right, so in other words, um this is actually a fancy term for uh uh you know, we talked about the radius of your graph in the first problem.
Now we've got the diameter, which is Well, not necessarily two times the radius the way that we've defined it here, but but actually almost. Um uh I think within some constant of that. Okay, so, uh Right. So, notice that the vertical axis here is really big. And this is explaining why this BFS code is so slow, right? Because these are all the different configurations it has to hit. Um or more accurately, if I take the Y position of each one of these vertices and sum up its height, those are all the configurations that are reachable. Uh and those are all the steps that BFS needs before it's done.
And so, that number is in the ooh certainly in the millions. Yeah. Okay, so then the last part of this problem which it conveniently looks like I'm I'm low on time to solve um but I'll refer you to to to the solution anyway um is is asking how we might do this uh faster. Um and so in particular what it says is uh let's say that I have a total of n configurations uh for my Rubik's Cube. In this case, it turns out that that's that's like roughly 3 million, I think. Okay. And now I want an algorithm that gives me the shortest uh sequence of moves to solve any Pocket Cube. Man, I'm really ravaging the chalk today.
Um and I want to solve any cube uh in a number of steps that looks like 2 n to the ceiling of w over 2 uh where um Uh let's see here. The code provided Sorry, this problem changed on me this afternoon. Right. So uh where n sub i is equal to the uh number of configurations reachable within i moves. Oh good. I see what we did here. Right. So like if this is my base cube, then we've got like maybe like a six different 1 2 3 4 5 six different cubes that I can reach from those and then there's six cubes I can reach from all of those. But of course some of those might be pointing backward um or to each other.
Uh but this is the number of things that are reachable in i moves. And they asked for an algorithm that finds the shortest path in this amount of time. By the way, big n typically exponentiates in that subscript there. It's the This looks innocent, but it's not. Um the basic trick here uh is to do I'm not going to bother writing it down. We'll just talk about it for a second and call it for the day. Well, I'll draw a picture. So, the breadth-first search algorithm that we've thought about so far chooses a vertex and then computes level sets outward from that vertex until it maybe reaches the destination uh that you want to hit.
That doesn't quite work here in the Well, I mean, it does work, but it's going to be quite slow because like let's say I had bad luck and I were in that 14 vertex, right? Then somewhere in there I'm going to hit this big height uh which is uh sitting over the 11 um before I can get to the vertex 14. So, the trick here is it turns out that I can do it by only ever getting to seven. Uh and the way that I'm going to do that is instead, I'm going to run BFS sort of in parallel for two different vertices, right? The source and the target. So, in this case my current cube and the cube I would like it to be, like the solution to the problem.
I'm first going to compute the the level set one of that cube, then level set one of the next cube, then level set two, level set two, three, three. And notice that eventually they're going to intersect pretty much right at the midpoint. And so, the size of the level set I never need to compute a level set that's bigger than half of the shortest path uh length after round up to be conservative about that. And and that's why I get this factor here. So, this is a nice little trick for for reducing the uh search size. This is another kind of standard trick. If you look at some of the uh code people use for for solving board games algorithmically and so on, I think they typically uh sort of search from the beginning and end state outward to and and try to meet in the middle uh for exactly this this reason, which is that exponential growth uh as we all know can be uh quite problematic.
All right, folks. So, I think we're just about out of time and I've certainly worn myself out. Uh so, with that, hopefully we'll see you next week, and uh yeah, I hope everybody's doing well.