The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

354 ratings

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 1

Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim's MST algorithm.

- Tim RoughgardenProfessor

Computer Science

Okay. So to this point we've proven the correctness of Prim's minimum spanning

Â sheet algorithm under an assumption, under an assumption that the cut property

Â is true. So, the purpose of this video was to

Â supply the missing proof to convince you of this cut property.

Â Let me remind you where we stand. So through all the minimum spanning tree

Â videos, we're assuming distinct edge costs.

Â All of this can be extended to edge costs with ties.

Â In particular, there's a version of the cut property when the edges have ties,

Â but we're just going to focus on the main ideas which were exposed already with

Â distinct edge costs. So what does the cut property say?

Â Well, it's meant to be a guarantee that an edge is safe to include on, in your

Â tree so far. So it justifies an iteration of a greedy

Â algorithm like Prim's algorithm. Specifically, consider an edge of a

Â graph, and suppose you can find some cut A, B.

Â So that, amongst all the edges that are crossing this cut, E is the cheapest.

Â So E, the edge E has to not just cross this cut,

Â but it has to be cheaper than any edge that crosses this cut.

Â If you can find just one cut of this form, so that E is the cheapest crossing

Â edge, then it's definitely not a mistake to

Â include E in your tree. You definitely want it.

Â It is in the MST. So this is a non-trivial claim and, let's

Â turn to the proof. At a high level, the plan will be not

Â that different than the correctness of our greedy scheduling algorithm for

Â minimizing the weighted sum of the completion times.

Â That is, we're going to use an exchange argument embedded in a proof by

Â contradiction. [COUGH] The type of contradiction will be

Â of the same form. We'll start with an optimal solution.

Â Suppose it doesn't have the property that we want it to have,

Â and then we do an exchange to make it even better, contradicting the assumption

Â that this solution is optimal. So specifically, if we argue by

Â contradiction we assume, that the cup property is false.

Â So let's just make sure we understand what that means.

Â If the cup property is false, then there's a graph and there's an edge,

Â which actually is the cheapest crossing some cut, and yet, that edge does not

Â belong to the minimum cost spanning tree T star.

Â The plan then is to exchange this missing edge E with some edge that isn't a tree T

Â star, which is more expensive, thereby getting a better spanning tree providing

Â the contradiction. So, this idea currently is a little bit

Â hand-wavy. To really execute it, we have to specify

Â which edge we're going to exchange the edge E with.

Â That's a subtle point and we'll develop it over the next couple of slides.

Â So let's begin with a sort of first cut attempt at an exchange argument.

Â So what's the world look like? Well, we have some cut of a graph.

Â So at one blob, the vertices is A and then the rest of the vertices are in this

Â blob B. this is the cut for which edge E is the

Â cheapest. And by our assumption in this proof by

Â contradiction, this cheapest edge E does not belong to the minimum spanning tree T

Â star. That said,

Â I claim while T star may not have this edge E to cross in this cut, it better

Â possess some other edge crossing this cut A, D.

Â So why is that true? Well, suppose the opposite, suppose in

Â fact T star did not have any edge crossing this cut A,

Â B, well then, T star wouldn't be connected. It wouldn't span all the

Â vertices, right?

Â Remember our proof of empty cut lemma, so if you had this empty cut and there's no

Â way to have a path from one side to the other side.

Â Okay? But that's spanning trees have to have

Â paths between each pair of vertices. So T star as a spanning tree have to

Â contain something from this cut, by assumption it doesn't contain edge E. So

Â it contains some other edge, let's call it F, that crosses this cut.

Â Now of course, since E is the cheapest edge crossing this cut and F is some

Â other edge crossing this cut, F is strictly more expensive than E.

Â And at this point, we seem beautifully set up to execute the desired exchange

Â arguement. We have the edge that the optimal solutions missing. We have a

Â canvid replacement edge F, which is more expensive.

Â So if we swap E and F, hopefully we get a new spanning tree that has strictly

Â smaller cost providing the desired contradiction.

Â But, things are more settled than they were with these scheduling applications.

Â The reason being is that schedules are simply sequences of jobs.

Â So whenever you do an exchange of two jobs, it's clear you get another

Â schedule. But spanning trees and graphs are subtle

Â objects and there's a question, if we take a spanning tree and we add one new

Â edge and delete an edge, do we get another spanning tree of the

Â graph or not? So the following quiz is going to ask you

Â to think about that question carefully. Okay. So what we wish that the answer to

Â this quiz was, was either answer A or answer C.

Â So A would be the cleanest solution. If it were always true that when you take

Â a spanning tree, you take an edge outside of the spanning tree and then you swap

Â those two edges, you get a new spanning tree,

Â then in fact, our proof of the cut property would be done, right?

Â We would just go on that previous slide. We would rip out the edge F from the

Â spanning tree. We'd plug in the edge E,

Â because E costs less than F, we'd get a spanning tree which was

Â cheaper. And we'd be done,

Â that would be our contradiction. Now if A wasn't true, we'd still be okay

Â if C was true. If maybe not every swap yields a new

Â spanning tree, but at least if you're swapping in the

Â edge that's the cheapest crossing some cut,

Â you get a spanning tree. Then we'd also be golden, because in

Â fact, we're only are trying to execute the swap,

Â the exchange, using an edge, which is the cheapest crossing some cut.

Â If you go back to the previous slide, you'll see that was the only case we

Â needed this fact to be true. Unfortunately, the correct answer to this

Â quiz is D. You need not get a new spanning tree when

Â you execute an exchange, even if you're plugging an edge which is the cheapest

Â edge crossing some cut. So to understand this better, let me the

Â picture that we had on the previous slide.

Â We had our cut A, B, we had our cheapest edge E which by assumption does not

Â belong to the spanning three T star, but we observed that T star has to contain at

Â least one other edge crossing this cut because it's connected and we called that

Â F. And we're wondering if swapping E and F

Â yields a new spanning tree or not. So, to reason about this, let me just

Â draw you what the rest of the spanning tree might look like.

Â So in this picture, this spanning tree T star is given by the pink edges.

Â And it's just to this path of five edges on the six vertices.

Â So, what happens if we exchange E and F? Well unfortunately, something bad

Â happens. So we certainly get a new subgraph of

Â five edges, after all, we just subtracted one and

Â added one. But this new spanning, this new subgraph

Â fails to be a spanning tree. It fails on both counts.

Â First of all, it obviously has a cycle and it's a four cycle and secondly, it's

Â not connected. The upper right vertex is just totally

Â disconnected from the rest of the rest of the vertices.

Â So that's no good. That's an exchange which just does not

Â produce a feasible solution and it is therefore not useful in our proof by

Â contradiction. Now, if you just want to salvage some

Â hope from this seemingly promising proof plan, we could take solace from the fact

Â that there is not just one pink edge crossing the cut A, B.

Â F isn't the only one, there's actually this other one on the bottom.

Â so let me call that E prime. Now, E being the cheapest edge crossing

Â this cut overall. Not only is E cheaper than F, it's

Â cheaper than E prime also. So in some sense with our motivation, we

Â could care less which edge we exchange E from crossing this cut, because it's

Â cheaper than all of them. And we see that at least in this example,

Â swapping with E prime yields a good solution, yields a feasible spanning

Â tree. So what have we learned?

Â What we've learned is that if we want to execute this exchange argument, we cannot

Â blithely exchange with any edge of T star that crosses this cut.

Â So the best case scenario, so what we're hoping is true that we can always find

Â some suitable edge, like E prime on the previous slide.

Â So that when we execute this swap, we do in fact, get a spanning tree.

Â And I'm happy to report that we can indeed always do this.

Â So what I need to explain is the procedure by which we exhibit edge, this

Â edge E Prime, which doesn't get us into trouble after we swap, which still gives

Â us a spanning tree after the swap. So let me explain the procedure by which

Â we identify this magical edge E prime that we can swap with and still be a

Â spanning tree. So here's the way to think about it, so

Â we've got this spanning tree T star, we've got this edge which is not yet in T

Â star. Now, if we just plug E into T star, we're

Â going to get a cycle. Why?

Â Well, a spanning tree, remember, it has a path between each pair of vertices. So if

Â this new edge, maybe its endpoints are U and V. T star already has a path between

Â U and V, so when you plug in this new direct edge between U and V, it closes

Â the loop, it gives you a cycle. So let's go ahead and call that cycle

Â capital C. Let me also redraw the picture from the

Â example on the previous slide so you can see what that cycle was in that special

Â case. Now, here's the pattern to notice about

Â this cycle capital C, at least in this example, which is that the lousy edge,

Â the edge F, for which when we swapped, we didn't get a spanning tree, that's off of

Â this capital C. Whereas, the good edge, the edge where we could do a swap and get

Â a spanning tree, E prime that's on this same cycle capital C.

Â And that turns out to be true in general. So, when you add the edge to the spanning

Â tree and you get a new cycle, that cycle is what furnishes the candidates for

Â swaps that will give you a new spanning tree.

Â So the one lingering concern then, we have this cycle.

Â We would, all edges of the cycle are going to be good candidates for the

Â swapping. Wee just need to make sure that there is some edge that actually crosses

Â this cut A, B like the edge E prime does in the picture.

Â But here, we're going to rely on a fact from a previous video, the double

Â crossing lemma. Remember the double crossing lemma says,

Â that if you have a cycle that crosses a cut at least once, then it has to cross

Â it twice. All right.

Â So if it'd cross once, then it has to loop back around, then in looping back

Â around, it's going to cross it a second time.

Â So, in this cycle capital C, we know it crosses the cut A, B once,

Â that's because it includes the original cheapest edge across the cut E.

Â So, it's got to cross it a second time. There's got to be an E prime in the cycle

Â crossing the cut and that's going to allow us to do the swap and get a new,

Â cheaper spanning tree completing the contradiction.

Â So, just to spell things out in a little more detail.

Â So what we do is we first say we use the double crossing lemma.

Â So, we have this reported minimum spanning tree T star.

Â We have this cheap edge E knot in it. We plug E into the spanning tree, we get

Â cycle, we call the cycle capital C. The cycle crosses the cut A, B once,

Â through the edge E. It crosses it a second time by the double

Â crossing lemma. We're going to call that edge E prime.

Â Since E prime crosses the same cut as E, we know that E prime is strictly more

Â expensive than E. Remember we use the cheapest one crossing

Â this cut, A, B.

Â So now what we do is we execute the swap with this new edge E prime.

Â So E prime in T star. The cheapest edge, E, is not in T star so

Â we can swap them. We can take,

Â we can rip E prime out, we can stick E in.

Â Now something I want you to think through carefully at home, convince yourself this

Â is true, is that because we plucked E prime from the cycle, this new tree which

Â I'm going to call capital T, this is a spanning tree necessarily.

Â You know, intuitively, the reason being, you plug in E and you get this one cycle

Â involving E, and then when you rip out E prime, you destroy the cycle.

Â And because it's on a cycle, you don't destroy connectivity between any pair of

Â veriticies, there is still one path between each pair.

Â But make sure you believe that, convince yourself at home.

Â And once you're so convinced, you will also realize that we've finished a proof.

Â We've executed our proof by contradiction.

Â since E was the cheapest edge crossing the cut, and E prime is another edge

Â crossing the cut, E is got to be cheaper.

Â Since T differs from T star only in the swap of these two edges,

Â it's aggregated cost has gone down and that contradicts the purported optimality

Â of T star comp completing the proof of the cut property.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.