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

291 ratings

Stanford University

291 ratings

Course 3 of 4 in the Specialization Algorithms

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 we now have an algorithm, a very elegant one, that solves the weighted

Â independent set problem in path graphs. Moreover the algorithm runs in linear O

Â of n time, clearly the best possible. But before we do a victory lap I want to

Â point out that there's something this algorithm doesn't do that you might want

Â it to do, mainly hand you the actual optimal solution, not merely the value of

Â that optimal solution. So the point of this video is to show you

Â how we can reconstruct an optimal solution given the table-filling

Â algorithm from the previous video. So we just write that algorithm back

Â down. It's so short, it won't take me too long.

Â Now when this algorithm completes, what do we have in our hands?

Â We have an array, and this array is filled with numbers.

Â In particular, in the last entry in the array is a number like 184 so that's

Â great. That tells us that the maximum weight

Â that any independence set possesses is 184.

Â But, in many applications, we're going to want to know not just that information

Â but actually which vertices constitute that independence set with total weight

Â of 184. So, perhaps the first hack that comes to

Â mind to address this issue is to augment the array, so that each entry stores not

Â just the value of an optimal solution to the sub-problem produced by the graph G

Â sub I, but also an actual set of vertices achieving that value.

Â And I will leave it for you to if you want, rework the previous pseudo codes so

Â that when you fill in a new entry, you fill in not just the value of an optimal

Â solution given solution to the previous sub-problems but infact also the solution

Â itself. This hack however is not generally how

Â things are done in dynamic programming. It unnecessarily wastes both time and

Â space and a much smarter approach is to reconstruct from the filled in table an

Â optimal solution as needed. So if you think about it, it's kind of

Â cool that this is even possible, that our one line algorithm doesn't cover its

Â tracks, that it leaves enough clues for us as detectives to go back and examine

Â and reconstruct what the optimal solution is.

Â The following key point articulates exactly why this is indeed possible.

Â So the starting point of this observation is the correctness of our algorithm, our

Â one line algorithm. Which of course we established in the

Â previous video. And by correctness I mean what's

Â guaranteed that this algorithm will populate each entry of your array

Â correctly. The number in the ith entry is indeed the

Â maximum weight of independent set in the graph G I.

Â So remember our thought experiment about what the optimal solution could possibly

Â look like. We concluded it could only be one of two

Â things, and we really wound up wishing we had a little birdie that could tell us

Â whether or not the rightmost vertex v.sub.n was in the optimal solution or

Â not. If we knew which case we were in we could

Â just recursively compute the remainder of the solution from a graph that has either

Â one or two fewer vertices. So here's the point,

Â this filled in table, that's our little birdy.

Â Here's what I mean. But what, what's, what's the reasoning

Â that our algorithm goes through to fill in this last entry of this array, and

Â don't forget, we've already proven that our algorithm's correct, we did that in

Â the last video? Well, it does a comparison between the

Â two possible candidates vying for the optimal one.

Â On the one hand it commutes the case one solution that looks up the optimal value

Â of a solution for the graph with one fewer vertex and it compares that to the

Â case two solution including V N the last vertex and adding that to an optimal

Â solution with two fewer vertices. And in this max operator in the line of

Â code it's explicitly comparing which is better, case one.

Â The solution which excludes B sub N, or case two, the solution which includes B

Â sub N. So, whichever one of those was the

Â winner, whichever one of those cases was used to fill in that last entry.

Â That exactly tells us whether or not B sub N is in the optimal solution.

Â If we use the first case, that means B sub N is not in the optimal solution, it

Â gets excluded. If the second case was the winner, then

Â we know B sub N is in the optimal solution, because that was the winner.

Â If we have a tie, then there's an optimal solution either way.

Â There's one that includes BN and there's one that excludes BN,

Â So those are the tracks in the mud left for us by the forward direction of the

Â for-loop. We can just go back and look at which

Â case was used to fill in each entry of the array.

Â Again, for the ones that used case one, that corresponds to excluding the current

Â vertex; for those that used case two to fill in the entry, that corresponds to

Â including that vertex, in the solution. So the reconnect structure algorithm will

Â take as input the filled in array that was generated by our one line algorithm

Â on the previous slide. And what it's going to do, it's going to

Â trace through this array from right to left.

Â And at each step of the main loop, it's going to say, it's going to look at the

Â current entry. And it's just going to compute explicitly

Â which of the two candidates were used to fill in this array entry.

Â If you want, you can also cache the results of these comparisions on the

Â forward pass. That's an optimization that will be

Â useful later for harder problems. But for now if you want, you can just

Â think about redoing the comparision thing.

Â Hey, you know, their were two possible. More ways that we could have filled in

Â this entry, let's just check which of the two were used.

Â So if in fact the preceding array entry is at least as large as the one from two

Â back plus the weight of the current vertex, that corresponds to case one

Â winning, to the sub-solution that excludes the current vertex being better

Â than the one that includes it. So in that case we just skip the current

Â vertex V sub I and we decrease the array index by one in our scan.

Â If the other case wins, that is, if we fill in the current entry, if an optimal

Â solution to the current graph G sub I comprises the current vertex of E sub I

Â plus the optimal solution to the graph with two fewer vertices.

Â In this case we know we'd better include V sub I.

Â That's part of an optimal solution to the current sub-problem.

Â Moreover, that's the case where we need to look up the optimal solution with two

Â fewer vertices. So, we include the current vertex and we

Â decrease the array and index by two. So formally we have a correctness claim

Â which is that the final output S return by the reconstructing algorithm is, as

Â desired, a maximum weight independent set of the original graph g.

Â We've already talked about all the ingredients necessary for a formal proof,

Â for those of you who are interested. Of course, it precedes by induction and,

Â in the inductive step, you use the same case analysis we've been using over and

Â over again. The optimal solution at any given point,

Â it has only two possible candidates. The algorithm explicitly figures out

Â which of the two it is and that is what. Triggers whether or not to include or

Â exclude the current vertex. The running time, it's even easier.

Â We have a wild loop that runs in most an iterations.

Â We do constant work in each of the iterations.

Â So just like the forward pass, this backwards pass is really just a single

Â scan through the away. It's going to be lightning fast linear

Â time.

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