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

248 ratings

Stanford University

248 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 4

Advanced dynamic programming: the knapsack problem, sequence alignment, and optimal binary search trees.

- Tim RoughgardenProfessor

Computer Science

So now that we understand the structure of optimal solutions for this optimal binary search tree problem. That is, we understand how an optimal solution must be one of a relatively small number of candidates. Let's compile that understanding into a polynomial time dynamic programming algorithm.

Let me quickly remind you of the Optimal Substructure Lemma that we proved in the previous video. Suppose we have an optimal binary search tree for a given set of keys, one through N, with given probabilities. And suppose this binary search tree has the root R. Well then it has two sub-trees, t1 and t2. By the search tree property, we know exactly the population of each of those two sub-trees. T1 has to contain the keys one through r - 1. As usual we're sorted, we're assuming these are in sorted order. Whereas the right sub-tree t2, has to contain exactly the keys r + 1 through n. Moreover, t1 and t2 are, in their own right, valid search trees for these two sets of keys. And finally, and this is what we proved in the last video they're optimal for their respective sub-problems. T1 is optimal for keys one through r minus one and the corresponding weights or. Abilities and T2 is optimal for R plus one through N and their corresponding frequencies. So let's now execute our dynamic programming recipe. So now that we understand the way in which an optimal solution must necessarily be composed in a simple way from solutions to smaller subproblems. Let's take a step back, and ask, well. Given that, at the end of the day, we care about the optimal solution to the original problem. Which subproblems are relevant? Which subproblems are we going to be forced to solve? For example, with independent sets in line graphs we observed that to solve a subproblem we needed to know the answers to the subproblems where we pluck either one or two vertices off of the right hand side. So overall what we cared about was subproblems corresponding to prefixes of the graph. In the knapsack problem we needed to understand subproblems that involved one less item and possibly a resus, reduced residual knapsack capacity, so that led to us caring about solutions to subproblems corresponding to all prefixes of the items and all integer possibilities for the residual capacity of a knapsack. In sequence alignment, when we looked at subproblems. As we were plucking a character off of one or possibly both of the strings. So we cared about subproblems corresponding to prefixes of each of the two strings. Now, here's one of the things that's interesting about the binary search tree problem which we haven't seen before. Is that, when we look at a subproblem. In the optimal structure lemma, there's two that we might consider. We don't just pluck off from the right. We care about both the subproblem induced by the left subtree. And that induced by the right subtree. In the first case, we're looking at a prefix of the items we started with. And that's like we've seen in our many examples. But in the second case, the sub problem corresponding to t sub two. That's actually a suffix of the items that we started with. So put differently, the sub-problems we care about are those that can be obtained by either throwing away a prefix from the items that we started with or throwing away a suffix from the items that we started with. So in light of this observation, that the value of an optimal solution depends only immediately on sub problems that you obtain by throwing out a prefix with a, or a suffix of the items, what I want you to think about on this quiz is, what is the entire set of relevant sub problems? That is, for which subsets s of the original items one through n is it important that we compute the value of an optimal binary search tree on the items only in s? So before I explain the correct answer which is the third one, let me talk a little bit about a very natural but incorrect answer, namely the second one. Indeed, the second answer seems to have the best correspondence to the optimal substructure lemma. The optimal substructure lemma states that the optimal solution must be composed of an optimal solution on some prefix and an optimal solution on some suffix, united under a common root r. So we definitely care about the solutions to all prefixes and suffixes of the items but we care about more than just that. So maybe the easiest way to see that is to think about the recursive application of the optimal substructure lemma. And again relevant subproblems at the end of the day are going to correspond to all of the different distinct subproblems that ever get solved over the entire trajectory of this recursive implementation. So, I mean just think about one sort of example path in the recursion tree, right? So in the outermost level recursion you've got the whole item set, let's say there's 100 items one through 100, you're going through and trying all possibilities of the root. So at some point you're trying out root number 23 to see how it does. You have to recurse once on items one through 22 to optimally build a search tree for them, and similarly for items 24 through 100. Now let's sort of drill down into this first recursive call where you recurse on item just one through 22. Now here again, you're going to be trying all possibilities of the route, those 22 choices. At some point you'll be trying route number seventeen. There's again going to be two recursive calls. And the second recursive call is going to be on items eighteen through 22. It's going to be the items that were passed through this recursive call. A prefix of the original items. And then the second recursive call here, locally is going to be on some suffix of that prefix. So in this case, the items eighteen through 22. A suffix of the original prefix, one through 22. So, in general, as you think through this recursion multiple levels. At every step, what you've got going for you is, you're either deleting a chunk of items from the beginning, a prefix. Or you're deleting a chunk of items from the end. But you might be interleaving these two operations. So it is not true that you're always going to have a prefix of a suffix of the original set of items. But. What is true is that you will have some contiguous set of items. It's going to be. If you, if you have I as your smallest item in the subproblem and J is the biggest, you're going to have all of the subproblems in between. And that's because you were only plucking off items from the left or from the right. So that's why C is the correct answer. You need more subproblems than just prefixes and suffixes. Alright, so that was a little tricky, identifying the relevant sub problems but now that we've got them in our grubby little hands the dynamic programming algorithm as usual is just going to fall in to place, the relevant collection of sub problems unlocks the power in a very mechanical way of its entire paradigm. So let's now just fill in all the details. The first step is to formalize the recurrence. That is, the way in which the optimal solution of a given subproblem depends on the value of smaller subproblems. This is just going to be a mathematical formula which encodes what we already proved in the optional substructure lemma. And then we're going to use this formula to populate a table in a dynamic programming algorithm to solve, systematically, the values for all of the subproblems. So let's have some notation to put in our recurrence, in our formula. We're going to be indexing sub-problems with two indices I and J and this is because we have two degrees of freedom where the continuous interval of item starts I, and where the continuous interval of items ends, J. So for a given choice I and J, where of course I should be the most J. I'm going to denote by capital C sub IJ, the weighted search cost of an optimal binary search tree just in the contiguous set of in, items from I to J. And of course, the weights or the probabilities are exactly the same as in the original problem they're just inherited here, PI through PJ. So now let's state the recurrence. So, for a given sub problem cij, we're going to express the value of an optimal binary search tree in terms of those of smaller sub problems. The optimal sub structure lemma tells us how to do this. The optimal substructure lemma says, that if we knew the roots, if we know the choice of the root r which here is going to be somewhere between the items I and j, then in that case, the optimal solution has to be composed of optimal solutions to the two smaller sub-problems united under the root. Now we don't know what the root is. There's a j - I + one possibilities. It could be anything between I and j inclusive. So as usual, we're just going to do brute force search over the relatively small set of candidates that we've identified. So brute force search we encode by just explicitly having a minimum. So I choose some route R somewhere between I and J inclusive. And given a choice of R we're going to inherit the weighted search cost of the optimal solution on just the prefix of items I through R minus one. So on our notation that would be C of I. R minus one. Similarly we pick up the weighted search cost of an optimal solution to the suffix of items R plus one through J. And if you go back to our proof of the optimal substructure lemma you'll see we did a calculation which gives us a formula for what, how the weighted search cost of a tree depends on that of its subtrees. And in addition to the weighted search cost contributed by each of the two search trees we pick up a constant, namely the sum of all of the probabilities in the items we're working with. So here that's sum of. P sub K, where K ranges from the first item in the sub problem I to the last item in the sub problem J. So one extra edge case we should deal with is if we choose the root to be the first item, then the first recursive term doesn't make sense, then we'll have C, I, I minus one, which is not defined. Similarly, if we choose the root to be J, then this last term would be C of J plus 1J which is not defined. Remember indices are supposed to be in order. So in that case, we'll just interpret these capital C's as zero. And so why is the recurrence correct? Well all of the heavy lifting was done and our proof of the optimal substructure lemma. What did we prove there? We proved the optimal solution has to be one of just J minus I plus one possible things. It depends only on the choice of the root. Given the root, the rest is determined for us. The recurrency is by definition doing brute force search through the only set of candidates. So therefore, it is indeed a correct formula for the optimal solution value, in terms of optimal solutions to smaller sub problems.

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