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

438 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 in this video we're going to begin our discussion about why Prim's

Â algorithm is correct. Why always, for every connected graph

Â outputs a minimum spanning tree of that graph.

Â For this video, we're going to content ourselves with a much more modest school.

Â We're only going to prove for now the Prim's algorithm outputs a spanning tree.

Â We're not going to make any claims yet about optimality.

Â Even just this fact is not trivial and proving it will give us a good

Â opportunity to get our hands dirty with some basic properties of graphs and

Â specifically graph cuts. Graduates of part 1 of this online class

Â of course are already familiar with graph cuts. We studied them at length via

Â Karger's randomized algorithm for computing the minimum cut of a graph.

Â So, the concept is the same here, let me state it again to jog your memory.

Â So a cut of a graph is simply a partition of its vertex set, two groups, and each

Â of those two groups should be non-empty. So pictorially, we envision some of the

Â vertices of G, this blob A being in one group,

Â and the rest of the vertices, this graph B being in a different group.

Â Now, what's up with the edges? How can they be distributed in this

Â picture? Well, the two endpoints of an edge,

Â there's three cases, either both of the endpoints can be in

Â the set A. So there's various edges internal to A.

Â Similarly, an edge might have both of its endpoints inside of B.

Â But we're going to be most interested in the third case,

Â edges that have one point exactly in each of A and B.

Â So these are edges that we say cross the cut, A, B.

Â So hopefully the definition of a cut seems simple enough, but cuts in

Â particular their relationship to edges can be quite interesting, quite useful.

Â So as shown here in the picture, of course for a given cut, there can be many

Â edges crossing it. by the same token for a given edge of a

Â graph, in general, there will be many cuts of the grap,

Â that's, that edge crosses. So, to understand this a little bit

Â better, let's just review a simple property that cuts through the graph.

Â Let me just ask you just how many there are.

Â Specifically, for a graph that has n vertices, roughly how many cuts does it

Â have? Roughly n, roughly n squared, roughly

Â 2^n, or roughly n^n? Now, none of these four answers is

Â exactly right, but one of the four is a lot closer to the exact expression than

Â the other three and I'm asking you, which of them is it?

Â Alright. So the correct answer is the third one,

Â 2^n. A graph of n vertices has essentially 2^n

Â cut, so there's an exponential number of cuts there's a lot of them.

Â So why is this true? Well, in effect you can imagine making a

Â binary decision for each of the n vertices.

Â They either go into A. What were they going to be?

Â So n binary decisions results in 2^n different outcomes.

Â Now why is this slightly incorrect? Well, in fact, a cut has to have two

Â non-empty sets. A is not allowed to be empty,

Â B is not allowed to be empty, so that rules out two of the

Â possibilities. So actually, strictly speaking, it's 2^n

Â - 1 different cuts of a graph. So what we're going to do next is we're

Â going to state and prove three easy facts about cuts in graphs.

Â Once we have these three easy facts, we will be able to prove the claim at the

Â beginning of this video, namely the Prim's Algorithm always

Â outputs a spanning tree. The first of these three properties about

Â cuts, I'm going to call the empty cuts lemma.

Â The point of the empty cut lemma is to give us a characterization that is a new

Â way of saying when a graph is connected. So in particular, I'm going to phrase in

Â terms of a graph not connected. And the claim is that a graph is not

Â connected if and only if we can find a cut of the graph that has no edges

Â crossing it. So remember how we defined a graph being

Â connected, that means for any two vertices in the

Â graph we can find a path in the graph from one vertex to the other.

Â So what we're saying is that being not connected,

Â that is, there existing a pair of vertices with no path between them is

Â equivalent to there being a cut with no crossing edges.

Â So let's go ahead and prove this real quick.

Â So as an if and only if statement, really this proof, we have to do in two

Â parts. First, we have to prove that assuming the

Â first statement, we can derive the second.

Â Then we have to show that assuming the second statement, we can derive the

Â first. I think the easier direction is to assume

Â the right-hand side and then derive the left-hand side.

Â So let's start with that one. That is, consider a graph G so that

Â there's a cut, A, B with no edges of G crossing this cut.

Â The plan is to exhibit a pair of vertices that do not have a path between them,

Â there, thereby certifying that the graph is not connected.

Â So, it's pretty easy to figure out which pair of vertices we should look at,

Â just take one vertex from each side of the cut which has no crossing edges.

Â So why is it that there's no path from U to V in the graph G?

Â Well the path from U to V would surely have to cross the cuts, A, B, but there's

Â no edges available for crossing the cut. So therefore, this path from U to V

Â cannot exist. So that completes the first part of the

Â proof. We assume the right-hand side, we derive the left-hand side,

Â now we start all over again, but we assume the left-hand side and we have to

Â prove the right-hand side. So by virtue of, by the assumption that

Â the graph is not connected, there has to exist a pair of verticies U and V that

Â have no path between them. We are now responsible for exhibiting

Â some cut A, B such that no edges of the graph G crossing.

Â So where are we going to get these sets capital A and capital B from?

Â Well, here is the trick, which is going to make the proof go really nicely.

Â We define the set of verticies of capital A to be those reachable from U in the

Â graph G. Another way to think about this is that

Â capital A is simply used connected components in the sense that we discussed

Â in part 1 of the course. Now because we want to cut and a cut is

Â our partition, we better well put in the group, capital B, all of the verticies

Â that are not in A. If you like, this is all of the connected

Â components other than the one that contains U.

Â Note that by definition, U is in capital A,

Â certainly U is reachable from itself. And by assumption, V and U are not

Â reachable from each other, so V is going to be in capital B.

Â So neither of these sets is non-empty. This is indeed a bonafide cut of the

Â graph G. All that remains is to notice that there

Â are no crossing edges across this cut. And why is that true?

Â Well, if there was an edge crossing the cut A, B with one endpoint in A, one

Â endpoint in B. Well, by definition, there are paths from U to everything else in A,

Â so if there is any edge sticking out of A, that would give us a path to some

Â vertex in B. But, B definition of vertices not

Â reachable from capital A, so that's a contradiction.

Â So again, the point is that if there were edges crossing this cut, then we can

Â expand A and make it even bigger. So therefore, there aren't any edges

Â crossing the cut. The cut is empty, that's what we needed

Â to prove. Assuming the graph was disconnected, we

Â have exhibited a cut, A, B with no crossing edges.

Â So that wraps up of the first of our three facts, and in fact, the most

Â difficult of our three facts about cuts in graphs.

Â And again,, what did the empty cut lemma say?

Â It gives us a new way of talking about whether or not a graph is connected.

Â So it's disconnected if and only if there's an empty cut.

Â It's connected if and only if there are no empty cuts.

Â So that's the keypoint from this slide. Let's now knock off the other two facts

Â we're going to need. The first one I'm going to call the

Â double crossing lemma. In essence, what the double crossing

Â lemma says, is that, if a cycle in a graph crosses a cut, then it has to cross

Â it twice, it cannot cross it only once.

Â So pictorially, we look at a cut of a graph, so there's the two vertex groups A

Â and B. By hypothesis, there's some edge E with

Â one endpoint in each side, and by assumption, this E, this edge E,

Â participates in some cycle that we're calling capital C.

Â And if you look at the picture, you realize that the claim in this lemma is

Â obvious, that, because the cycle has to loop back

Â on itself, if it has an edge with one endpoint on either side, there has to be

Â a path connecting the two dots, connecting those two endpoints back to

Â each other and that path has to cross back for, over this cut A,

Â B. Indeed, the double crossing lemma is a

Â special case of a stronger statement which is equally easier to see, which is

Â that if you take any cut of a graph and you take any cycle you know, it starts

Â and ends at the same point, then it has to cross this cut an even

Â number of times. It might cross it 0 times, but it's not

Â going to cross it once. It could cross it twice.

Â It could cross it four times, if it crisscrosses back and forth.

Â It could cross it six times, and so on. But if it crosses it strictly more than 0

Â times, then it has to cross it at least twice.

Â That's the point of the double crossing lemma.

Â So, we'll use this in its own rights later on.

Â But I'm also, for the moment, interested in easy corollary of the double crossing

Â lemma. I will call this the lonely cut

Â corollary. Let me tell you the point of the lonely

Â cut corollary. In general, in these spanning tree

Â algorithms, to ensure that we output a spanning tree,

Â then we have to, in particular, make sure we don't create any cycles.

Â The point of this corollary is it's a tool to argue that we don't create

Â cycles. So how can we be sure that an edge

Â doesn't create cycles? Well, here is a way.

Â Suppose there's a cut, so we're looking at an edge E, suppose we can identify a

Â cut A, B so that edge E is the only cut crossing it, it's the lonely edge

Â crossing this cut. Well then, by the double crossing lemma,

Â there is no way this thing is in any cycle.

Â If it were in a cycle and a cross to cut, that cycle would have to cross it again

Â and it's edge wouldn't be lonely, it would have company.

Â So if you're lonely on a cut, it mean's you cannot be in a cycle.

Â So now we've got all of our ducks lined up in a row and we're ready to prove the

Â first part of the correctness of Prim. That is, we're ready to argue that Prim's

Â algorithm, given a connected graph, outputs a spanning tree.

Â Again, for the moment, we're making no claims about optimality, that will be in

Â the next video. So we're going to make this argument in

Â three steps. And for the first step, you might want to

Â go look again at the pseudocode of Prim's algorithm just to remember what the

Â notation was. The first step, we're just going to

Â notice that the semantics of the algorithm are respected.

Â So the algorithm maintains two different sets throughout its evolution.

Â On the one hand it maintains a set capital x, intended to be the vertices

Â spanned so far. The other hand, it maintains a set of

Â edges, capital T, the edges that have been picked so far.

Â And the intent was that the current edges capital T always spans the current vertex

Â at capital x. So the first thing is just to verify that

Â that is in fact true. This I'm not going to prove formally.

Â In my experience, students find this kind of obvious and the intuition is correct.

Â if you want a rigorous proof, go go ahead and fill in the details yourself.

Â It's a straightforward induction with no nasty surprises.

Â [SOUND] Now, we're trying to argue the output of this algorithm is a spanning

Â tree. So let's recall what that means.

Â What is it that we have to check? So there's two properties.

Â First of all, there can't be any cycles, there can't be any loops.

Â Second of all, it has to span all of the vertices.

Â It has to be a path inside the tree edges from any vertex to any other vertex.

Â So let's go ahead and prove both those things in reverse order.

Â So, the second step of the proof is going to be to argue that the algorithm outputs

Â something which does span all of the vertices.

Â So at the end of the day, we'll have a path from any vertex to any other vertex

Â using only the edges in our chosen set, capital T. Now, by part one of this

Â proof, all we need to prove is that the algorithm halts with capital X equal to

Â capital V, then we know that capital T spans everything in V.

Â So how could that not happen? How could Prim's algorithm somehow halts

Â with this spanned vertices capital X, not being all of capital B,? We'll go back

Â and check out the pseudocode and look at the main wild loop.

Â So every wild loop, every iteration, we add one new vertex to capital X. What

Â could go wrong? The only thing that could go wrong would be is if some iteration,

Â before we're spanning everything, when we scan the frontier around capital X, there

Â aren't any edges. That's the only way we can fail to

Â increase the vertices in capital X in a given duration.

Â But what would that mean? What would it mean if in some iteration

Â we couldn't find edges with one endpoint in capital X and the other endpoint in V

Â - X? Well then we would have exhibited an

Â empty cut. The cut X, V - X would have no crossing

Â edges. And now we can use the empty cut lemma,

Â which says if there's an empty cut, then the graph is disconnected.

Â But by assumption, we're working with a connected input graph, so that can't

Â happen. Okay? So the algorithm never gets stuck,

Â we always increase capital X by one vertex because the original graph was

Â connected, that means that halt was something spanning all of the verticies.

Â For the final step, we need to argue that Prim's algorithm never creates any cycles

Â in the edges that it, it's choosing capital T.

Â So, why are there no cycles? Well, what we're going to do is we're

Â going to talk about each edge in turn, the Prim's algorithm adds,

Â and argue that whenever a new edge gets added, there's no way that edge creates

Â any cycles in the set capital T. And, to see why, take a snapshot of the

Â algorithm of some given iteration, to the sum current set capital T, and

Â there's some set verticies capital X that the edges in T span.

Â V - X to the verticies not yet spanned by T and of course we can think of X, V - X

Â as a cut of the graph. And at this moment in time, at this

Â snapshot, the edges of capital T, they're all of one type.

Â They all have both of their endpoints inside capital X, none of them have any

Â endpoints inside V - X. So in particular, none of the edges

Â chosen thus far cross the cut X, V - X. That's by construction, they only span

Â the verticies of X. Now what type of edge is going to get

Â added in this iteration. Well, Prim's algorithm searches only over

Â edges that have one endpoint inside X and one endpoint outside.

Â That is, it searches only over edges that cross the cut X, V - X.

Â So the edge that gets added in this iteration is going to be a trailblazer

Â for this cut. None of the edges yet shows and cross the

Â cut, but the edge showed in this iteration

Â will definitely, cross the cut. So the moment edge E gets added to the

Â tree capital T, it is going to be lonely across the cut V sorry, X, V - X.

Â So by the lonely cut corollary as the sole member crossing this cut in capital

Â T, it cannot possibly participate in any cycles.

Â Remember, if it participated in a cycle in capital T, that cycle would have to

Â cross this cut somewhere else. But there aren't any other edges crossing

Â this cut, this is the only one. So that's why when we add a new edge,

Â there's no way it can create any cycles. It's the sole member crossing this

Â particular cut.

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