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

351 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

Alright. So now that we've completed our warm up

by showing that at the very least, Prim's algorithm outputs a spanning tree. Let's

move on and actually show it outputs a minimum cost spanning tree.

And to prove this theorem, we're going to have to tackle head-on the kind of crisis

which you always face when designing a greedy algorithm.

So in a greedy algorithm, you're making an irrevocable decision,

like in Prim's algorithm, we're including an edge in our tree and never revisiting

it later. And, how can you be sure that you're not

making a mistake? How can you have a guarantee that the

decision you're making seemingly myopically right now is actually a good

decision won't come back to bite you later?

So it turns out for minimum spanning trees, there is a beautiful condition

which tells you when you're guaranteed to not regret including an edge into a

spanning tree, but guarantees when an edge has to belong

to the minimum spanning tree. So that's called the cut property,

it's the subject of the next slide. So this is a cool enough property that

we're going to bestow it not just with all caps but even with a box.

Now, that's a pretty good property. So what does it states?

Well, consider an edge of a graph, an edge that we are wondering if it's safe

to include it in the tree so far. So here is this sufficient condition

guaranteeing that you won't regret including this edge in the tree so far.

The condition is stated in terms of the cut.

So suppose you can find a cut, A, B with the property that amongst all edges in

the graph G, that happened across this cut, the edge E is the cheapest edge

crossing this cut. Okay? So not only should edge E cross

this cut, A, B, but it should cheapest such edge.

If this condition is met, then we definitely want them include the edge E

in our solution. Indeed, the edge E has to be a member of

any minimum spanning tree of the graph. So in this video, we're going to assume

that the cut property is true. It is by no means obvious.

It definitely requires a proof. I'll give you the proof in a separate

video. It's not,

it's a little bit tricky. It's based on a subtle exchange argument.

For this video, we're going to assume that it's true, however, and we just want

to be quiet, so that we want to figure out what it's good for.

Now, I will soon show you that it actually implies correctness of Prim's

algorithm. But just to get a feel for it, let's look

at a much simpler graph. Let's just look at a four cycle.

Four nodes, four edges with edge costs 1, 2, 3, and 4.

So let's look at, let's look at a few cuts.

So, let's look at the cut. We're on one side of the cut,

I put the upper right vertex, and on the other side of the cut, I put

the other three vertices. So there are two edges crossing this cut,

the edge that has cost 1, the edge that has cost 2.

So the edge with cost 1 is the cheapest edge crossing this cut, so by the cut

property, the edge of cost 1 has to be in the MST.

Okay. So we looked at one cut and both the cut

property [INAUDIBLE} to stick in the MST. That was pretty cool.

let's look another cut. Let's look at a cut where on one side, we

just put the bottom right vertex, and on the other side, we put all Now

this cut has two edges crossing it the edges that have cost 2 and cost 3.

The edge of cost 2 is the cheapest edge crossing this cut.

So by the cut property, it has to be in the MST.

So that's cool. So we know the two has got to be there.

Now let me point out something interesting that's happened,

which is that, it is not the case that this edge of cost 2 is the cheapest

crossing, every single cut that it crosses. Remember when we looked at cut

number 1, this edge of cost 2 was actually the most expensive edge crossing

that cut. But, we found a different cut that is the cheapest crossing and that's

enough to justify the cut property. So in other words,

all that's important for the cut property,

I just got to find you one cut for which an edge is the cheapest, that's enough to

conclude its presence in the MST. So similarly, we can look at a third cut

just consisting of the bottom left vertext and the other three vertices.

And it's the same story, there are two edges crossing this cut, the edge of cost

3, the edge of cost 4. The edge of cost 3 is the cheapest edge

crossing this cut, so we know it's got to be in the MST.

And again, when we look at cut number 2, it didn't tell us whether or not the edge

of cost 3 is in the MST, but when we looked at cut number 3, that was enough

to conclude that the edge of cost 3 has to be in the MST. So there we go.

So we could use the cut property that construct an entire MST.

On the other hand, there's no way to use the cut property to try to justify the

edge of cost 4. Any cut that you pick for which the edge

of cost 4 crosses, there will be some other cheaper edge crossing it.

So you can never use the cut property as one would hope to justify the inclusion

of the edge of cost 4 and you'd better not be able to, because 4 is not in the

MST. Now a quick side note, some of you might

be wondering when I wrote in the conclusion of the cut property,

I said the MST of G, so that would seem to indicate that the minimum spanning

tree is unique. So that deserves a quick comment.

so first of all, if the edge costs are not distinct, if you have ties between

edges, then you can certainly have multiple different minimum spanning trees

and you have to state the cut property a little bit differently.

But again, in the lectures we are just going to assume distinct edge costs, so

that's not a problem. And in fact, something that will be a

consequence of the next slide, we'll notice that the minimum spanning tree is

unique with distinct edge cost. It's not obvious, but we'll prove it

shortly. All right.

So what I want to do to finish up this video is I want to assume that the cut

property is true. And then, from that, I want to derive, I

want to argue that Prim's algorithm is correct,

always outputs an MST. The proof of the cut property is

non-trivial and deserves its own video, which you can see separately.

All right. So given the tools that we've developed, this argument is actually

going to be quite short. So let's assume that the cut property is a true statement

and let's begin by building on the previous video.

The previous video argued that Prim's algorithm outputs a spanning tree, didn't

argue it was a minimum one, but it argued it's a spanning tree, it spans all the

vertices and has no cycles. Let's call the output of Prim's algorithm

at the end of algorithm T star. Now,

stare at the cut property, stare at the pseudocode of Prim's

algorithm. What happens in each iteration of Prim's

algorithm? Well, we have our set capital X, that's

what we spanned so far. There's the rest of this stuff, V - X, so

that's a cut X, V - X. What does Prim choose to include next?

Well, in brute-force searches through the edges, the cross is cut and it adds the

cheapest one of them. Well, that is right in the wheelhouse of

the cut property. What does the cut property says? It says

cheapest edges crossing cuts have to be in the MST.

So they just fit together beautifully. Prim's algorithm explicitly picks an edge

at each iteration which satisfies the hypothesis of the cut property and

therefore has to be in the MST. So remember, the conclusion of the cut

property says edges so justified must belong to the MST. So if everything in T

star is justified by the cut property, then everything in T star is in the MST

so T star is a subset of the MST. But T star, of course, as we have argued,

is already a spanning tree in it of itself.

And, if you add more edges to T star, it's no longer going to be a spanning

tree, because you are going to pick up cycles, right? If you ever have something

that is connected, there is a path from each pair of vertices, and you add a new

edge, you are going to close a path, you're going to get a loop.

Okay? So T star is already a spanning tree, and

you can't have anything bigger and still be a spanning tree.

So therefore, this has to be the minimum spanning tree,

there cannot be anything else. So for this reason, T star must in fact

be the minimum cost spanning tree of the graph.

Since the input graph was arbitrary, assuming only it was connected, this

completes, assuming the cut property, the proof of correctness of Prim's minimum

spanning tree algortihm.

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