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

So the third and final issue to think through is we need to make sure that we

Â pay the piper, that we keep these N variance maintained.

Â We know that if they're satisfied than we have this great way of finding the best

Â edge in each iteration, we just do an extractment But how do we make sure that

Â these N variance stay maintained throughout the algorithm?

Â So, to get a feel for the issues that arise in maintaining of the invariants,

Â in specific, invariant number two, and also to make sure we're all on the same

Â page with respect to the definition of key value of the vertices in the heap.

Â Let's go through an example. So in this example, I've drawn in the

Â picture a graph that has six vertices. in effect we've already run three

Â iterations of Prim's Algorithm, so four of the six vertices are already in

Â capital X, the remaining two vertices V and W are not yet an X, they're in V

Â minus X. So, for five of the edges, I've given

Â them a cost labeled in blue. For the other edges,

Â it's not relevant for this question what their edge costs are.

Â So you don't have to worry about it. So, the question is the following.

Â So given our semantics of how we define keys for vertices that are not in X, so

Â in this case the vertices V and W. What are their current key values

Â supposed to be? So those are the first two numbers I want

Â you to tell me. What's the current key value of V and W?

Â And then secondly, after we run one more iteration of Prim's algorithm.

Â Then what is the new key value of the vertex W supposed to be?

Â So the correct answer is the fourth one. Let's see why,

Â so first let's remember the semantics of keys.

Â What's the key supposed to be? It's supposed to be amongst, all the

Â edges. That on the one hand, are incidents to

Â the vertex. And on the other hand, are crossing the

Â cuts. It's the cheapest cost of any of those

Â edges. So, for the node V, there's four incident

Â edges with costs one, two, four, and five.

Â The one is not crossing the cut, the two, four, and five are crossing the cut.

Â The cheapest of those is two. So, that's why V's current key value is

Â two. For the node V, the node W, it has two

Â incident edges, a one and a ten. .

Â The one is not crossing the cut. The ten is.

Â It's the only candidate crossing the cut, so its key value is ten.

Â So the third part of the question says, what about when we execute one more

Â iteration of Prim's algorithm? So, what is Prim's algorithm going to do?

Â Well, it's going to move the edge with the smallest key from the right hand side

Â to the left hand side. V has a key value of two, w has a key

Â value of ten, so, V is going to be the one that gets moved from the right hand

Â side to the left hand side. So, once that happens, we now have a new

Â set capital X with a fifth vertex, V is now a member, so the new value of X is

Â everything except for the vertex W Now, the key point is that, as we've changed

Â the set capital X, the frontier has changed.

Â The current cut has changed. So of course, it's a different set of

Â edges that are crossing this new cut. Some have disappeared, and some are newly

Â crossing it. The ones that have disappeared are the

Â two and the four and the five. Anything between the vertex that got

Â moved that was already spanning, going to the left hand side has now been sucked

Â inside of capital X. On the other hand, the edge VW which was

Â previously buried internal to V minus X, with one of it's endpoints being pulled

Â to the left hand side. It is now crossing the cut.

Â So why do we care well the point is W's T value has now changed it use to have only

Â one incident edge crossing the cut the other across ten now with a new cut it

Â has two incident edges both the one and the ten are crossing the cut.

Â The cheapest of those two edges is of course the edges of cost one and that now

Â determines its key value its dropped from ten to one.

Â So the take away from this quiz is that well, on the one hand, having our heap

Â set up to maintain these two invariants is great, because a simple extract min

Â allows us to implement the previous brute force search in Prim's algorithm.

Â On the other hand, the extractions screws things up.

Â So it messes up the semantics of our key values.

Â We may, may need to recompute keys for the vertices.

Â So in this next slide I'm going to show you the piece of pseudocode you'd use to

Â recompute keys in the light of an evolving frontier.

Â Fortunately, restoring in varient number two after an extract min is not so

Â painful the reason being is that the damages done by an extract min are local.

Â More specifically, let's think about what are the edges that might be crossing the

Â cut now that were not previously crossing the cut?

Â Well the only vertex whose membership in these sets has changed is V so they have

Â to be edges that are incident to V. If the other end point was already in X

Â then we don't care this edge has just been sucked into X, we never have to

Â worry about it. But if the other end points, so if this

Â edge is incident to v if the other end point w is not an x.

Â Then with V being pulled over the, the left hand side.

Â Now this edge spans the frontier when previously it did not.

Â So the edges we care about are incident to V with the other N point outside of X.

Â And so our plan is just the obvious one, which is for each dangerous vertex.

Â Each vertex incident to V where the other endpoint W is not an X.

Â We just follow to the other endpoint W, and we just recompute its key, and we

Â just do that for all of the relevant W's. So that recomputation necessary is not

Â difficult, there's basically two cases. So this other end point W now it has one

Â extra candidate edge crossing the cut. Namely the one that's also incident on V.

Â The vertex that just moved. So I did this new edge VW is the cheapest

Â local candidate for W, or it's not. And we just take the smaller of those two

Â options. So that completes the high level

Â description of how you maintain invariants one and two throughout this

Â heap-based implementation of Prim's algorithms.

Â So each iteration, you do an extract min, from the extract min you run the

Â pseudocode to restore invariant number two, and you're good to go for the next

Â iteration. So for those of you who want not just the

Â conceptual understanding of this implementation, but really want to get

Â down to the any degree. You want to dot all the I's and cross all the T's. A

Â subtle point you might want to think through is how it is you implement this

Â deletion from a heap. The issue is, is deletion from a heap is

Â generally from a given position. And so here I'm only talking about

Â deleting a vertex from a heap, that doesn't quite tight check.

Â Really what you want to see is delete the vertex at position I from a heap.

Â So really pulling this off, the natural way to do it is have some

Â additional bookkeeping to remember which vertex is at which position in the heap.

Â So again, for the detail-oriented amongst you that's something to think through,

Â but this is the complete conceptual description of the algorithm.

Â Let's now move on to the final running time analysis.

Â So the first claim is that, the non-trivial work of this algorithm all

Â takes place via heap operations. That is, it suffices to just count the

Â number of heap operations, each of which we know is done in logarithmic time.

Â Okay, so let's count up all of the heap

Â operations. One thing we already talked about,

Â but I'll mention it here again for completeness is we do a bunch of inserts

Â just to initialize the heap in a pre-processing step.

Â So after we initialize, we move on to the main while loop.

Â Remember, there's exactly N minus one iterations of that while loop.

Â And in each one, we extract min exactly once.

Â So these were the easy steps. What you should be concerned about.

Â Are, the, heap operations, the deletions and re-insertions that are triggered by

Â needing to decrease the key avertices that are not in X.

Â Indeed, in a single iteration of Prim's algorithm, in a single move of a vertex

Â inside of capital X, can necessitate a large number of heap operations.

Â So, it's important to think, to count these operations in the right way, namely

Â in a edge-centric manner and the claim is that a single edge of the graph is only

Â going to trigger a single decrease key pair of.

Â Operations a single insertion deletion combo.

Â We can even pinpoint the moment in time at which we're going to have this inser,

Â this deletion and reinsertion. It's going to be when the first of the

Â endpoints, so either V or W, the first iteration at which one of those gets

Â sucked into the left-hand side capital X, that's going to trigger the

Â insert-delete, potentially for the other endpoint.

Â When the second endpoint gets sucked into the left-hand side, you don't care,

Â because the other endpoint has already been taken out of the heap,

Â there's no need to maintain its key. So that means that the number of heap

Â operations is almost twice the number of vertices plus almost twice the number of

Â edges. We're again going to use this fact that

Â the input graph is connected and therefore the number of edges is

Â asymptotically at least the number of vertices.

Â So we can say that the number of heap operations is at most a constant factor

Â times the number of edges, M. As we've discussed every heap operation

Â runs in time logarithmic in the number of objects in the heap so that's going to be

Â Log N in this case so we get an overall running time of O of M times Log N.

Â So this is now a quite impressive running time for the really quite non-trivial

Â minimum cost spanning tree problem. Of course we'd love to do even better.

Â If we could shave off the Log N factor and be linear in the input, that would be

Â even more awesome. But we gotta feel pretty good about this

Â running time. Right?

Â This is only a Log N factor slower than what it takes to read the input.

Â This is the same kind of running time we're getting for sorting.

Â So this actually puts the minimum spanning tree problem into the class of

Â four free primitives. If you have a graph and it fits in the

Â main memory of your computer, this algorithm is so fast.

Â Maybe you don't even know why you care about the minimum spinning shaver graph.

Â Why not do it? It's basically cost-less.

Â That's how fast this algorithm is.

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