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

437 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

In this next sequence of videos we're going to study a slightly more intricate

Â application of the dynamic programming paradigm,

Â namely to the problem of computing optimal search trees.

Â Search trees that minimize the average search time, with respect to a given set

Â of probabilities over the keys. So I'm going to assume in these videos

Â that you remember the basics of the search tree data structure.

Â So if you need to jog your memory, you might want to review the relevant video

Â from part one. So a search tree is they contain objects,

Â each object has a key drawn from some totally ordered sets.

Â And the search tree property states that at each node of a search tree, say it

Â contains some object with a key of value x, it better be the case that everything

Â in the left subtree of that node has keys less than x and everything in the right

Â subtree under the node with key x has to have keys bigger than X. So that has to

Â be true simultaneously at every single node of the search tree.

Â The motivation for the search tree property is so that searching in a search

Â tree just involves following your nose, just like binary search in assorted

Â array. So if you're looking for, say, an object

Â with key seventeen, you know whether to go left or right from the root, just

Â based on the root's key value. If the root has key value twelve, you

Â know where seventeen, if it exists, has to be in the right sub-tree.

Â So you recursively search the right sub-tree.

Â If the root has value 23, you know where seventeen has to be in the left sub-tree.

Â So that's where you recursively search. Something we originally discussed in the

Â context of balanced binary search trees. Like red black trees.

Â And I'm going to reiterate now. Is that, for a given set of keys, there

Â are many, many valid search trees containing those keys.

Â So just to remind you how this works, let's even just suppose there were only

Â three keys in the world, x, y, and z, with x less than, y less than z.

Â One obvious search tree would be the balanced one.

Â So that would put the middle element y at the roots.

Â You would have left child x and right child y.

Â But there's also the two chain search trees containing these three keys, one

Â with the smallest element x at the root, the other with the largest element z at

Â the root. So, given the multiplicity of solutions,

Â all of the different search trees one could use to store objects with a bunch

Â of keys, an obvious question is which one is the best.

Â What's the best search tree to use out of all of the possibilities?

Â So I don't blame you if you've got a sense of deja vu.

Â We did already ask and answer this question in one sense, when we discussed

Â red black trees. There we argued that the best thing to

Â have is a balanced binary search tree that keeps the height as small as

Â possible and therefore the worst case search time, which is proportional to the

Â height, as small as possible, namely logarithmic in the number of objects in

Â the search tree. But now let's make the same kind of

Â assumption that we made when we discussed Huffman codes.

Â That is, let's assume that we actually have accurate statistics about how

Â frequently, each item in the tree is going to be searched for.

Â So maybe we know that item X is going to be searched for 80% of the time,

Â whereas Y and Z will only be searched for 10% each.

Â Could we then improve, upon the perfectly balanced search tree solution?

Â So let me make this question more concrete, just by asking you to compare

Â two candidate solutions. On the one hand the balance tree, which

Â has Y at the root and X and Z as children.

Â On the other hand, the chain which has X as a root, Y as its right child and then

Â Z as the right child of Z, excuse me, Z as the right child of Y.

Â So what is the average search time in each of these two search trees, with

Â respect to the search frequencies I told you, 80% for X, 10% for Y, and 10% for Z?

Â And when I say the search time for a node, I just mean how many nodes do you

Â look at on route to discovering what you're looking for, including that last

Â node itself. So the search time for something that's

Â at the root for example, that would be a search time of just one,

Â because you only look at the root to find it.

Â All right so the correct answer to the quiz is the fourth option 1.9 and 1.3.

Â So to see why, let's just compute the average search time in each of the two

Â proposed search trees. In the first one, with Y at the root,

Â well, 80% of the time we're going to suffer a search time of two, whenever we

Â look for X we have to look at the root Y and then we look at the X.

Â So we pay two 80% of the time and that contributes 1.6.

Â 10% of the time we get lucky, we see a Y, that contributes a.1.

Â 10% of the time we see Z, that contributes another.2 for a total of 1.9.

Â By contrast think about the chain that has X at the root.

Â Here 80% of the time we get lucky, and we only have to pay one.

Â Two for every search for X so that contributes only 8. to the total.

Â It is true our worst case search time has actually gone up.

Â When we see its Z we suffer a search time of three which never ever happened in the

Â balance case. But we pay that three only ten% of the

Â time, that contributes a.3. The remaining ten% of the time we suffer

Â a search time of two to look for Y. That gives us a total of 1.3.

Â And the moral of the story, of course, is that this example exposes an interesting

Â algorithmic opportunity. So the obvious, quote unquote, solution

Â of a perfectly balanced search tree, need not be the best search tree when

Â frequency of access is non uniform. You might want to have unbalanced trees,

Â like this chain if it gets extremely frequent searches, closer to the roots to

Â have smaller search time. So the obvious question is then, given a

Â bunch of items and known frequencies of access, what is the optimal.

Â Search tree. Which search tree minimizes the average

Â search time? So that brings us to the formal problem

Â definition. We're told n objects that we gotta store

Â in a search tree and we're told the frequency of access of each.

Â So let's just keep things simple and the notation straightforward, let's just say

Â the items are named from one, two, all the way up to n, and that is also the

Â order of their respective keys. So key one is the frequency of searching

Â for the item with the smallest key, and so on.

Â You might wonder where these frequencies come from.

Â How would you know exactly how frequently every possible key will be searched for.

Â It's going to depend on the application. And you know there will be applications

Â where you're not going to have these kinds of statistics.

Â And that's where you'd probably want to turn to a general purpose balanced binary

Â search tree solution, something like a red black tree, which guarantees you that

Â every search is going to be reasonably fast.

Â But it's not hard to think about applications where you are going to be

Â able to learn pretty accurate statistics about how frequently different things are

Â searched for. One example might be something like a

Â spell checker. So if you would implement that by storing

Â all of the legally spelled words in a search tree, and as you're scanning a

Â document, and every time you hit a word, you look it up in the search tree to see

Â if it's correctly spelled or incorrectly spelled.

Â You can imagine that after, you know, scanning through a number of documents,

Â you would have pretty good estimates, about how frequently things get searched

Â for. And then you could use those estimates to

Â build a highly optimized binary search tree for all future documents.

Â If you're in some other kind of application where you're concerned about

Â these frequencies changing over time, so, for example, if they're privy to trends

Â in the industry, you could imagine rebuilding the search tree every day or

Â every week or whatever, based on the latest statistics that you've got.

Â In any case, if you're lucky enough to have such statistics, what you're

Â going to want to do is to build a search tree, which, on one hand is valid.

Â It should satisfy the search tree property and on the other hand, should

Â make the average search time as small as possible.

Â So let me go ahead and write down a formula for the average search time.

Â It's the one that you would expect it to be.

Â And also introduce some notation, namely capital C of T.

Â We'll denote the average search time of a proposed search tree T.

Â So for these lectures, we're going to focus on the case where all searches are

Â successful. The only thing that ever gets searched

Â for is stuff that's actually in the tree. But everything we'll talk about in these

Â lectures and the algorithm is easily extended to accommodate the case where

Â you also have unsuccessful searches and statistics about how frequent the various

Â unsuccessful searches are. But, if there is only successful

Â searches, then we average only over the n elements that are stored in the tree.

Â So we sum over each of the items I, we weight it by the probability or the

Â frequency of it's access P sub I, and then that gets multiplied by the search

Â time required in the tree T to find the item I.

Â And as we discussed in the quiz, the search time for a given key I and a given

Â tree T is just the number of nodes you have to visit until you get to the one

Â containing I. So if you think about it, that's exactly

Â the depth of the node in this tree plus one.

Â So for example, if you're lucky enough that the key is at the root, the depth of

Â the root is zero, and we're counting that as a search time as one.

Â So it's depth plus one. So, one minor point.

Â It's going to be convenient for me to not insist that the PI's sum to one.

Â Of course, if the PIs were probabilities, they would sum to one.

Â But I'm going to go ahead and allow them to be arbitrary positive numbers.

Â And that, for the same reason, I'm going to sometimes call capital C of T,

Â the weighted search time rather that the average search time,

Â because I won't necessarily be assuming that the PIs, sum to one.

Â With that said, go ahead and, you know? Think of that as the canonical special

Â case in your mind as we go through these lectures.

Â So for example, in the case where these are probabilities, where the PIs sum to

Â one, we could always as a reference point use a red black tree as our search tree.

Â But, as we've seen, when these PIs are not uniform, you can generally do better.

Â And so that's the point of this computational problem.

Â Exploit the non-uniformities in the given probabilities to come up with the best

Â possibly unbalanced search tree as possible.

Â So I'm sure many of you will have noticed some of the similarities between this

Â computational problem of optimal binary search trees.

Â And one that we already solved back in the greedy algorithm section,

Â namely Huffkin, Huffman codes, which, amongst all prefix free binary codes,

Â minimize the average encoding length. So, let's just be precise about the

Â similarities and differences between the two problems, and in particular, why we

Â can just reuse the algorithm we already saw off the shelf, to solve the optimal

Â BST problem. So it's, of course, super similar in the

Â two cases, is the format of the output. In both problems, the responsibility of

Â the algorithm is to output a binary tree, and the goal is to minimize the average

Â depth, more or less, where the average is with respect to

Â provided frequencies, over a bunch of objects that we care about.

Â Characters from an alphabet in the case of Huffman codes,

Â and a bunch of objects with keys from some totally ordered set in the binary

Â search tree case. And it is true that in the optimal BST

Â case, we're not really averaging depths, we're averaging depths plus one but if

Â you think about it that's exactly the same thing.

Â More important is to understand the differences between the problem solved by

Â Huffman codes and the computational problem that we have to solve here.

Â In the Huffman code case, we had to output of binary code and the key

Â constraint was that it be prefix-free. And in the language of trees what that

Â meant is that the symbols that we're encoding had to correspond to the leaves

Â of the tree. Symbols could not correspond to internal

Â nodes of the tree that we output. Now in the optimal binary search tree

Â problem we do not have this prefix free constraint, so we're going to have a

Â label that is an object at every single node of our tree, whether it's a leaf or

Â not. But, we have a different, seemingly quite

Â a bit harder constraint to deal with, namely the search tree property.

Â So remember, back in the Huffman code case we didn't even have an ordering on

Â the symbols of the, of the alphabet. There wasn't a sense that one of them was

Â less than another, it wouldn't even make sense to talk about the search tree.

Â Brought in that context. Here by contrast, we're given these keys

Â and there's this total lowering on them. And we'd better satisfy the search tree

Â property in the tree that we output, that is in every single node in the tree that

Â we output, it better be the case that all keys in the left sub-tree are less than

Â the key at that node, and all keys in the right sub-tree are bigger than the key at

Â that node. That's a constraint that we have no

Â choice but to satisfy. This constraint is harder in the sense

Â that no greedy algorithm, Huffman's Algorithm or otherwise, solves the

Â optimal binary search tree problem. Rather we're going to have to turn to the

Â more sophisticated tool of dynamic programming to design an efficient

Â algorithm for computing optimal binary search trees.

Â That's the solution we'll start developing in the next video.

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