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

433 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 motivated and formally defined the optimal binary

Â search tree problem, lets think about how to solve it.

Â After settling on dynamic programming as the paradigm we are going to try to use

Â we're going to proceed in the usual way, turning to the optimal solution for

Â clues, asking in what way is it composed of optimal solutions to smaller

Â sub-problems. So let me just remind you of the formal

Â problem statement. There's n objects we got to store in a

Â search tree, and let's just name them in the order of their keys, and let's name

Â them one, two, three, all the way up to n, for simplicity, and we're also given.

Â frequencies or weights reflecting how often the different objects are searched

Â for. So that's p1 up to pn positive numbers.

Â Canonically we think of these summing to one, being probabilities, but actually

Â won't use that fact so in general they're just arbitrary positive numbers.

Â The goal is to output a search tree. It should satisfy the search tree

Â property, it should contain all of these objects one through n, and amongst all

Â such search trees it should minimize the weighted search time.

Â So the sum over all of the items I of the probability of I times the search time

Â for I, namely its depth in the tree plus one.

Â Now in case you're feeling cocky about the fact that the greedy algorithm works

Â to solve the seemingly similar optimal prefix-free binary code problem in the

Â form of Huffman's algorithm, I want to spend a little time pointing out that

Â greedy algorithms are not sufficient, are not correct, to solve the optimal search

Â tree problem. So if we were to design a greedy

Â algorithm what kind of intuition would motivate a particular greedy rule.

Â Well, staying at the objective function it's very clear that we want the objects

Â that high frequency of access to be at or near the root and we want items of low

Â frequency access to be in the bottom levels of the tree, like the leaves.

Â So what are some ways we can compile this intuition into a Greedy algorithm?

Â Well one, perhaps motivated by the success of Huffman's algorithm, is we

Â could think about a bottom up approach. Now I'm not going to define what I mean

Â here precisely, but informally we want to start with the bottom most levels, with

Â the leaves and the nodes you want to put there are the objects that are accessed

Â the least frequently. Any reasonable way of implementing this

Â kind of body of greedy rule is not going to work.

Â Let me show a simple counter example. So, let's just assume we have four

Â objects, one, two, three, four. What I'm showing here on the right in

Â pink is two possible search trees valid for those four keys.

Â And let's assume that, the frequencies are as followed.

Â Object one is searched for two% of the time.

Â Object two for 23% of the time. Object three, the bulk of the time 73%.

Â An object for only one% of the time. Any greedy algorithm which insists on

Â putting the lowest frequency objects in the very bottommost level of the tree is

Â not going to produce this tree on the right, which has the two% object below,

Â at a lower level than the !% object. Instead, such a greedy algorithm would

Â presumably output a searchtree like the one on the left, which has the two as the

Â root, and then the object four, at the lowest level, at depth two.

Â But you should be able to easily convince yourself that, for these probabilities,

Â it's the tree on the right which is the one you want, that's optimal, because the

Â object three is the one that's searched for the bulk of the time, that's the one

Â you want at the root as opposed to the object two.

Â So I realize I'm being a little informal here but I hope you get the idea that a

Â naive bottom-up implementation of a greedy algorithm, which if you think

Â about it is really what we did in Huffman's algorithm, is not going to work

Â here. The same can be said about a top-down

Â approach. Perhaps the simplest top-down approach

Â would be just to take the most frequently searched for object and put that at the

Â root and then recursively develop an appropriate left and right sub-trees

Â under that most frequently accessed element.

Â So let me show you again and, formally, just the same kind of counter-example.

Â We're going to use the exact same four objects, the exact same two trees.

Â I, I will however, change the numbers. Now, let's imagine that object one is

Â searched for almost never, just one percent of the time and each of the other

Â three objects are searched for roughly a third of the time each.

Â But, let me sort of break ties, so that the object number two is the most

Â frequently one. Searched for 34%.

Â So that, in that case the Greedy algorithm will put the 34% node up in the

Â roots when really what should happen is you want a perfectly balanced sub-tree

Â for the objects two, three and four because each accounts for roughly a third

Â of the searches. So let's give object three 33% of the

Â searches and object four 32% of the searches.

Â And again I'll leave it for you to convince yourself that this is indeed a

Â counter example the tree's spit out by the greedy algorithm on the left, we have

Â an average search time of roughly two, where as the search tree on the right we

Â have an average search time of roughly five thirds.

Â So we'd like to produce the tree on the right but the greedy algorithm proposed

Â here will spit out the tree on the left. This of course doesn't exhaust the list

Â of potential greedy algorithms. You could try others but it's not going

Â to work. There's no known greedy algorithm that

Â successfully solves the optimal binary search tree problem.

Â So in particular if we focus on the top down approach.

Â The choice of the route. The choice of what to do at the uppermost

Â level. Has very hard to predict repercussions,

Â for what the two different sub-problems look like.

Â So this is what stymie is, not only the top down gritty approach, but also a

Â naive divide and conquer approach. So for example if we just wanted to split

Â the keys into the first half, and the second half, recursively compute and

Â optimal B is I need on each of those two half's, and then put them back together.

Â The search tree property would say that we have to, unite those two sub-solutions

Â under a root which is the median, in between the two sub-problems.

Â And who is to say that the median is a good choice for the root.

Â Again, because the ramifications further down the tree, maybe that's a stupid

Â root. But, boy, is it tempting to try to solve

Â this problem recursively, right?

Â We're trying to output this binary tree. It has recursive structure.

Â If only we knew which root we should pick.

Â We would love to recurse twice. Once to construct an optimal left

Â subtree. Once to construct an optimal right

Â subtree. Okay,

Â so if only we knew the right route. this is starting to sound familiar,

Â actually. How did it work in all our dynamic

Â programming solutions? We always said, oh.

Â If only a little birdie told us this one little piece of the solution.

Â Well, then, you know? Then we could, sort of, look up or

Â recursively compute the rest of the solution.

Â And extend it back to one for the original problem, easily.

Â So maybe the same thing's true here. Maybe, if only a little birdie told us

Â what the root was. Then we could look up or recursively

Â compute optimal solutions to smaller subproblems.

Â And paste everything back together, and be done.

Â That would be great. So as usual we want to make this precise

Â with an optimal substructure lemma. We want to understand the way in which an

Â optimal solution to an optimal BST problem must necessarily be constructed

Â from optimal solutions to smaller sub-problems.

Â So in the following quiz I'm going to ask you to guess what the appropriate optimal

Â substructure lemma is and then after that quiz once we've identified the right

Â statement at that point I will show you the proof.

Â Okay, so the answer I'm looking for is the fourth one, is D.

Â Which is the strongest statement of all. So the first point is that each of the

Â trees T1 and T2, now as subtrees of a binary search tree these of course are

Â themselves binary search trees, valid for the trees that they contain.

Â And not only can they be viewed as search trees on the keys they contain, but the

Â claim which we'll prove on the next couple slides is that they are indeed

Â optimal. They minimize the weighted search time

Â over all possible search trees for the objects contained in those two trees.

Â So that gets us down, it rules out A, it rules out B.

Â We can say something stronger than that, but we can even say something stronger

Â than C, that each of the two trees is optimal for the items that they contain.

Â We actually know exactly which items are in T1 and which items are in T2.

Â And this is by the search tree property. Search tree property said that every node

Â and in particular here at the roots everything to the left of the root is

Â less than that of everything to the right of the node is bigger than it.

Â So the root being R by assumption we know the objects one through R minus one, but

Â they got to be somewhere. The only way they can be is in the left

Â sub-tree, t1. So that's exactly the contents of T1.

Â Similarly, the contents of t2 are precisely the objects r+1 through n.

Â So the two sub-trees are optimal. And we know exactly which keys they are,

Â it's everything less than r on the left and everything bigger than r on the

Â right. Okay,

Â so here's where things stand at the end of this quiz.

Â We've identified a statement that we're really hoping is true.

Â We're really hoping that an optimal BST, binary search tree, must necessarily be

Â composed in this way of optimal binary search trees for the key sets to the left

Â of the root and the right of the root. If that's true, hopefully with the

Â experience we now have, we can sort of envision what a dynamic programming

Â algorithm might look like. I'll just fill in the details in the next

Â video. If this weren't true, if we didn't have

Â this optimal substructure, honestly, I have no idea how we'd get started.

Â It's really not clear what an algorithm would look like if this weren't true.

Â So the next couple slides, I'm going to prove this to you.

Â The format, you know, will not be radically different than the ones we've

Â already seen. I don't think there'll be any big

Â surprises, but it's so important, this really is the whole reason why the

Â algorithm is going to work, I'm still going to give you a fool proof of this

Â optimal substructure lemma.

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