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

439 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 3

Huffman codes; introduction to dynamic programming.

- Tim RoughgardenProfessor

Computer Science

So now that we've done some work with our thought experiment, understanding exactly

Â what the optimal solution, the maximum rate independent set had to look like in

Â the path graph, let's turn that work into a linear time algorithm.

Â Let me quickly remind you, the bottom line from the previous video.

Â So we argued two things. First of all, if the max weight

Â independent set of a path graph happens to exclude the rightmost vertex, then it

Â has to in fact be a max weight independent set with the smaller graph g

Â prime, obtained from g by plucking off the rightmost vertex.

Â If on the other hand a max weight independent set does include the

Â rightmost vertex v sub n, then if you take out v sub n and look at the

Â remaining part of the independent set, that has to be max weight among the

Â smaller graph g double prime, defined by plucking the two rightmost vertices off

Â of the original graph g. Ergo, if we happen to know, if a little

Â birdie told us which of these two cases we were in we could recursively compute

Â the optimal solution of either G prime or G double prime as appropriate and be

Â done. If we recurse on G prime we just return

Â the result. If we recurse on G double prime we

Â augment it by V sub N and return the result.

Â Now, there is no little birdie, we don't know which of the two cases, we're in.

Â So we're concluded the previous video by proposing just trying both case.

Â So let's write down what that proposed algorithm would look like before we take

Â a step back and critique it. So, the good news about this algorithm is

Â it is correct. It's guaranteed to return the maximum

Â weight independence set. So, how would you prove this formally?

Â Well, it would be by induction, in exactly the same way we proceeded with

Â divide and conquer algorithms. And for the same reason, I'm not going to

Â talk about the details here. If you're interested, I'll leave it as an

Â optional exercise to write this out, formally.

Â But intuitively, the inductive hypothesis guarantees correctness of our recursive

Â calls. So computing the maximum weight solution

Â in either G prime or G double prime, and then, in the previous video, the

Â whole point of that, in effect, was arguing the correctness of our inductive

Â step, given the correct solution to the sub-problem, we argued what has to be the

Â optimal way to extend it to a solution, to the original graph, G.

Â The bad news, on the other hand, is that this algorithm takes exponential time.

Â It's essentially no better than brute force search.

Â So while the correctness of this kind of recursive algorithm, follows the template

Â of divide and conquer pretty much exactly.

Â the running time is blown up to exponential.

Â And the reason for that difference is, in our divide an conquer algorithms, think

Â of Merge Sort as a canonical example, we made a ton of progress before we

Â recursed. Right?

Â We threw out half of the array, 50% of the stuff before we bothered with

Â any recursion. How much progress are we making in this

Â algorithm? Well, very little.

Â It's positive progress, but very small. We throw out either one or two vertices

Â out of maybe this graph with say a million vertices before recursing.

Â So we're branching by a factor two and making very little progress before each

Â branch. That's why we give this exponential

Â running time rather than something more in the neighborhood of n log n.

Â So this brings us to the following question.

Â This is an important question. I want you to think about it carefully

Â before you respond. So we have this exponential time

Â algorithm, it makes an exponential number of recursive calls.

Â Each recursive call is handed some graph, for which it's responsible for computing

Â the maximum-weight independence set. The question is this. Over all of these

Â exponentially many different sub-problems, each of which is passed

Â some graph as a sub-problem, how many distinct,

Â How many fundamentally different sub problems are ever considered across these

Â exponentially many recursive calls? So the answer to this question, and the

Â key to unlock the crazy efficiency of our dynamic programming implementation, is B.

Â So despite the fact that there's an exponential number of recursive calls, we

Â only ever solve a linear number of distinct sub-problems.

Â In fact, we can explicitly say what are the different sub-problems it could solve

Â throughout the recursion. What happens before you recurse?

Â Well you pluck vertices from the graph you were given off from the right.

Â Maybe you pluck off one vertex that's in the first recursive call, or in the

Â second recursive call you pluck off two vertices, but both from the right.

Â So an invariant maintains throughout the recursion is that the sub-problem you're

Â handed was obtained by successive plucking off of vertices from the right

Â part of the graph, from the end of the, end of the graph.

Â So, however you got to where you are, whatever the sequence of recursive calls

Â led to where you are now, you are guaranteed to be handed a prefix of the

Â graph. The graph induced by the first I

Â vertices, where I is some number between zero and n.

Â So therefore there's only a linear number of sub-problems you ever have to worry

Â about, the prefixes of the original input graph.

Â From this, we conclude that the exponential running time of the previous

Â algorithm arises solely from the spectacular redundancy of solving exactly

Â the same sub-problem from scratch, over and over and over and over again.

Â So this observation offers up the promise of a linear time implementation of this

Â algorithm. After all, there's no need to solve a

Â sub-problem more than once. Once you've solved it once you know the

Â answer. So an obvious way to speed up this

Â algorithm, to speed it up dramatically is to simply cache the results of a

Â sub-problem the first time you see it. Then you can look it up in some array,

Â constant time, at any point later on in the algorithm.

Â There is a word for this, I won't really use it in this class, but just so you

Â that know what it is, it's called memoization.

Â So in case this is a little vague, what I mean is you would have some array, some

Â global array, indexed one to N or maybe zero to N with the semantics that the Ith

Â entry of this array, is the value of the solution of the Ith sub-problem.

Â Now when you do a recursive call and you're handed the first I vertices of the

Â graph, and again remember that we know that the sub-problem has to look like the

Â first I vertices of the graph for sub I. You check the array, if it's already been

Â filled in, if you already know the answer, great.

Â You just return it and count the time, you don't bother to resolve.

Â If this is the first time you've ever seen.

Â this sub problem then you recurse and you solve it,

Â as as we saw, as we suggested in the previous slot.

Â So with this simple memoization fixed, this action, this algorithm is linear

Â time. The easiest way to see that, and actually

Â in fact a better implementation, is to go away from this recursive top down

Â paradigm, and instead implement the solution in a bottom up way.

Â So solving sub problems in a principled way from the smallest to the original

Â one, the biggest. So a little bit more precisely,

Â let me use the notation G sub I to denote the sub graph of the original graph,

Â consisting of the first I vertices. So we're going to again going to ha-,

Â going to have an array with the same semantics as in the recursive version.

Â The Ith entry denotes the solution to the Ith sub-problem.

Â That is the max rate independent set of G sub I, and the plan is to populate that

Â bottom up, that is from left to right. So we'll handle the edge cases of the

Â first two entries of, of this array specially G sub zero would be the empty

Â graph, so there's no independent set. So lets define the max weight,

Â independent set of the map graph, to be zero.

Â And, if you graph in G one, where the only vertex is v one, the max weight

Â independent set is obviously that one vertex.

Â Remember weights are not negative. So our main four loop just builds up

Â solutions to all of the sub-problems in a systematic way, going from smallest

Â graph, G sub two up to the biggest graph, the original one, G sub n.

Â And when we consider the graph G sub I, how do we figure out what the max weight

Â independence set is of that graph? Well now we use, completely directly, the

Â work that we put in the previous video. The previous video told us what an

Â optimal solution has to look like. And it has to have one of two forms.

Â We know, we proved, either, the maximum independent set of G sub I.

Â Excludes the last vertex V sub I, and then is merely an optimal solution of the

Â graph G sub I minus one. If it's not that, there is nothing else

Â it can be, other than including the last vertex V sub I.

Â And being an optimal max weighted independent set for the graph G sub I

Â minus two. We know its one of those two things.

Â We don't know which. We do brute force search among the two

Â possibilities, and that gives us the optimal solution

Â for the Ith sub problem. Crucially, when we need to do this brute

Â force search for the Ith sub problem, we already know.

Â We've already computed the optimal solutions to the smaller sub problems

Â that are relevant, those can be looked up in constant time, and that's what makes

Â this, each iteration of this four loop run in constant time.

Â So we've done a fair amount of work to get to this point,

Â but, after seeing that the greedy algorithm design paradigm failed us.

Â The divide-and-conquer algorithm design paradigm was inadequate.

Â Brute force search is too slow. With this, as we'll see, dynamic

Â programming algorithm, we now have a one line solution, effectively, to the max

Â weight independent set problem in path graphs.

Â Pretty cool. What's the run time?

Â Well this is probably the easiest algorithm is run time we've ever had to

Â analyze. Obviously, it's linear time,

Â constant time per each iteration of the four loop.

Â Why is the algorithm correct? Well it's as same as our recursive

Â algorithm. It makes exactly the same decisions.

Â The only difference is it doesn't bother with the spectacular redundancy of

Â resolving sub-problems it's already solved.

Â Again if you wanted to prove it by scratch, it would just be a straight

Â forward induction, like in our divide and conquer algorithm, the recursive calls

Â are correct by the inductive hypothesis. The inductive step is justified by the

Â case analysis of the of the previous video.

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