Transcript
The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseware continue to offer high-quality educational resources for free. To make a donation or view additional materials from hundreds of MIT courses, visit MIT OpenCourseware at ocw.mit.edu. All right, good morning, everyone. Thanks for coming on quiz day. I have to have someone to throw frisbees to. You know, empty chairs would be difficult. All right, so we're going to be doing dynamic programming. A notion you've learned in 6.006. I we look at the three different examples today. The first one is really at the level of 006.
A cute little problem on finding the longest palindromic sequence um inside of a longer sequence. Sometimes it's called longest palindromic subsequence. And uh as we'll talk about, a subsequence means that it can be non-contiguous. So, you could you could skip letters in a sequence of letters and it it it was you would still have a subsequence corresponding to that. Don't have to be contiguous. And then we'll raise the stakes a little bit. So, each of these gets progressively more complicated, more sophisticated. And you'll probably see problems here, at least alternating coin game, that are beyond 006 in the sense that it wasn't covered.
Those kinds of notions weren't covered in 006. So, just in terms of review, I wrote this up here because I don't want to spend a whole lot of time on it. This is something that you should have some familiarity with by from the recitation, for example, that you had on Friday and from 006. Dynamic programming is this wonderful hammer. It's an algorithmic technique that you can use to solve problems that you know, look exponential in complexity, but if you can find this optimum substructure associated with the the problem and its connection to its subproblems. And if you can characterize that, then you can do a recursive decomposition of the problem where you show that you can construct the optimum solution from the subproblems.
And that's really the the key step really in dynamic programming is step two. You know, once you've made this characterization, where you write this recurrence out that relates the optimal value of a bigger problem to the optimal values of subproblems. And you compute the value of the optimal solution through recursive memo memoize recursive memoization. And that memoization is really what gives you the efficient algorithm because you don't repeat the solution of subproblems. You can also do this in an iterative fashion. Essentially, you're going to be computing things bottom up. You might want to think about it as top-down when you write your recurrence, but ultimately when you actually execute the program, you'll be computing things bottom up and you'll be checking the memo table to see if you've actually solved this problem before.
And that would be the recursive memoize case, which in some sense is a little bit easier to think about and translates directly from the recurrence. But the other way to do it is to do it iteratively. And we'll take a look for this first problem as to how you do the two different ways at least from a conceptual standpoint, even though I might not write out the code for each of those cases. So, a couple of choices here. Recursive memoize or essentially do it iteratively. And the smaller subproblems would have to get computed first in both approaches. The one thing that sometimes we don't spend a whole lot of time on is this last step, which is getting the exact solution.
So, a lot of the time you stop with saying, I can compute the value of the optimum solution. The value of in terms of the length of the longest palindromic sequence is seven or nine. But what is that sequence or subsequence? That requires some additional coding, some additional accounting, some the construction of this optimal solution typically requires some backtracking and some information to be keep kept track of during the recursive memoize step or during the iterative step. So, that's something to keep in mind. You're not quite done once you found the value of the optimum solution. More often than not, you want the solution.
All right, so we'll talk about that as well a little bit. But let's just dive in and look at this cute little problem of uh longest palindromic sequence. And palindromes, of course, read the same front to back or back to front. Radar is a palindrome. This is a trivial example. A single letter is a palindrome. Maybe I should have used A since that's actually a word. But you know, here I got BB. That's not definitely not a word. At least not a word that acronym, maybe. Redder is a palindrome. Able was I ere I saw Elba. Right? That's a palindrome. That's of course not a single word, but it's a famous palindrome.
Days of Napoleon. But what we're trying to do here is given that we have this notion of a palindrome, we'd like to discover palindromes inside longer words or longer sequences. So, what we have is a string and we'll call it uh X1 through N. N greater than or equal to one. And we want to find the longest palindrome that is a subsequence. And so, here's an example to get you guys warmed up. We'll have a couple of puzzles here in a second. So, character. And you want to find the longest palindrome. And so, you go, I'll pick C, I'll skip H, I'll pick A, I'll pick R, A, and C. And carac which I guess is not a word either, but uh it's it's the longest palindrome that corresponds to a subsequence of character.
Right? So, the game here, as you can see, is to pick the letters that form the palindrome and drop the ones that don't. Okay? And we're going to have to use dynamic programming to do this. The answer will be greater than or one in length because we've defined a single letter as a palindrome. Right? So, it has to be if you have one letter in the input, well, you just pick that letter. But regardless of how many letters you have on the input greater than or equal to one, you know that you're going to get at least a one letter palindrome at the output. So, here we go. Let's say I have under and this is thanks to Eric here.
Got a couple of nice words. Underqualified. The person who gets me the longest palindrome wins a frisbee. And if you want to code dynamic programming the next two minutes and run it on your laptops, that's perfectly fine with me. That's not cheating. Okay. So, underqualified. So, U is a palindrome. So, we we got that. Right? So, one letter for sure. What else? What's the longest palindrome? Shout it out. Go ahead go ahead, shout it out. D E I What That was quick. Deified. That's right. So, Mm. Right? Well, deify to make is to make somebody a a deity. So, that was you? Couple of couple of you guys?
Do you have a frisbee yet? All right. All right. This is a little bit more difficult. I tried this on my on my daughter yesterday, so I know it's a little more difficult. Right? Turbo ventilator. Right? We'll call that a word. Turbo ventilator. Right? Yell it out. Sorry? Rotor. Okay, well, that's five. Can anybody beat that? Rotator. So, rotator rotator. So, R O T A T O R. Rotator. All right. Who's the rotator? All right. Could you say You already have one? I want to I want to throw this one. Right. Um good practice with the quiz, guys. Good practice with the quiz. No, no, no. The These quiz jokes never go over well.
You know, I've been teaching for 27 years and I still haven't learned that you don't joke about exams. But I So, nothing like this on the quiz. I don't want you studying the thesaurus as opposed to the textbook for the for the next few hours, okay? Nothing like this on the quiz. All right. Um those of you who are missing Python who loves 606 and Python, uh let's let's talk about uh uh how you would uh actually solve this using dynamic programming. Uh and so, what we want is L I J which is the length of the longest palindromic uh subsequence for X I J and we're going to have I um less than or equal to J.
So, so that's essentially what we'd like to uh compute. And uh I essentially when I've said here I when I have L I J, I have decomposed the overall problem into sub problems and it's kind of fairly obvious in this case because I'm going to have to go in order, right? I mean, that's the constraint. A subsequence does maintain the ordering constraint. Uh it's not like I can invert these letters, right? That would be a different problem if I allowed you to do that. So, um I'm going to start somewhere and I'm going to end somewhere and I want to have a non-null subsequence. So, I'm going to have I less than or equal to J.
I'm good with I being equal to J cuz I still have one letter and uh well, that happens to be a palindrome and it'll have a length of one. Right? So, that's my L I J. And what I want to do is uh define a a recursive algorithm that computes L I J. Right? So, uh we'll just try and figure out what the recurrence looks like and then we can talk about uh memoization or iteration. So, if I equals equals J then I'm going to return one because I know that that's a palindrome uh by default. So, that's easy. And um what do you think the next check should be? Uh if if I look at this X sequence and I've have I as the starting point and J as the next uh point, what do you think the next check is going to be uh once I have if I is not equal to J?
Uh sorry, what was that again? If X at I equals X plus X Beautiful. You're just checking to see uh you're you're you're just checking to see whether uh uh the two end points are uh equal or not because if they're equal, uh then uh you can uh uh essentially uh grab those letters and uh say that you're going to be looking at a smaller subsequence uh that uh is going to uh get you a palindrome and you're going to be able to add these two letters that are equal on either side of the computed palindrome from the subsequence. Right? So, if X of I um equals equals X of J then uh I'm going to say if I plus one equals equals J, I'm going to go ahead and return two uh because uh I at that point I'm I'm done.
Uh there's no nothing else to do. Um else I'm going to return two plus L of I plus one J minus one. Right? So, I'm going to look inside and uh I got these two letters on either side that are equal, so I can always uh prepend to the palindrome I got from here the letter and then uh append the same letter and I got two plus whatever value I got from this quantity here. Right? So, so the so far I it's uh not really particularly interesting from a standpoint of constructing the optimum solution, but this last line that we have here where we have the case that the two letters are not equal is the most interesting line of code.
That's the most interesting aspect of this algorithm. Right? So, someone want to tell me what this line is going to be out here? Yeah, go ahead. Max of L I plus one J or L I J. Beautiful. That's exactly right. So, what you're going to do is you're going to say I need to look at two different sub problems and I need to evaluate both of these sub problems uh and uh the first sub problem is I'm going to since these two letters are different, I'm going to have to drop one of them. Okay? And I'm going to look inside. Uh I'm going to say I I in this case I'm going to drop uh the I-th letter and I'm going to get L I plus one J and in the second case I'm going to drop the J-th letter and I'm going to get I J minus one.
And that's it. So, it's uh max and there's nothing that's being added here because uh those two letters, one of them had to get dropped. Uh they they weren't equal, so one of them had to get dropped, so you're not adding anything to this. Right? So, uh so that's good. And at this point, you're kind of done, right? Um Whoops. Oh, nice catch. But you did drop something. So, uh all right. So, uh the the thing that we've done here is gotten to um step three. Right? So, just to be clear, we're not done done uh in terms of this chart here because uh we don't have the code there that corresponds to actually computing uh the sequence.
Right? So, it's not that hard. Uh I'm I'm not going to go over uh the code here. I I'll uh you can certainly uh uh look at it in the notes. Uh but uh you need a little bit of uh tracing backwards uh in this uh recursion to actually compute things. Right? What is the complexity of what I wrote up there, though? Yeah. Theta N squared. Theta N squared. Do people agree that the complexity is theta N squared or is this gentleman an optimist? Is this Is the complexity theta N squared? Tell me why the complexity is theta N squared. Uh because each sub problem is that that occurred right there just actually by itself is constant and then there's theta N squared sub problems.
Absolutely. But if you actually implemented this code and you ran it and N was a was a was a hundred how long would you wait for this code to complete? Look at it. What's missing? The cache, exactly. Well, you fixed uh your own little error there. It was a trick question. Okay? So, there's no recursion. I'm sorry, there's recursion here, but no memoization. Right? So, this is exponential complexity. Right? You will uh recur. In fact, the recurrence for that is something like T of N equals one if N equals one and two T N minus one if N greater than one and this would be two raised to N minus one in complexity.
Right? Now, there's a single line of code and you all know this that would fix this, right? And that single line of code is simply something that says right here look at the L I J and I'm writing this differently. I'm I'm uh I'm calling this now a 2D array. Right? So, that's why I have the open brackets and close brackets. So, I'm overloading L here. But it's a 2D array that is going to essentially be a cache for uh the sub problem uh solution values. Okay? And then if you want to do the the back tracing to actually compute uh the solution, you can certainly have that as an additional record that's uh connected to this very same value, uh but that's uh implementation and we won't really go there.
So, look at L I J and don't recurse if L I J already computed. Okay? So, that's important to remember. Right? Now, if you actually put that uh the cache look up, hash table look up, array look up, what whatever you want to call it out there, then what you said is exactly correct. Right? So, our um our uh formula for computing the complexity of a DP that you've seen a bunch of times and I mentioned in the very first lecture as well is number of subproblems times time to solve each subproblem assuming or given that smaller ones are solved or a lookup is order one. So, lookup Now, you could say the hash table lookup is order one on average, etc.
etc. So, uh what actually happens in the worst case? In this particular case and in most DPs uh you can uh do things like perfect hashing or something that's even simpler in this case is just a 2D array. Uh there's not going to be any collisions if you just use I and J as the indices to the array. So, you will definitely get a an order one lookup uh in in this case and most problems we look at uh in 046. So, if you just do that computation which uh my friend over here just described, you do get your theta n square because you have theta n square subproblems and um um uh time to solve each subproblem given that the smaller ones are solved um is uh is is simply going to be a computation of a of a max uh and an addition, right?
So, all of that is is theta one. Right? Because you're not counting the recursive calls. Okay? So, uh this is our first example. I'm I'm uh done with it. Uh any questions about it? Any questions about DP in general? All right, good. Uh so a little bit of review there. Uh not a particularly complicated question. Uh let's uh go to a different question corresponding to optimal binary search trees, which is a very different question. I I don't think I need this anymore. And it's kind of cute in its own way. One of the things that's interesting about this question is is it seems like a greedy algorithm should work and we'll talk about that and as to why the greedy algorithm, you know, doesn't quite work.
So, it's kind of similar to the interval scheduling and the weighted interval scheduling uh problem that we had uh back in February where the regular interval scheduling problem greedy worked, earliest finish time worked, uh but when it came to weights, we had to graduate um to dynamic programming. So, um here's our second problem. Optimal BSTs. Right? So, what is an optimal BST? Um we have a bunch of keys that we want to store in the BST K1 through Kn and um we'll assume that the way this is set up is that K1 is less than K2 da da da less than Kn and just to make our life easier in our examples I will just assume that Ki equals i.
Um that's not necessarily required for anything we're going to do next, it's just for the sake of examples and keeping things manageable. So, I got a bunch of keys and clearly there many different binary search trees that uh can come uh whether they're balanced or unbalanced, many different binary search trees uh can be consistent with uh a given set of keys. Right? If I choose the root to be uh Kn, then I'm going to get this horribly unbalanced tree. Right? If I chose the root to be somewhere in the middle, then I'm going to get something that looks a little better at least at the top level, but uh again, if I messed it up at the next level, I'd get something that's unbalanced.
Right? So, there's clearly many different BSTs. Uh I'm not talking about balanced BSTs here, but we're going to define an optimality criterion that's a little bit different from balanced BSTs because it's going to have this additional uh cost function associated with it that corresponds to the weight of the keys. Okay? So, what is that? Well, I'm going to have weights um associated with each of these keys corresponding to W1 through Wn and um the easiest way to um motivate you to think that these weights are an interesting addition to this problem is to think about these weights as being search probabilities.
So, what you have for argument's sake is a is a static structure that you've created uh and I mean, you could modify it. There's nothing that's stopping you from doing that, but let's just pretend for now that it's a static structure corresponding to this BST has a particular structure and um uh chances are you're going to be searching for some keys more frequently than others. And the Wis tell you what uh the probabilities are in terms of searching for a particular key uh Ki. Right? So, you can imagine and we won't have this here that uh you take that Wis all sum up to one if you want to think of them as probabilities or you can just I'm just going to give you numbers.
I don't want to deal with fractions. No, don't particularly like fractions. Uh so, uh you can imagine that each probability corresponds to uh Wi divided by the sum of all of the Wis if you want all of the probabilities to sum up to one. Okay? But so, think of them as search probabilities because then you'll see what the point of this exercise is. Uh and uh the point of this exercise is to find the BST T. So, we're actually constructing a binary search tree here. So, it's a little more interesting than than a subsequence for example. It has a richer structure associated with it. There are an exponential number of possible binary search trees that are associated with the given set of n keys that are all, you know, binary search trees that consistent, unbalanced, balanced, you know, unbalanced in one way versus another way, etc.
etc. So, uh we want to find a binary search tree T that uh minimizes um sigma i equals one through n. Obviously, we're going to have this Wi that's uh the game here. Uh depth uh in that T. So, this depth is for that T. What is the depth of the node? Um and K of i plus one. Okay? Um and I'll explain exactly what this is and I'll tell you what precisely the depth is, uh but roughly speaking uh the depth of the root, uh not roughly speaking, the depth of the root is zero. Okay? Uh and uh the the depth of one below the root is one and so on and so forth. Um and so, uh as you can see, what you want to do is collect uh in roughly speaking, you want to collect the high weight nodes uh to have uh low depth, right?
If Wi is high, you want the the multiplicative factor corresponding to depth T uh of that node i, the ith node, uh to be to be small. And if Wi is small, then you don't mind the uh depth uh number to be higher. Uh you only have a certain number of uh low depth nodes. You only have one node of depth zero. And you have two nodes of depth uh one, uh which means that you only have one node where that quantity there is going to be one, right? Because you're doing zero plus one. And you have two nodes where the quantity is going to be two. Um and uh so on and so forth. So, you have some room here to play with corresponding to the BST structure and you want to minimize that quantity.
Okay? Um any questions so far? All right, good. Um so, uh the search probabilities would be an example. So, uh in terms of a more concrete application, you could imagine you had a a dictionary uh English to French, French to English, what have you. And um there are obviously uh words that are more common let's say in uh common speech uh than others and you do want to do the translation uh in a dynamic way using this data structure. And you can imagine that in this case the uh the search probability of a word is associated with the uh occurrence of the word, the uh the number of times uh over some normalized uh number of words that this particular word occurs and that would be the that would be the weight.
So, it makes sense to create a structure that minimizes that function because it would minimize the expected search cost when you want to take this entire uh essay for example and and convert it from English to French or vice versa. Okay? So, this can if if these are search probabilities, then this would minimize this cost function here would minimize expected search cost. Right? Um Makes sense? Okay, so that's the definition of the problem. Um and now we have to talk about um why this is complicated, why uh this requires dynamic programming, uh why can't we um just do something fairly straightforward uh like a like a greedy algorithm.
And so let's look into that. Let me give you a really good sense for what's going on here with respect to this cost function and maybe a little abstract uh by giving you a couple of concrete examples. Uh first off, we got exponentially many trees, exponential in n. Let's say that n equals two. So the number of nodes is two. Then uh remember that I'm assuming that the KIs are all uh uh Is. That's the one and two would be uh the Ks for uh n equals two and one two three for uh K n equals three etc. So I could have a tree that looks like that. And I could have a tree that looks like this. That's it.
Um n equals two, I got two trees. Right? So in this case, my cost function is w1 + 2w2. Uh and in this case, my cost function is 2w1 + w2. Okay? Um just to be clear, um what this is is the uh is is um uh the K, right? And this is also the I. So the numbers that you see inside, uh those are the I numbers, which happen to be equal to the KI numbers, okay? Uh and the weight itself would be the WI. So I put w1 here and the reason it only gets multiplied by one is because the depth here is zero and I add one to it. The depth here is one and I add one to it, which is why I have a two out here. Okay?
Um being a little uh pedantic here uh and pointing things out because you're going to start seeing some equations uh that uh are a little more complicated than this and I don't want you to get confused as to what the weight is and what the key number is and what the depth is. There's three things going on here, okay? So over here, you see that um I got uh I'm looking at w1 here, which is this key, right? So the the one corresponds to the one and and this uh has a depth of one, so I put a two in here and so on. Okay? So so far, so good? Um uh uh when you get to n equals three, um you you start getting Well, you have you have at this point, you have um one two three four five, you got five trees.
Uh and uh the trees look like this. I'll draw them really quickly just to get a sense of the variety here, but I won't write the equations down for um all of them. There you go. So those are the the five binary trees associated with uh n equals three, right? The binary search trees. Um and um this is this is kind of cool. Uh it's nice and balanced. You know, the other ones aren't. Um and I'm not uh I'm not uh um uh looking at um uh do we Should I Should I have another one here? I guess I should have. This is a Oh, no, no. So I'm not doing mirrors. Uh and so so there is there are a bunch of other trees that have the same equation associated with two.
No, that's that's not true because uh these are it. I I I was going to say that you could put three in here, but that won't be a binary search tree. Right? So this this is it. Uh and we got a bunch of trees. This This one would be uh 2w1 + w2 + 2w3 by the same process that I used to show you the w1 + uh 2w2 for the n equals two case, you just go off and that's the equation. And so your goal here in an algorithm, clearly this is not the algorithm you want to enumerate all the exponentially many trees, compute with the equations for each of those trees and pick the minimum. Right? I mean, that would work, but it would take exponential time.
Right? So uh so but that's what you have to do now. Uh that's the the goal. You absolutely want the best possible tree that has for the given WIs that you're going to be assigned as constants, you do want to find the one uh a tree that has the minimum sum uh and you want to do that for arbitrary n and you want to do that in polynomial time. Okay? So uh the first thing that uh you do when you have something like this is forgetting about the fact that uh we're in a dynamic programming lecture, uh a dynamic pro- programming module of this class, when you see a problem like this sort of in the real world, uh you want to think about whether a greedy algorithm would work or not.
Um and uh you don't want to go off and build this dynamic program solution, uh which is chances are going to be in the more in a more uh inefficient than a greedy solution, which if it produces the optimum answer, um is the best way to go. So um an obvious greedy solution would be to pick KR in some greedy fashion. And what is the obvious way of picking KR uh to try and get a greedy solution that at least attempts to minimize that cost function that we have there? Highest weight, right? So just pick KR to be highest weight because uh that goes back to what I said about if WI is high, you want uh this value here to be small, right?
So that's essentially your greedy heuristic. So KR should be picked in a in a greedy fashion. So what you do is you pick KR as the root in this particular problem and you could certainly apply this greedy technique recursively, okay? Uh so you do that for every subproblem that you find because when you do this choice of the the root for KR in the current problem that you have, you immediately split the keys into two sets, right? Uh the sets that have to go on the left hand side uh of KR and the sets that have to go on the right hand side of KR. Right? So in this case, uh you know that you're going to have uh a a bunch of keys here uh that correspond to KI to KR and over here um you're going to have a KR minus one, I should say, cuz you already have KR out there.
And the keys here are going to be KR + 1 to uh KJ if overall uh I'm going to say that um EIJ um is the cost of the optimal BST on KI KI + 1 um all the way to KJ. Okay. So um I'm kind of already setting myself up here for uh uh dynamic programming, but it also makes sense in the case of uh of a greedy algorithm where this greedy heuristic is going to be applied recursively. Okay? So initially, you're going to have uh E1N, right? So if you want to compute E1N, which is the cost of the optimal BST on the original problem, all the way from one to n, you're going to look at it and you're going to say uh I I I have a bunch of keys here with different weights that correspond to K1 through Kn.
I'm going to pick the KR that corresponds to the maximum weight and I'm going to use that as the root node and I'm going to stick that up there. And uh the reason I did that uh is because I'm I believe that this greedy heuristic is going to work where this maximum weight node should have the the absolute minimum depth. Okay? So I stick that up there and then my BST invariant tells me that KI through KR minus one, remember these are sorted, right? Uh and they go uh in increasing order as I have up here, uh you're going to have those on the left and you have you're going to have those on the right.
Uh and then you're going to go solve this problem and uh you can certainly apply the greedy heuristic to solve this problem. Right? You could go essentially uh and find the K uh that uh has the highest weight. So you look at WI through WR minus one and you find the the K that has the highest weight. Right? So you're not going midway here. It's quite possible that KR is K of n. Okay? It just happens to be KR is K of n. So that means that uh uh you have the highest weight node up here, but it's also the the biggest key. So all of the nodes are going to be on the left. So this greedy heuristic, and now you're starting to see maybe there's a problem here because uh if you uh have a situation where the the highest a weight node is also the largest node, you're going to get a pretty unbalanced tree.
Okay? So, I can tell you that greedy doesn't work. And um uh when I give this lecture, I think it was a couple of years ago, I I made that statement and um uh this uh uh annoying student asked me for an example. Okay? And I couldn't come up with one. And so, I kind of build on it, went on, uh completely dissatisfied, of course. And by the end of the lecture, uh the same student came up with the counterexample. Right? So, I I'm going to have to put that up here and uh thank the student who sent me uh email about it. And so, here's a concrete example. It turns out I was trying to get a three-node example for a few minutes and uh fail.
It It's It's It's uh I think impossible. I haven't proved this to to find a three-node example with arbitrary weights for which the greedy algorithm fails. Okay? But four nodes, it fails. Okay? So, that's the good news. Um so, here's Here's the example. Thanks to Nick Davis. And it looks like this. Oops. So, uh I claim that the greedy algorithm for the problem that is given to me I would produce uh this uh BST. Right? And uh the reason for that uh is simple. Uh the highest weight node happens to be node two, which has a weight of 10. So, I would pick that. And I'd stick that up here, which means, of course, that I'm going to have to have one on this side.
And I'm going to have to have four and three on the other side. And since uh four has a higher weight uh than three, I'd pick that first, and then three would have to go over here. Okay? So, if I go do the math, um the cost is going to be 1 * 2, and I'll explain what these numbers are. I did tell you it was going to get a little uh cluttered here with uh with lots of numbers. But if you keep that equation in mind, then uh this should all work out. Um so, what do I have here? Um I'm just computing uh this is W1. So, you you see the first numbers in each of these are the are the weights. Uh and so, this would be W2 and etc.
And you can see that uh this is at a depth one, which means I have to have two here because I'm adding one to the depth. So, I have 1 * 2, uh 10 * 1 because that's at the root, uh 9 * 2, etc. And I get uh I get 54. Right? It turns out the optimum tree, you can do you can do better than that if you pick three um and you go like this. And so, what you have here is the cost equals 1 * 3 plus 10 * 2 plus 8 * 1 plus 9 * 2 and that's 49. Okay? So, I'll let you look at that. Um the bottom line is I because of the way the weights are set up here, uh you really want to use the top three spots uh for which have the the minimum depth uh for the highest weight nodes.
Right? And so, you can see that I could make this I these weights uh arbitrary, obviously, and I could break uh a greedy algorithm as this little example shows. Right? So, we got no recourse here. We got to do some more work. Uh we're going to have to use DP to solve this problem. Uh the good news is DP does solve this problem. Okay? Um so, let's let's take a look at the decomposition. And as with anything else, uh the key is uh uh the the step that corresponds to a breaking up the original problem into two parts uh or more uh that that essentially give you this sort of decomposition. And uh we don't quite know.
So, this is really the key question here. We don't quite know what the root node is going to be. So, what is what do we do when we don't know what to do? Right? What do we do in DP when we don't know what to do? This is a very profound question. What do you do? You guess. And not only do you guess, you guess all outcomes. You You You say, "Is it going to come up heads? Is it going to come up tails? I'll guess both." You have a die, it's going to get rolled a one, two, three, four, five, six. Guess them all, right? So, we're going to have to guess that the root node could be any of the any of the keys.
Right? And it's still I mean, there's there's a linear number of guesses there. That's the good news. It's going to stay polynomial time. Okay? So, we're going to have to guess, and once you do that guess, it turns out that the decomposition that you see up there um is exactly what we want. Uh it's just that the greedy algorithm didn't bother with the all of these different guesses, and the DP is different from the greedy algorithm because um it's going to do each of those guesses, and it's going to pick the best one that comes out of all of those guesses. Right? So, it's really not that different from greedy.
Right? So, um we'll keep that up there. Uh leave that here. Let's go over here. So, the recursion here is not going to be that uh hard once you have gotten the insight that you just have to go make a linear number of guesses corresponding to the root node for your particular subproblem. And obviously, this happens recursively. Okay? So, there's a little subtlety here that I'll point out with respect to writing these equations out. Right? So, what I have here, just to be clear, is what I wrote up there even when I was talking about the greedy algorithm, I uh I had uh the subproblems defined. So, the original problem is E1 through N.
Uh the subproblems correspond to uh EIJ. Uh and I given a subproblem, uh once I make a root choice, I get two subproblems that result from the root choice. Okay? Uh and uh each of those two subproblems is going to be uh something, and this is something to keep in mind as we write these equations out. They're going to be one level below the root. Okay? So, keep in mind that the original EIJ subproblem corresponded to this level, uh but the E uh IR - 1 problem uh and the E R + 1 J problem uh are at uh one level below. Okay? So, keep that in mind as we write these equations out. Um and so, uh what I want to do here is just write the recurrence.
And after that, things become fairly mechanical. The fun is in the recurrence. Right? So, I got WI if I equals J. Right? So, I'm at this level, and uh if I just have one node left, then um at that level uh I'm going to paid uh the the weight associated with that node, uh and I I'm going to have to uh do a certain amount of um um uh of of multiplication here uh with respect to the depth, but uh I'm just talking about EIJ as the subproblem weight, just focusing in on that problem. So, if I only have one node, it's the root node, and that weight is going to be WI because the root node has depth of zero, and I'm going to add one to it.
Right? So, for that subproblem, I got uh I got WI. All right? Keep that in mind because that's the only subtlety here with respect to these equations, making sure that our actual cost function that we're computing has the correct uh depth uh multiplicands associated with it. Okay? So, um then we have our linear guessing uh and uh oh, I I I might have said max at some point. Uh we want to get the the the min here, and I had min minimize here. So, I think I wrote things down correct, but at some point, I think I might have said we want to maximize cost. Uh but we do want to minimize cost here corresponding to the uh the search expected search.
So, we're doing a linear, and uh we're doing a a min, and we're going to go off and look at each of the different uh nodes as being the root just like we discussed. Okay? Um and uh what I'm going to do here is I'm going to simply say first that I'm going to look at EIR - 1, which corresponds to this. Um and I'm going to uh, have plus E of R plus 1, {comma} J. Okay? And I at this point I I don't quite have what I want because I haven't actually taken into account the fact that uh, the the depth of the E I R minus 1 and the R plus 1 J is one more than the E I J. Right? So, it's it's one more than that, right?
And I also haven't taken into account the fact that in this case, I definitely need to add a W I as well. Right? Because the root node is part of my solution in both cases. In one case, it ended my solution. Uh, the top case, but in this case, it's also the root node as you can see over on the left, and I got to add that in there. So, I definitely need to add a W I here. Okay? And what else do I need to add? Uh, from a from from a standpoint of the weights, what other weights do I need to add uh, to to this line? Yeah, go ahead. First of all, shouldn't that be a W R? Uh, first of all, that should be a W R.
You're exactly correct. And you want to add all the weights, right? Uh, and uh, you're exactly right. Um, I have two more Frisbees, but I need to use them for something else. Okay, so you get one next time, right? Or um, do I have more than that? No, no. I these are precious Frisbees here. You know, I Sorry, man, you know. Um, so and you you corrected me, too. You know, shoot. This is This is sad. Uh, uh, so that needed to be a W R, okay? But, you also need to add uh, all of the nodes that are in here because they're one one more level, right? And now you see why I made the mistake, right? I don't usually make mistakes.
But, what I really want actually it's more like, you know, I don't know, a few per lecture, you know, constant order one mistakes. Right? And I'm going to say this is W I {comma} J. All right, where W I {comma} J is simply the sum of all of the weights from I to J. Okay? So, and this makes perfect sense because the nice thing is that it I don't even need to put an R in there. All right, so it's I could choose a particular R. W R will be in there, but all of the other nodes are going to be in there anyway, right? So, it doesn't really matter what the R selection is corresponding to this term here.
I will put it inside the the the minimization. This bracket here is closed with that, but you can pull that out because that doesn't depend on R. It's it's just going to be there for all of the cases, all of the guesses. All right? So, that's it. That's that's our recurrence relationship corresponding to the DP for this particular problem. Um, you can go figure out what the complexity is. Um, I I have other things to do, so we'll move on. Uh, but you can do the same things, and these are fairly mechanical at this point to go write code for it, trace the solution to get the optimum binary search tree, uh, yada yada yada.
All right? Uh, any questions about this equation or anything else? Do people get that? Yeah, go ahead. Where does the depth come So, um, the depth is getting added by the weights. Um, so basically what's happening is that um, as I go deeper into the recursion, I'm adding the weights and potentially multiple times depending on the depth, right? So, if you really think about it, this W I J added all of these weights, but when you go to into this recursion, into the E I of R minus 1, well, you're going to see I to R minus 1 in the next level of recursion. So, you would have added, you know, the weight again, right?
So, it's not the case that the weights are only appearing once. They in fact appearing this many times. Right? So, that's what's kind of cute about this. Right? The way the way we wrote it. Okay? Uh, any other questions? All right, good. So, um, we're done with that. So, one last example. Um, this is again a little bit different from the examples of DP we've looked at up until now because it's it's a game, and you have an opponent, and um, uh, you have to figure out what the opponent is going to do, uh, and you know, try to try to win. Uh, I guess you suppose you could try to lose as well, but um, let's assume here, same thing with minimization and maximization.
Uh, most of the time you can invert these cost functions, and DP will still work. Uh, but let's assume here that uh, you want to win this game. Right? So, uh, so the game is an alternating coins game where we have a row of n coins um, of values V1 through Vn. Um, these are not necessarily in any particular order. Uh, it and n is even. And um, I the goal here is select the outer coins, so uh, select either the first or last coin uh, from the row, and then the uh, opponent plays. Remove permanently, but add it to your value. And receive the value. All right? So, I need two volunteers to play this game, and uh, you want to maximize the value.
The winner gets a blue Frisbee. The loser gets a purple Frisbee because blue is greater than purple. And and you might ask, why is that? Well, if you went to a beach and you saw water this color, and you went to another beach and you saw water this color, which beach would you pick? Right? This is Cozumel. This is Boston Harbor. All right. Right? So, blue is greater than purple, right? Don't use this proof technique in the quiz. All right. So, do I have a couple of volunteers to play this game? Two of them over there. All right, you were waving for him? Yeah, I see one. You can come down. Another volunteer?
Right? Yeah, over there. Right? All right, you don't get your Frisbees yet. So, um, we're going to make this really fair. Right? What's your name? Josiah. Josiah? Tessa. Tessa. Josiah and Tessa, I'm going to write out uh, a bunch of It's going to be a uh, a fairly short game. Okay? And uh, we're going to be really fair, and we're going to flip a coin to decide whether Josiah goes first. You can pick uh, heads or tails. Uh, and or whether Tessa goes first. And you can actually, if you win, you can let her go first if you want. But, you get to choose, right? So, pick. Heads. That's heads. All right, do you want to go first, or do you want to let Tessa go first?
You should go first. All right. So, um, Tessa, you get to go first. Okay. Um, six. Six, okay. So, uh, let's just say T, okay? Uh, so you get to choose either 25 or 4, Josiah. Well, I think I'd pick 25. You think you'll take 25. Okay. So, that's J. All right, so it's it's not down to 4 and 19 over here because those are gone. So, your turn again. Okay. Um, can I take a minute, or should I just go? Uh, well, you can take you can take 30 seconds. Okay. All right. 19. 19, okay. The four. All right, four. Four. All right. And 42? All right, 42. This is one strange game. All right. All right, now we get to add up the numbers.
This is going to be tight. All right? 4 plus 39 is 43. 43 plus 25 is 68. Um, 42 plus 19 is 61. 61 plus 6 is 67. Ooh. All right, well, you get Frisbees. Right? All right. Well, uh, blue for you. Right? I mean, you can give her blue if you like. Oh, yeah, you prefer purple, right? Thanks. Okay, good job. Um, no offenses intended to Josiah and Tessa, but that was a classic example of how not to play the game. First off, Josiah could have won uh, regardless of the coins that were up there, regardless of the values of the coins, if he'd chosen to go first. Right? So, this game, the person who goes first is guaranteed to not lose.
And by that, I mean, uh, uh, you uh, uh, may have a situation where uh, you can have a tie in terms of the values, but you're guaranteed to not lose. All right? So, now he ended up winning anyway, because there were other errors made uh, in in in during this, and I don't have the time to enumerate all of them. Okay? Uh, so, we're just going to go move on and do the right thing. All right? So, So, let me first tell you, outside of DP, just in case you play this game over spring break or something, how you can uh, win this game uh, without having to compute, you know, complicated recursive memorization DP programs, right?
For this case, okay? So, let's say I have V1, V2, V3, all the way to VN - 1 and VN. And remember, N is even. All right? So, you're going to pick N N over two coins uh, if you're the first player, uh, and N over two of you are the second player. Um, so, what the what the first player does um, is simply compute V1, take the odd numbers, and N is even, so you got VN - 1 being odd, compute V1 + V3, all the way to VN - 1, and compare that with uh, the even positions, V2 + V4, all the way to VN. So, in this particular instance, um, uh, Josiah, who went second, uh, uh, but if you just if you just look at the odd positions, which is in fact what he ended up picking, it was 4 + 39 + 25, which is 68.
And uh, so, you can do this computation beforehand. You compute this to be 68 in our case. Compare that with um, 67. Okay? And uh, uh, you don't give up your your uh, your first player advantage. So, you're going with the first player, but now you say, "I know that I can uh, set this up." And that wasn't the order that he did this, but I know I can set this up, so I I always have a chance to get V1, V3, uh, V5, etc. Because let's just say that uh, uh, the first player, Josiah, started first. Uh, and he decided in this case that the odd values are the ones uh, that win, right? So, you'll pick uh, he'll he pick let's say he picks V1.
Uh, at this point, uh, Tessa sees V2 through VN, right? So, he's just looking at that. Now, Tessa could either pick V2, or she could pick VN. In that case, uh, uh, Josiah, who's the first player, could pick V3 or VN - 1, and stick with his rule of picking the odd coins. All right? So, regardless of what Tessa does, uh, uh, the first player uh, uh, Josiah could pick odd if odd was the way to go, or if the values were such that even were were the way to go, he could go even. Okay? So, no reason for the first player to lose, uh, but uh, let's just say that um, you're a nasty person, right? Michael Jordan nasty.
You want to just crush your opponent. You you want to make sure they never want to play you again. Okay? So, now you have a uh, uh, a maximization problem, right? So, this is clearly not DP. You don't need DP to add up a bunch of numbers. Uh, but let's say that you want to given a set of coins V1 through VN, uh, you want a strategy, a dynamic strategy that um, uh, gives you the maximum value. Right? Um, this odd versus even is a bit constraining, because you're stuck to these positions, and it's good to be uh, in that situation if you just want to win, and you don't care how you win. Right? But if you want to maximize, then it's a more complicated problem.
Right? And so, we have to talk about how you would do uh, something that would uh, give uh, maybe it would be V1 and V4 and something else, depends on the values. Uh, how would you get to a situation if you're the first player? We just stick with you're the first player, you know you can't lose using this strategy, but not only do you want to not lose, you want to get as many coins as possible. Let's say this is money. Now, more money is better. Uh, and uh, uh, that's your goal. Okay? So, uh, so people understand that. A little um, little trick there with the I guess a greedy algorithm you can you can think of, or it's not really a even something that you might want to call an algorithm.
Little computation. And our goal now is to maximize the amount of money when assuming you move first. And so, this is going to be a little bit different uh, from all of the other problems we've looked at, because we have to now think about what the opponent would do. Right? And there's going to be a sequence of moves here, right? You're going to move first, so that one is easy. You got the whole problem. Uh, but now you have to say, um, the opponent is going to move uh, and pick a coin, and then you have to think of your subproblems as the potential uh, rows of coins uh, that are going to be different depending on what the opponent does.
Right? And through this process, you have to maximize the value. Right? So, it's it's really pretty different from the other couple of examples that uh, that we looked at. Um, so, we're going to have to do a little bit of setup before we get to the point where we can write something like this, which is uh, the solution to our to our DP. And so, let me do that setup. But it's not super complicated. And part of this is going to look kind of the same uh, as previous problems we've looked at. Um, so, VIJ is the max value we can definitely win if it is our turn and only coins VI through VJ are remain.
Okay. And so, we have VII, then there's only one coin left, and you just pick I. Right? Now, uh, you need this you might say, "Well, but that's never going to happen if there's an even number of coins and I'm playing first, uh, because the other uh, player is going to be at the end of the the the the is is going to be the person who picks the last coin." But we need to characterize VII is because we need to model what the other player is going to do. Right? So, we can't just say that we're going to be looking at even number of coins in terms of the row of coins that uh, you you look at, which is true that when you get to move, you only see an even number of coins if you're the first player, but you do have to model what the opponent does.
So, we need the VII. Okay? Um, and what you you might see, of course, uh, is a board that looks like VII I + 1. Uh, and I mean, it might um, uh, uh, be for some arbitrary I, right? So, that's why I have it up there. But remember that you're only picking uh, coins on the outside, so it's not like you're going to have a gap. I mean, you're not going to have V3 left and V7 left, right? There's no way that's going to happen. You're just going to keep shrinking, taking things from the left or the right. Right? So, it's going to be I and I + 1. Right? That makes sense? Um, and so, in this case, what would you pick?
VI and I + 1. You just pick the max, right? Because at that end of this, uh, either you did it right, or you did it wrong. Either way, you're going to improve your situation by picking the max of VI or VI + 1. Right? So, there's no two things about it. So, here you're going to pick the maximum of the two. Um, and uh, you might have VI I + 2, which is an an odd number of coins uh, that uh, that your opponent might see. Uh, it gets more complicated for VI and I + 2. Uh, we're going to have to now start thinking in more general terms as to what the different moves are. Right? But we got the base cases here.
All I did here was take care of the base case, or a couple of base cases, associated with um, a single coin, which is what your opponent will see and pick, or two coins, which is your last move. Okay? So, with all with DP, of course, you always have to go down to your base case, right? And that's when things become easy. Um so, let's talk about We have to talk about two things and put uh our recurrence together. The two things we have to talk about are what you do when you move. Um and that's actually fairly easy. And uh the second thing is what uh the model of the opponent looks like uh when you're waiting for uh uh him or her to move.
So, let's take a look at your move. And I got V1. Let's look at VI. Let's say VJ here, dot dot dot, VN. Right? So, that's the the what you see uh and you're looking at I and J. And at this point, you're you're seeing uh all those other coins, the outer coins have disappeared uh into people's pockets, uh and uh you're looking at this uh interval. So, I'm going to write out what VIJ should be, and keep in mind that we want to um uh maximize the amount of money, and we want to say that we should be able to definitely win uh this amount of money, right? Regardless of what the opponent does. So, um I want to do uh a max, obviously.
And um I have two choices here. I I can pick VI, or I can pick VJ, right? So, it's not like there's a lot of choices here. Right? So, if I pick uh VI, uh then let me go ahead and say I pick VI here. And here, I'd pick VJ. And uh whoops, let me draw this out a little bit better. So, I got to fill in uh these two uh arguments to to my max. Right? So, um this is easy. Uh I'm going to have a plus VI here. I'm going to have a plus VJ here. Right? So, because I picked the appropriate value. Um and um now, uh this is also not that uh difficult. Uh what exactly happens? What can I put in here if I pick VI?
Uh VI + 1 to J. So, the range becomes uh I + 1 J. So, I got uh uh at I I I have to be a little careful here uh in terms of uh uh whether um I can argue that it's actually the V that I put in here. So, the subtlety here is simply that uh uh that the the VI + 1 J is not something that I see in front of me. Okay? This is the complication. VI + 1 J is never a board that I see in front of me. Whereas VIJ was a board that I saw in front of me. Right? So, I have to model uh at the the boards that I see in front of me, because those are the boards that I have control over, that I can maximize. Right? I the the I need I cannot put VIJ VI + 1 J in there, simply because I I don't quite know what that is, because what I get eventually is not something I control.
Right? It's going to be the the the board after my opponent has moved. All right? So, all I'm going to do is I'm going to say the range um becomes range is um I + 1 J. Um and I'm going to say something else in a second here. Uh the range is uh I J - 1. Okay? And in both of these cases, the opponent moves. Right? So, in order to actually write out my DP, I'm going to have to now uh look at the worst-case situation in terms of the board I get back, because the only times I'm adding values is when I see a board in front of me and I pick a coin. And I'm going to have to say now the opponent is going to see an I + 1 J uh I uh and or or an I - 1 I J - 1, excuse me, uh and uh might do something, and I'm going to get something back.
Uh let's assume that I I'm going to assume that the opponent is just as smart as I am, knows DP, taking 6046, etc., etc. Uh and uh I still want to get the maximum value that I can definitely win. Okay? Um and so, uh we need to look inside of that a little bit, and it's not that hard if you just make the assumption that I just did, which is uh the opponent um is going to uh I mean, might not necessarily do the right thing, but you have to assume that uh And uh it's just one uh more equations. So, here's the solution. We now have a VI + 1 J subproblem with the opponent picking. And um the simple observation is that we are guaranteed the min of VI + 1 J - 1 or VI + 2 J.
In this case, um the opponent picks VJ, and in this case, the opponent picks VI + 1. Right? And you're you're guaranteed the minimum of these two, because the opponent can only pick one coin. Right? So, that's the the simple observation that lets you jump ahead uh at two your next move, which is really what uh the DP is interested in, uh because uh that's the only time that you're actually executing something in terms of picking coins from the board and adding to your value. Right? But, we did did have to model that as to what uh the maximum value was that you could win uh jumping ahead of this move, and you have the the min in here, because you're assuming that uh this is a definite guarantee.
Right? That's what we want. Uh I it it's possible that uh the opponent plays uh um a different game from uh the one that um we think he or she is going to play, which uh maximizes his or her value. But, the min is guaranteed. Okay? So, now that you've made this observation, uh it turns out we just have to take that and uh uh we'll we'll we'll we'll be done. Right? So, let's see. Uh let me erase this. It's the last set of equations. And it's just plugging in that observation into what I wrote before. So, we have VIJ = max. This is the outer max that I had up there already. So, that's the same max.
Um and put these giant brackets here. And inside, I I'm going to plug in this this min, uh which is something that corresponds to the the the value that I would win in the worst case after the opponent plays the best possible move, and that would be VI + 1 J - 1 uh comma VI + 2 J + VI. This VI is the same as this one up here. Um and got a + VJ here, and I didn't actually do this, but in terms of uh writing out uh what the opponent would do in the other subproblem case, but it's really pretty straightforward. Uh you um have a problem uh that corresponds to uh the I J - 1 problem, and the opponent could pick uh the Ith, or could pick pick the J - 1th.
If the opponent picks the J - 1th, you get um V um I J - 2, and uh you need to take the min of that. Uh and the other case where the opponent picks I, in which case you get I + 1 J - 1. Okay? And that's our DP. That's uh that's our DP. Okay? So, the big difference here was uh the modeling that you had to do in the middle. We didn't actually have to do that in any of the DPs uh we've covered uh in uh 046 at least uh up until this point. Um before we talk about complexity, I that should just take um a minute. Uh people buy that? See that? Good. So, uh with all of these problems, the complexities are fairly straightforward to compute.
Uh the complexity here is simply again as before the number of sub problems times the time it it it takes to solve a sub problem. Uh you can see here that these are all constant time operations. So assuming that the the the V I J's have been computed, it's data one time to compute a sub problem. So that's your data one and as before there are n squared sub problems. So let's just do number of sub problems times data one which is data n squared. All right. So that was good. All right. So good luck for the quiz. And don't worry too much about it. See you guys next week.