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 4

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

- Tim RoughgardenProfessor

Computer Science

So now that we have our magic formula, our recurrence, all that's left to do is

Â to systematically solve the subproblems. As usual, it is crucial that we solve the

Â subproblems in the right order, from smallest to largest.

Â How should we measure the size of a subproblem in the optimal binary search

Â tree problem? The natural way to do it is the number of items in the subproblem.

Â So if you're starting at I and you're going till J, the number of items in that

Â subproblem is j - i + 1 that, and that's going to be our measure of subproblem

Â size. So let's bust out our [INAUDIBLE] array.

Â The number of dimensions of this array is going to be two and that's because we

Â have two different degrees of freedom for annexing subproblems,

Â one for the start of the contiguous interval, one for the end.

Â So the outer for loop is going to control the subproblem size.

Â It's going to ensure that we solve all smaller subproblems before proceeding to

Â larger subproblems. Specifically, we'll be using an index s S

Â and in the iteration of this outer for loop, whatever the current value of S is,

Â we're only going to consider subproblems of size s + 1.

Â So you should think of s as representing the difference between the larger index j

Â and the earlier index i. The inner for loop controls the first

Â item in the contiguous interval that we're looking at,

Â so that's just i. And now, all we have to do is rewrite the

Â reccurrence in terms of the array entries and with this change variable where S

Â corresponds to j - i. That is for a given subproblem, starting

Â with the item i and ending with the item i + s.

Â We just by by brute force pick the best route, so the route here is going to be

Â similar to i and i + s. Regardless of the choice of the route, we

Â pick up the constant, the sum of the Pks where here, K, is ranging from the first

Â item i to the last item i + s. And then we also look at the previously

Â computed optimal solution values for the two relevant subproblems,

Â one starting in i, ending in r - 1. The other starting in r + 1 and ending at

Â i + s. So a couple of quick comments about the

Â two array lookups on the right-hand side of this formula.

Â so first of all, if you choose i to be, the root to be the first item i, then the

Â first lookup doesn't make sense. If you choose it to be the last item, the

Â second array lookup doesn't make sense. In that case, it's understood we're just

Â going to interpret these lookups as zero. Of course, in an actual implementation,

Â you'd have to include that code but, I'll let you take care of that on your own.

Â So the second comment is just our usual sanity check and again, you should always

Â do this when you write out a dynamic programming algorithm.

Â When you write down your formula to populate the array entries,

Â make sure that on the right-hand side, whenever you do an array lookup,

Â that is indeed already computed and available for constant time lookup.

Â So in this case, whatever our choice of the root is, the two relevant subproblems

Â are going to involve strictly fewer items than what we started with.

Â And therefore, the two subproblem lookups on the right-hand side will indeed have

Â been computed in some previous iteration of the outer for loop.

Â Remember, the outer for loop is ensuring we solve some problems from smallest

Â number of items up to largest number of items.

Â And of course, after the two for loops complete, what we really care about is

Â the answer in A of one comma n, that is the optimal binary search tree

Â value for all of the items that's the eventual output.

Â Some students like to think about these double for loops pictorially. So let's

Â imagine A, the 2-D array is laid out as a grid.

Â So imagine the x-axis correspond to the index i,

Â that is the first item in the set of items we're looking at and the y-axis

Â corresponding to j, the last item in the current set. And let me single out the

Â diagonal of this grid, so these are subproblems corresponding to

Â i = j, that is subproblems with a single

Â element. Now, we only ever solve problems where j

Â is at least as large as i, so that means we're really only filling in the upper

Â left or northwestern part of this table. So we never bother to fill in the

Â southeastern, the bottom right part of this table.

Â We just sort of think of it all as zero. Now, in the first outer iteration.

Â So, when s0. = 0, that's when our dynamic programming

Â algorithm solves, in turn, each of the n single item problems.

Â So, in the first iteration of this double for loop, it's going to solve the

Â subproblem A11. In the next iteration of the inner for

Â loop, it's going to proceed the A22, then A33, and so on.

Â In each of those, both of the array lookups are going to just correspond to

Â zero and we're just going to fill in this diagonal with the base cases,

Â where Aii is just the probability of item i.

Â Then, as the dynamic programming algorithm proceeds, we're going to be

Â filling in the upper left portion of this table diagonal by diagonal.

Â Each time we increment s, the index in the outer for loop, we're going to march

Â up to the next northwesternmost diagonal, and then as we step through the possible

Â values of i, we're going to fill in that diagonal one at a time moving from

Â southwest to northeast. When we're filling in the value of a

Â subproblem on one of these diagonals, all we need to do is lookup the value for two

Â subproblems on lower diagonals. Lower diagonals correspond to subproblems with

Â strictly fewer items. So that's it.

Â That's the dynamic programming algorithm that computes the value of an optimal

Â binary search tree given a set of items with probabilities.

Â I'm not going to say anything about correctness.

Â It's the, the same story as we've seen in the past.

Â All the heavylifting is improving the optimal substructure lemma,

Â that gave us the correctness of our occurrence given that our magic formula

Â is correct and we're just applying it systematically, correctness of the

Â dynamic programming algorithm follows in a straightforward way, just by induction.

Â Let me, however, make some comments about the running time.

Â So, let's just follow the usual procedure.

Â Let's just look at how many subproblems got to get solved and then how much work

Â has to get done to solve each of those subproblems.

Â So as far as the number of subproblems, it's all possible choices of i and j,

Â where i is at most j, or in other words, it's essentially half of that n by n

Â grid. So this is roughly n squared over two,

Â let's just call it theta of n squared, so a quadratic number of subproblems.

Â Now, for each of the subproblems, we have to evaluate this recurrence, we have to

Â evaulate the formula, which conceptually is a breadth-first search through the

Â number of candidates that we've identified. And a disctinction between

Â this dynamic programming algorithm and all of the other ones we've seen

Â recently, sequence allignment, knapsack, computing independent set of the line

Â graphs, is that it's actually kind of a lot of options for what the optimal

Â solution can be. That is, our breadth-first search, for the first time,

Â is not over a merely constant number of possibilities.

Â We have to try every possible route, each of the items in our given subproblem

Â is a candidate route and we try them all. So, given a start item of i and an end

Â item of j, there's j minus i plus one total items and we have to do constant

Â work for each one of those choices. So there will be subproblems, some

Â subproblems that we can evaluate quickly and only say constant time if i and j are

Â very close to each other, but for a constant fraction of the

Â subproblems we have to deal with, this is going to be linear time,

Â theta of n time. So over all, that gives us a cubic

Â running time, theta of n cubed. Alright, so I would say this running time

Â is sort of okay, not great. So it is polynomial time, that's good.

Â That's certainly way, way, way faster than enumerating all of the exponentially

Â many possible binary search trees, so it blows away breath-first search.

Â But it's not something I would call blazingly fast or for free primitive or

Â anything like that. So you're going to be able be to solve

Â problem sizes with n in the 100's, but probably not n in the 1000's.

Â So that will cover some applications where you'd want to use this optimal

Â binary search tree algorithm, but not all of them. So it's good for some things,

Â but it's not a universal solution. On the other hand, here's a fun fact.

Â And the fun fact is you can actually speed up this dynamic programming

Â algorithm significantly. You can keep with the exact same 2-D

Â array with the exact same semantics. Again, each index is going to correspond

Â to the subproblem with the optimal binary search tree between items i and j

Â inclusive. But, you can actually fill up this entire

Â table all n squared entries using only a total of n squared time.

Â That is on average, constant work per subproblem.

Â So this fun fact, it's very clever. It's really more intricate than what we

Â discussed in this video here, but it, it's not impossible to read.

Â So if you're interested, I encourage you to go back to the original papers or

Â search the web for some other resources on this optimized speed up version of

Â this dynamic programming algorithm. I mean, at a very high level,

Â sort of from 30,000 feet, the goal is to avoid doing this

Â breadth-first search over all possible routes in every single subproblem.

Â And it turns out there's structure, nice structure in this optimal binary search

Â tree problem that allows you to piggyback on the work done in smaller subproblems.

Â So, in smaller subproblems, you already searched over a bunch candidate roots and

Â it turns out using the results of those previous breadth-first search is, you can

Â make inferences about which subset of the current set of roots might conceivably be

Â the ones that determine the recurrence. And so, that lets you avoid searching

Â over all of the possible candidates for the roots,

Â instead focusing just on a very small set.

Â In fact, the average, on average, constant number of possible roots over

Â all of the subproblems. And needless to say, this speeding up of

Â the running time from cubic to quadratic really significantly increases the

Â problem sizes that you can now apply this algorithm to.

Â So now, instead of being stuck in the hundreds, you'd certainly be able to

Â solve problem sizes in the 1000's, possibly even in the 10,000's using this

Â quadratic time algorithm. Very cool.

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