Quiz 2 Review

Key Takeaways

okay welcome back to 6006 we're going to have a this problem session we're doing a quiz 2 review we're in a much bigger room today so i have a little bit more board space so i just want to go through what's going to be covered on the exam first off the scope uh now quiz one material will be fair game for this uh this quiz but it's not something that's gonna be explicitly emphasized or anything like that right you should know that you know when we're storing graph data structures that they can achieve certain running time bounds and and and that kind of thing but we're really going to be concentrating on graphs the six lectures that we've had on graphs the two on unweighted graph algorithms and the four that we had on weighted graph algorithms they covered the material that was uh covered in the two problem sets uh problem set five and problem set six now uh we only usually this this material covers uh three problem sets worth of material uh this term it's covering two problem sets worth of material uh so just keep that in mind when you're when you're studying and you wanna go look back on previous material okay in general there's lots of graph problems that we've talked about how to solve there's really a small number of graph algorithms but they can solve a lot of different problems okay and so we we saw two algorithms to solve the graph reachability problem single source uh what is reachable from me right uh and i can only search a connected component of my graph from me right and the connected component from me is actually upper bounded asymptotically by the number of edges in my graph because a a spanning tree of my component has at least or has v plus one edges right and so uh the number of vertices i can reach is upper bounded by the number of edges in my graph asymptotically anyway uh graph then then uh we talked about exploring an entire graph even if it's disconnected not necessarily from a source right just just touching every vertex in a graph of course we can just you know touch every vertex in a graph right i can look at the adjacency representation of my graph and just go through it but this is really we're trying to explore the whole graph maybe count how many things are reachable from each other in the graph and this is what we had a we talked about exploring a graph and counting the size of connected components in a graph in an unweighted graph right and we could do this via full bfs or full dfs it's basically putting a loop around one of these graph reachability algorithms to explore an entire graph by exploring component by component and when i'm done with a component i find a vertex i haven't reached yet before and explore it again okay and that still gets linear time in the graph v plus e then we had uh special types of graphs directed graphs directed acyclic graphs uh that we could use we proved this property of if we ran dfs full dfs on that graph we could actually get topological sort of that graph basically an ordering of the vertices in the graph such that all edges go in one direction with respect to that ordering like all forward in that ordering right and we could actually use that to detect cycles in a directed graph by just looking at the topological sort order and seeing if if look at the finishing time the reverse finishing time order of dfs and just checking to see whether it was a topological sorter right because any back edge there would correspond to a cycle in our graph because the proposition was that if our graph was acyclic doing this procedure would give us a topological report okay then we had an algorithm bellman ford that uh was able to detect and find negative weight cycles in our graph in the way that we've presented it in lecture and but but normally we concentrated on these two problems single source shortest paths and some a little bit all pair shortest path shortest paths right uh first in the unweighted context and then in the weighted context for the majority of the lectures okay so let's move on to what those single source shortest paths algorithms were we had kind of to me in increasing in generality here the first restriction is bfs already solves unweighted shortest paths in linear time in the unweighted context that's all good but for uh weighted graphs regardless of the weights if we had this very strong property on the graph that the property that the graph didn't have any directed cycles then we could get this in linear time via dag relaxation and then for general graphs we had these increasing or decreasing restrictions on the weights first we had the restriction was that they were unweighted and that that's the bfs constraint or that they're non-negative that's the dijkstra constraint and if we have no constraints that gives us bellman ford and they increase in time in general you want to choose an algorithm that's higher on this list but sometimes the algorithms higher on this list don't apply right if you if on a quiz you come to a graph for which uh so it's not a dag but you use dag relaxation that's no longer a correct algorithm right and so you're going to get fewer points than if you happen to use an inefficient algorithm that is correct right so if i just whenever i saw shortest paths i used bellman ford right it's the slowest thing that's probably going to be a correct algorithm it's not necessarily going to be the most efficient algorithm but you'll get more points because it is a correct algorithm then if you apply a faster algorithm that doesn't apply to your problem because it's not going to solve it correctly does that make sense okay so and then in the last lecture we had we talked about all pair shortest paths and really running a single source for just paths from each vertex is pretty good in most circumstances we don't know how to do a lot better for for a lot of these and then johnson gives us basically in this last line of our graph restrictions and weight restrictions uh where bellman ford is right there we can actually get a speed up over v times bellman ford uh by kind of two tricks right re-weight the find if the graph has negative weight cycles and if it doesn't then there exists a re-weighting of this graph so that all the weights are non-negative but the shortest paths are preserved and so we can use dijkstra v times and get that that running time instead okay so that's that's just an overview of the contents that we've covered so far just want to go right just brief overview of what these algorithms actually do dag relaxation uh you know finds a topological order of the thing using dfs looking at the reverse order of the finishing times you prove that that's a top a reverse topological order and then we relax edges forward in that order because we know that we'll have found shortest path distance to everything before us before and we use that invariant to prove that this constructs it in linear time bfs explores things in levels right out increasing in the number of edges as we go out and i just process all of the ones in the same level at the same time and dijkstra generalizes this notion by saying well i don't know all of the things that are in the same level per se from fr as i'm going but i can using a clever use of a data structure find the next one i should process in kind of a topological relaxation order to find shortest paths when the weights are non-negative because in some sense i know that once i've reached things from a short distance i will never have to update their distance again that's that's kind of the invariant that we're having with dijkstra and then bellman ford essentially duplicates our graph so that each node corresponds to reaching a vertex using at most a certain number of edges and then that duplicated graph is a dag and we can run dag relaxation so that's the basic idea of all these algorithms uh when i approach problems on a quiz uh there's a couple things to keep in mind there's kind of two two things that we have to worry about when we're you're looking at a graph problem in this class the first thing is i might not see a graph in my problem right i mean on quiz 2 you know that there's going to be a graph in your problem because we cover graph algorithms on on this quiz but in general some of the word problems you've been seeing on your problem sets there's no graph defined for you they give you a an array of things or a set of things or you know some connections between some things right and that might be a graph that you want to make but uh kind of defining a graph is an important aspect of that problem solving that is not necessarily something that we've covered in lecture right we've not emphasized that in lecture so much right but it's something that you've had to do on your problem sets and something that will appear on the quiz right so it's the part of this is a modeling context can you look at a real real world situation or maybe not so real world but non mathematical context right and you're trying to abstractify put it in the language of this class the mathematics of this class make a graph so that solving one of the problems that you know how to solve can adequately solve the word problem that we gave you right this is a modeling part so i always suggest when you see a word problem on quiz 2 or on your problem set right it's that uh see if you can state cleanly an abstract problem related that if you knew the answer to that abstract problem you could easily solve your word problem can make it a little easier to decouple the complexity of the word problem right then you don't have to think about i don't know uh you know various strange characters we come up with in in weird contexts and they're weird conditions right if you can map that to just a graph with a certain with certain properties and solving an abstract problem on that graph that might be easier for you to think about and apply the material in this class so you don't have to worry about oh do i have to remember that roads are connected to five other things or do i have to remember you you maybe you're given as the input a sparse graph or something like that right that's a little easier to think about for when applying this material okay and so con converting your problem into a finding a shortest path problem or finding a cycle or finding a topological sword or connected component or a negative weight cycle or any of these kinds of things right can make it easier for you to think about uh it's not like fundamental material in this class that's that's that's super uh that we need to lecture on but it is really important for you when you're out in the real world looking at problems to be able to make that transformation from a a non-mathematical context to a mathematical i like to think of this as a modeling part of the problem but in general once you've got that nice abstract problem uh then in general you you might have a graph but it might not be the graph that you the only graph you want when you're solving this problem right that might be the input graph that you have but in general a lot of the kind of tricks of this thing is not modifying the algorithms that we gave you if you find yourself trying to modify the algorithms we gave you that we spent entire lectures on proving their correctness and things like that that's maybe not something you want to be doing on an exam because then you're going to be writing pages of derivation and proof that these algorithms work this unit in particular is much more on the let's reduce to some very powerful black box that we showed you how it works and so because that's the framework here the way in which we introduce complexity into problems is to make the graph non-obvious on the thing that you're supposed to apply right and so the graph that we give you as the input may be different than the graph that you'll want to use to solve the problem and here are some strategies that you can use to modify a graph like if if you uh if you want to store state as you're traversing this graph right you can expand the number of vertices in your graph to keep track of what state i'm in right i can have a different vertex for every possible state i could be at that vertex right you know in your problem session you had this guy who's drinking when he got to bars right and or or every third time and you need to remember how many times it's been since i've been to a bar right or i had a drunk at a bar and and so you can duplicate the vertices to be able to store that information another thing if you if you if you need to search from multiple locations at the same time or search to multiple locations at the same time right you can simulate that without having to run an algorithm many times you can simulate that by adding a an auxiliary node an extra node in your graph with edges to those sources or to those sinks and run a a single source shortest path algorithm from that that that super node sometimes we call it uh to get better performance it's kind of a an efficiency we're adding efficiency by changing our graph to fit the algorithms that we know to solve efficiently and then the last thing maybe it helps to pre-process the graph in some way right some edges in the graph that we gave you might be forbidden or may need to be traversed in one direction rather than the other even though the problem statement seems kind of seems like they should be traversable in either direction right and doing this pre-processing of the graph could mean that you break up your graph into your connected graph into a set of you know disconnected components that you need to find or makes a undirect makes a a cyclic graph acyclic right or prunes part of the graph that you don't want to explore i never want to touch on my my way to get to to a location right so these are all really common strategies that we have you know uh duplicating graph adding auxiliary vertex vertices or edges to the graph i don't know the context in which we add edges it's an interesting question and then preprocessing kind of filtering out the graph or transforming it in some way to to give it properties that will allow us to solve the problem better okay so any questions about the problem solving strategies that we have or or the content the kind of baseline content of this class this is kind of an overview of the lecture type material where we're not necessarily applying this material in lecture the rest of this uh you know quiz review session will be on applying this material to some uh a quiz from a previous term uh some of those problems okay so yeah what are some common ways people uh lose points that's that's great thing we i'll add it to the notes uh when we post uh so common things that people lose points on in this unit when they're solving problems you're given a word problem and you don't define a graph right super it's as easy as that you start solving assuming that we know what graph you're talking about when the implicit graph in the problem may or may not be correct but we don't there's no graph defined in the problem right so you need to define a graph in the problem so that's the first thing the second thing is a lot of times it's really useful just as a strategy when you construct that graph tell us how many vertices and edges are in it tell if tell us if it's acyclic right tell us what the weights are on each edge if you don't tell us these things it's really hard for us to base to judge your application of algorithms based on that graph because you know you if there's redundancy there even if you define for every vertex in my original graph i have 10 vertices or blah blah right and maybe you're adding a super node or all these things it can be difficult for us to follow how many things are so you do that bookkeeping for us your graders are going to be a lot happier um and that so so uh common mistakes not defined a graph not uh specifying your graph completely and then uh not uh i i would also suggest that instead of just applying an algorithm to a graph that you clearly state the problem you're solving on the graph first right i want to solve this problem because we've given you number of ways to solve that problem on the graph right and if you happen to choose the wrong algorithm then maybe that's like separating off the problem from your implementation of how you solved that problem can maybe help you get some points for stating the problem you're solving even if you choose the wrong or an inefficient way to solve it right so that that can really help decouple uh uh some of the the things that we're going to give points on in this class right so usually what we're we're breaking up the uh a graph rubric on grading in did you describe a graph right did you modify it in in a way that's going to help you solve the problem did you identify a problem that you need to solve on this thing did you use a correct algorithm to solve it did you analyze the runtime usually involves is the size of my graph not too large and what is the running time based on that graph and then the argument of correctness in this unit is basically like i constructed a graph that has properties so that shortest paths in this new graph correspond to whatever it is that i want in the original problem right some statement that links the problem you're solving in your problem statement to the the problem you're solving on your graph it's that's a really good statement to have to bring together correctness but aside from that statement you're mostly relying on the correctness of the algorithm so you don't need to do much on the correctness side okay but uh forgetting to analyze runtime is a is a big thing okay so those are a bunch of tips i'm going to add them to the end of this slide after after the lecture great question any other questions all right let's get to solving problems all right so these uh problems that we're gonna solve are from uh spring 18 quiz two uh slightly modified um but uh you know we're just gonna go through them uh one at a time so the first problem we have uh we have an image of black and white squares so this is like a pixel grid you think of it like as a you know a bitmap on your computer right and what we say is each white pixel is contained in a blob okay but what what what is a blob i don't know right okay i'm kind of giving you an implicit representation definition of what a blob is two white pixels are in the same blob if they share an edge of the grid okay so this kind of tells me this this graph has an edge if these these pixels are adjacent they're both white right that's what it means but an interesting part about that definition is that it kind of is transitive right if i have a white pixel that shares an edge with a white pixel a that shares a uh what let's start writing things on the board shall we probably instead of me just talking at you right we have kind of a pixel grid here okay and i don't know how to do this with the chalkboard because it's white versus black i guess i have to color in the white things these are all white all right so these guys are in the same blob right because they share an edge these guys are in the same blob okay but because they share an edge in the pixel grid these guys are also in the same blob because if these are in the same blob and these are in the same blob there's a transitivity argument here right this this guy needs to be in the same blob as that guy and then it says that black pixels are not in any blob okay and so i'm given an n by m array i never remember which one comes first but we have dimensions of this thing as n by m so we have n times m pixels uh and so we're describing uh essentially in a linear time algorithm to compute the number of blobs in the image why do i say linear time it's because for every pixel in my grid i needed to give you a specification of whether that was white or black right and so yeah if i naively gave you the input of this algorithm with a word per per one of these pixels that would be the input size of my right and so even though this has looks quadratic right the actual input size has is what we define as linear right and so we're looking for a linear time algorithm to count the number of blobs in the image okay so what is a this is a little underspecified as a problem i admit um i i hate to admit that i was involved in this class at that time but the idea here is if these are uh share an edge then everything the the observation here is if i just draw this picture i notice that anything kind of that's reachable through white white connections is going to be in the same blob right so this is a blob and this is a blob and this is a blob and this is a blob but right there's no path here this this black part is not part of a blob now actually there's nothing in this specification that doesn't say that says that we couldn't have these things be in the same blob okay so that's a little confusing maybe a source of error that there's a source of error that i had when reading this problem after a couple years um but you know when you are looking at a problem the if if everything could just be in the same blob then you just return one and this problem is not so interesting right so the right way to interpret this problem i mean i would not need n times m time i could just say one right so in in some sense i'd like there to be something interesting in this problem uh and and having these things that are not reachable from each other be different blobs is kind of the more algorithmically interesting thing to have and so what what is this then right this is just a pixel grid there's there's adjacencies right there's connections between pixels but in particular i really only care about the connections between white pixels right hard to draw on here but this component has a graph that looks like this this component is a single vertex this one's a an edge here and here's a singleton there and if we were to construct this graph we would have an unweighted graph such that the number of blobs in my pic image would be the number of connected components in this graph right see how i'm relating the thing that they're asking for in the problem to a property of a graph that i'm constructing okay so that's that's that's really the key part of argument of correctness that we're looking for is for you to to make some kind of statement connecting the two otherwise you're just constructing a graph and i have no idea what you're doing to that graph right you have to tell me part of it it's about communication to us uh so how do i construct this graph well i can just loop through all of the pixels right look at its four neighbors at most for and if those uh things share are both white then i add an edge we have a we have we're going to essentially have a graph we're going to construct a graph this i told you to do this okay so what is v here then uh v is a vertex for each white pixel right and i can just i mean from the beginning i can just walk through all the things find all the white vertices maybe i identify them uniquely by their x y coordinates in this in this grid that's fine okay so now i have all the vertices and now i want to see what the edges are i can loop through the pixels again and just look at its four possible adjacencies see if any of them are white stick that edge in this set so edge is any two white pixels that share [Music] an edge okay so i can construct both of these things in this in order n times m because there's at most that many vertices i just loop through them and the edges for each pixel i'm only checking a constant number of things and i'm adding them to a set so the number of edges the size of the number of vertices in my graph is at most n times m and the number of edges is at most n times m times four right it's upper bounded by that because that's the number of adjacencies i have in the graph okay you can probably get a better bound in terms of the number of vertices right it can be at most v times four right but that's that's a little stronger it doesn't really matter we're trying to get within the order n times m time bound so anything's fine here so that's the graph we construct and then we can run full bfs or full dfs we've identified a graph we've identified that we want to count the number of connected components in my graph so idea right count connect connected components and then for example using full bfs or full dfs right i wouldn't want you to write both of these algorithms there but when we write up our solutions we want them to uh you know cover the space of student solutions and so we will usually mention it you only have to mention one of them and because these run in linear time this also runs into n times m so all of these things are n times m and we're golden any questions on this question yeah what sort of things would you be looking for to make sure right so when i'm writing down i've i've described to you the algorithm and uh so the question is what kinds of things do i need to write down when i'm proving or when i'm arguing running time of my algorithm and i'm arguing correctness right for running time mostly just check out the size of your graph right state to me what the size of your graph is here in this case it's order n times m and then i state the what the running time is of the algorithm that i have is applied to that right and so because uh full bfs runs in o of v plus e time right it's useful to actually write this down even though right it's not in the terms of our original problem variables it's useful to write this down so that if i mess up when plugging these variables in uh that you know you're showing your steps and so if you mess up arithmetically then we can still give you points but because the size the number of vertices in the graph is n times m the number of edges is n times m i add them together it's still order n times m and that would be a sufficient for an argument of running time and then i was saying for correctness uh most of this the correctness of this algorithm is relying on the fact that this thing counts connected components correctly in my in my graph the key observation on a word problem that i uh uh or or even a graph transformation problem is that the property that you're wanting of the original graph for the original problem corresponds to the thing you're solving in a new graph that you've made right and so here an argument of correctness that i would be looking for that we might allow some weaker statements is uh that the number of blobs in the image corresponds to the number of connected components in this graph that i made okay that's that's really all it needs but i would like a connection between those values okay now why why would you be constructing this graph and finding connected components if that if if you didn't uh if that wasn't what your thought was uh i don't know but it's real it's good when you're communicating to make sure that that's abundantly clear that that's why this is uh i mean you should be able to argue why why these things are uh that is a connected component you could say something like because anything reachable is in the same blob or something like that right okay so that's problem one we got these nice mechanical boards all right so that's problem one problem two is a little funky okay uh it's been reworded a little bit from uh it's from spring 18 so that i could uh point out some other features of this graph we're given a connected so connected is in bold so that might be an important property of our graph that we're trying to communicate to you a connected undirected graph with strictly positive edge weights right so they're mapping to the positive integers where e is the same size as v right so the size of e is the same size as the size of v right so i have the same number of edges as i have vertices we're trying to find a order v time algorithm to determine a path from some vertex s if to some vertex t with minimum weight okay so what's the first thing i noticed i noticed that on this thing i've got a graph problem problem 2 we've got a graph it's undirected it's connected it has this weird property that v equals e or e equals v and weights are positive okay and we're asking for a single pair shortest paths right we want uh a path the shortest path a shortest path between two vertices now if if we just we're given this graph and we want to solve this problem a very easy way to do that would be to just say let's run dijkstra on the graph right this is a graph it has only positive edge weights one direction on this graph how long does dijkstra take on this graph idea one right what's the problem with this it applies right we're in the context of non-negative edge weights we can find single source paths from s to everything else in the graph in using dijkstra it applies it's a correct algorithm what's the what's the difficulty with this algorithm slow too slow right that algorithm would run in o of v log v plus e and in this case these are the same so this is asymptotically smaller than this one it runs in v log v so we're a little off we're off by a logarithmic factor in our running time but you know this would at least be a correct algorithm you know if whenever you approach a problem on the exam and you see a really stupid uh polynomial algorithm that still solves your problem correctly you might as well write that write that down in a line it doesn't it doesn't uh hurt you that much to just write that down because it's possible we give you points for that right but this but but on your exam notice why it doesn't is not sufficient right notice that oh this right this is v notice that this is not the running time bound we're looking for we got to exploit something different okay now this doesn't seem this is a weighted context we have weighted paths it doesn't seem to be in one of the the conditions that we can get a linear time weighted single source shortest path algorithm right uh in particular using bfs we saw a transformation where if as long as the sum of your weights was linear in the combinatorial size of your graph we could use bfs by by making each edge a bunch of undirected edges we don't have that in this context and this graph is undirected i mean so it definitely contains cycles so we can't use dag shortest paths so how the heck can we do this well what does this graph look like here i'm going to take a look at this condition v equals e okay so what does this graph look like it's connected and it's v plus e well how many edges does a tree have v minus one right so in a sense if a tree is the is the smallest number of edges you can have in a connected graph so this has one more edge than a tree right so really what this looks like what our graph g looks like is some kind of tree and somewhere we've got an extra edge in this graph right it's a tree plus an extra edge that's what our graph is okay so well let's take a step back if i just had a tree and i had weighed a weighted graph here undirected and the weights are all positive if if any of the weights were negative how could i solve this problem well every edge is reachable from every vertex i can just go to that edge and traverse a negative weight back and forth and my shortest pathway would be uh infinite for all our vertices that's not the case we have here we have positive edge weights only which means shortest paths are simple and actually there's only one simple path between any pair of vertices in a tree right i basically there's there's one thing i can do and in fact if i took if this was s and this was t t that's that's an x what am i doing okay t if i just ran any unweighted short i mean reachability algorithm i would get a a tree right a bfs tree or a dfs tree right it would visit vertices in some order now actually in a tree it i have to output a tree that connects all the vertices right and that would be this tree right and so in a sense the paths that i got from bfs or dfs in this graph would be exactly shortest paths i would just have to then go and add up all the pa path edge weights along the edges that make sense okay so uh bfs or dfs in the unweighted context can give me the shortest path in the weighted context because there's only one simple path in this graph but we have a complication here that's not the question that we're asking we have an extra edge and now we have a property where there's not just one simple path to t there could be two simple paths right i could go this way around the cycle or it could go this way around the cycle so that's a complication but there's only one cycle if t is over here there's only one path right so if there there is only one path i'll be golden but if basically the cycle can be reached between these two things i could have two simple paths that's the property right we have the closest vertex on so this is the cycle right there's a cycle here if this is the closest vertex to s and this is the closest vertex to t on the cycle then i could take either path around the cycle to get from one to the other and that gives me my two paths but this path and this path right these are completely edge disjoint right in other words any simple path from s to t if i if i find this vertex going through here it can only use one of these edges right because i can't i can't come back to this vertex once i go into it here i got to go out one direction and i can't come back right so it's only one of these two edges so the the idea behind this algorithm is i'm going to find the cycle or in particular i'm going to find this thing s prime on the cycle find the outgoing two edges here remove one and then do my tree searching basically find the shortest path by by running a an undirected i mean an unweighted reachability algorithm which will give me a path back to f the only simple path in that tree right i get rid of this this edge and i do that once and i do it again without this edge so that's that's the idea of my algorithm okay so how can i do fir so i first have to find s prime how can i do that well i don't know what this edge is but if i ran uh un uh uh an unweighted shortest path algorithm like bfs or dfs on here i would get back a tree right some edge of my graph will not be in my tree something like here right the shortest path to this so i look through i i run b so algorithm idea two two first find s prime okay and i can find s prime by run i don't know a single source shortest path unweighted uh i guess run single source reachability unweighted from s using bfs or dfs to explore a tree of my graph then some edge is not in my tree of the graph that will exist on the cycle kind of by definition right it's cons it's connecting two part parts of my tree now i can look at those two paths from here and the last one that they're in common from s is going to be my split point s prime it's the it's the closest one to my source that is on the cycle right because i constructed this cycle here okay so i can uh find edge u v not in the parent tree right so maybe this is u v right not in the parent tree and then find last common vertex in paths from s to u and s to v okay that's going to give me my s prime okay and i can do that by i mean these are each of linear size and i can just look at their prefix i can start from s i can walk forward until they diverge and the one before they diverge is s prime right that's s prime right here once i have s prime i know what the edges are when they diverge i remove one of those from the graph i do the same algorithm again to find a path to t and i do the same algorithm again to find the path to t and i see which one is shorter that's it there's only two of them and so i check or they could be the same path in which case uh my my t is actually before s prime on on my cycle does that make sense so that's that's the idea uh the last thing is remove an edge from s prime i don't even have to be picky about this it has degree three i can just run single sorted paths on all of them and take them in right uh for eat remove each edge from v at from s prime uh remove let's for each edge from s remove and run ssr from s okay and one of the paths there to t will be shortest my shortest path in the original graph because it can't use uh more than two of those edges that's that's the claim okay and this runs in uh linear time because what i'm doing is i'm running single source reachability once and maybe two more times or three more times a constant number of times on a graph that has size v right and this prefix finding also only takes order v and so we're done okay any questions about this problem no no questions all right we will move on to uh what's up there's a yeah there's a hint in the title actually the original version of this problem said instead of this e equals v specification it said there's only one cycle in the graph but it's in the context of undirected cycles as opposed to directed cycles which is usually what we talk about in this class right we say that there's a negative edge weight cycle in the graph if we can you know it's usually we're talking about we're allowing non-simple cycles in this class so to to you know remember this this uh property about trees and to enforce this property without talking about sicklicity i changed the condition uh for this problem session this review yeah could i also just run depth first search on this graph could you just run depth first search on this graph to do what to find the shortest path right so depth first search on this path if i ran it from s when i got to s prime i would have a choice on what the next outgoing edge to do right so if i ran depth first choice for one of those choices i would find a path to t right and then i would find then then i could run and i would find a path to t right there's only two of them or at most two of them but then there's the possibility i missed this other path that could be shorter well how would i miss it has to go through the other edge too it doesn't go through the other edge that's the point right um it won't go through no so depth first search will actually go through this thing traverse an edge go all the way around the cycle because everything here is reachable from here because it's an undirected graph it will reach back to here and then backtrack all the way so we'll actually never traverse this last edge here of the cycle so it's something you can actually prove with dfs now you could actually while you're running dfs try every possibility right because my branching factors at most three at some of these things right so what i i could do is uh or it could be at most four right i could i could connect two things with the same uh branching but in general it's a constant and and with with every choice dfs could make i could try all possibilities how many possibilities would that be you get a blow up of the degree of every vertex in my graph so the degree time multiplied by each other that's the number of times i would have to run dfs which is exponential right a constant degree so a constant uh [Music] multiplied like like two or three right uh multiplied v times is three to the v which is exponential in the size of my graph uh sure right because i could still have large branching for a large number of vertices okay good great question all right cool so that's that problem problem three i have half an hour for the last two problems i think that should be fine this one's uh okay this is doughnut is the problem name uh momar has just uh finished work at the fing sprilled power plant at a particular location p and needs to drive home to a known location h but along the way if his driving route ever comes within driving distance k of a donut shop he won't be able to resist himself and will have to go there and eat donuts and his wife harge will be angry okay maybe you can get the reference here mohmer knows the layout of finn sprielled which can be modeled as a set of n locations with two-way roads of known driving distance connecting some pairs of them and you may assume that no location is incident to more than five roads okay so we've got a degree bound here as well as the location and and he knows the locations that all the locations that contain doughnut shops there's at most d of them okay describe an n log n time algorithm to find the shortest driving route from the power plant back to home that avoids driving within distance k of a doughnut shop okay so we got a couple variables in here we've got k we've got d but a running time bound only relies on n right okay i see shortest paths i see that uh i don't see an explicit mention of positive distances of the i i see lengths right they say he knows the uh known driving distance connecting some pairs of locations so usually i think if if i were writing this problem now i'd probably be a little bit more explicit the distance is positive but that's you know something that you might come into contact with right distances are positive right and so we can't have negative distances here okay uh so i look at n log n i'm like hey what has a log in it in this unit dykstra maybe i can use dijkstra okay so let's see if if we ran dijkstra from p to h okay so we've got we've got a graph here we've got our graph so i'm this is a word problem so there's no graph there so i have to define a graph okay so i'm going to define a graph v e and we've got v that's going to be my set of locations locations so this has their order n of them there's actually n n of them and then e what are we going to have we're going to have uh it's a known pair of things right road roads with weight equal to driving driving drive driving distance which uh by my assumption is going to be greater than zero right now it's not stated explicitly but you know that would be a reasonable assumption for you to make on your exam because distances are positive we would probably be more explicit about that these days okay all right so this is a graph i could make and i have a vertex s or a vertex p and a vertex h and i'm trying to find a shortest path between them right shortest driving distance driving route right okay so i could run dijkstra wait so what do i know about this how many edges do i have my graph i have at most five per vertex right so this is upper bounded by five times v which is order v okay so i have a order v size graph that's a good thing order n because n is the number of vertices and so if i were to just run dijkstra on here from p doing dijkstra on g from any s takes order n log n right n log n plus n and n log n is bigger than n okay so that's that's a nice observation we may be we have we can at least afford to use dijkstra in this problem to find shortest distances but what's the problem with a shortest distance found by dijkstra in this graph donuts like the entire point of the problem right i need to avoid being too close to donut shops okay so we might have a donut shop here and we need to stay outside of that distance k right or we might have another donut shop here right and so we got to find a path that kind of goes around these donut shops okay so in other words if if i have a vertex in my graph where i can reach a doughnut shot within shop within distance k i got i can never visit that vertex right because then i you know momer will not be able to resist himself and have to go eat a donut okay so that's the thing we're trying to avoid so how can we do this well here's a silly thing i could run dijkstra from each of these vertices these donut shops find all the things reachable in k driving distance from them right and then remove those vertices from the graph that's an idea but how long would that take that would mean need me to run dijkstra d times right because there's d doughnut chops i gotta run dijkstra d times so that gives me a running time bound of i run d times to filter out the graph right to modify this graph and then i do one more to find the shortest path if there is one but in general that's going to take d times n log n not n log n i i have no bound on d except that it's under n right so it could be n and that would give me a bad running time so we're going to use a very similar trick here to one of your i think a previous review session uh stop here we go uh is to when you want to find things if we're on a prunograph from multiple locations one of the things we can do is any tricks super node right i can have a vertex well maybe i don't want to put it up yet okay if i have all of these donut shops what i can do is provide a i guess i guess these are unweighted undirected edges right here we can model all of those directed things by two undirected edges it doesn't really matter but here you know i don't want to go be able to go back to my super node okay but what i'm going to do is i'm going to add a super node with edge weight say 0 to everything else right and then if i ran dykstra from the super node and found all vertices reachable within distance k well i didn't i didn't spend any of that distance going through this first edge right and i didn't come back to s because these things are directed into the things and so anything i reach is going to be within distance k of this donut shop but for all donut shops and in some sense i'm doing this search in parallel so this is the same trick that we had in the like you're looking through the the sewer network or something and they're trying to avoid monitors or uh you know sensors or something like that we actually did this transformation and then binary searched on the distance it was kind of involved but this is an easier example now you can actually generalize this further what if each donut shop had had us uh a like a an amount that moamer liked it right so if uh momar is within a larger distance of a donut shop he really likes he still won't be able to resist right but a donut shop that doesn't make very good donuts you know he'll be able to resist a shorter distance without without having to to uh go to that donut shop so in other words each one of these donut shops has a different k right a different radius that momar will allow is there any way to generalize this technique to be able to prune all of those vertices instead ah all of these had weight zero before the same weight i mean the algorithm would have worked for any weight i put on all of these edges as long as i search the distance that weight plus k right here i can just make the distance of this frontier for each one of the the donut shops the same by modifying the distance to the of the incoming edge right so i can set the length uh the disc the weight from the to the donut shop with the largest radius to zero and then put the difference between the largest radius to all the other ones i put that as the weight on the other edges and then we still have a graph with positive edge weights and i can run dijkstra from this and that would generalize this problem and something that we've done in some practice exams and or in in exams and problem sets in the past okay so that's another common way so we filter filter uh forbidden there's two b's in forbidden or two d's two d's there's a three ds right vertices by using supernode plus one run of dijkstra those are the extra letters okay so on your exam you would probably want to be a little bit more explicit this is this is a summary of the things that we just talked about i just you know talked 10 minutes about the algorithm but it doesn't hurt to add a summary at the top of what you're going to write this is the approach that we're going to have we're going to filter out the vertices from g essentially by running dijkstra from each of these these donut chops but we're going to do it in parallel by adding the super node okay so actually on another uh uh recommendation i have for you on an exam is that almost any problem that we give you in this class can get 80 to 90 of the points by writing like maybe three lines right almost and maybe not some of the data structures problems but almost any question in this class can like uh can be solved with not all of the the points but most of the points by just writing a couple lines that we know that you know how to solve the problem right and this this would be one of those situations right now i would want to give you full points i would want all the details here did i construct a new graph i add this vertex here i have to add edges to each of the d things but i've only added d more edges and one more vertex so it still has this linear size in my input right and then i want to say that i'm you know putting the weights on here based on what the distance is now they're all the same weight because i don't have that generalization and then i run this thing and i remove all those graphs and construct a new graph from g right that's a third graph that i'm constructing now but notice that the graph that was implicit in my problem was very different than the graph that i'm ultimately running a shortest path algorithm like dijkstra from p to c if one a path exists does that make sense any questions on this problem all right we've got 20 minutes for my last problem uh man i'm not using i write much less than some of your other instructors so i like to talk more than i to write apparently okay so problem four let's take a look at this this one's one i made up last night kind of fun long shortest paths okay given a directed graph having arbitrary edge weights basically these could be positive or negative or zero and two vertices from the graph describe a v cubed time algorithm to find the minimum weight of any path from s to t okay that sounds like bellman ford right there but i have this last condition and the last condition is a little weird containing at least the edges so i want a short path in terms of weight but i want a long path in some sense in terms of the number of edges i traverse does