Algorithms - Lecture 9: Dynamic Programming

so I have one correction I've handed out homework 3 so the first correction for homework 3 is that I made a mistake in in reading my calendar and the due date is are not this Friday but it's actually next Friday so be hopeful there shall be no homeworks due in less than 7 days in this class and I shoot for 7 to 10 all right so what are we going to do in this class we are going to start a new technique a technique that just like divide and conquer it's a pervasive technique it'll be used for many interesting and practical algorithms a lot of the programming contest problems fall into this category it's called dynamic programming and I'm going to give you in the next three lectures six examples ranging from very simple ones getting progressively more and more complicated to illustrate this technique of dynamic programming today I hope to give you a log cutter example matrix chain and a typesetting example but I'm going to start with with a different problem a problem that actually you might encounter it for example in one of your interview questions I'll start with the personal detail although the picture is not coming out correctly as I grew up in Texas I always had a house with stairs in it and then when I went to college I always lived in dorms that had stairs not elevators and then when I went to live in San Francisco I've always had houses with stairs not elevators and then when I went back to grad school I also lived in a five-story walk-up and then after grad school when I lived in Zurich which is where this is from every one of my places were four or five-story walk-up so I've always had stairs in my life in fact the first place that I moved that had an elevator in the place that I lived was in fact Charlottesville so the question I posed to you is if you have a lot of stairs to climb in your life you might think about natural problems for example often times when you're climbing stairs you you take either one step you know you start here at the ground floor and you either take one step or sometimes you take two steps alright so you either take one step at a time or you jump steps now imagine you have n steps which in my case in my Zurich flat I had 98 steps to walk every time I needed to go to the grocery store or do anything outside so if you have 98 steps to walk up to get to your apartment and you can take essentially steps you can either take single steps or double steps how many possible ways are there to climb to the top of your house spend a minute and a half two minutes with your neighbor talking about how many ways there might be to climb up to the top of if you have an N storey staircase and you take either one step or two step at a time how many ways are there decline now let me give you an example for example one way to climb would be one one one one one one right so you just take one etc another way to do would be always take double steps another way would be to take a first double step and then all one's another way would be take two double steps and then all one's or take one and then etc so I would like you to count the number of ways there are to get to the top of your staircase if you're taking only ones these are two Z's the type of question you might encounter in a Google or McKinsey or de sha interview spend two minutes with your neighbors you cannot go backwards okay I hope you've had some time to think about this problem and I hope that you remember when you encounter similar problems at at your job interviews you will remember this algorithmic thinking or this you know this idea of breaking a big problem into smaller problems so this is a good interlude into the new unit that we're going to do dynamic programming so the way one might approach this is to say well this right here how many ways there are to climb and steps I'm going to call that T of n so T of n is going to be the number of ways to climb and steps and now this is going to be a technique that you all wait that you often use in dynamic programming you think if I were at the top if I was here at the top that very last action that I did what did I do I either took a single hop to get here or I took a double hop to get here and so the number of ways to get to the end step is going to be the number of ways to get to the n minus first step I'll write that in red so it's the same color okay so this is the number of ways to get to right here and then taking that one red step plus the number of ways to get right here and take a double step so the insight was think if you're at the very top what was the very last thing that you could have done you could have taken a one or two step and then how did you get to that spot well that's where the recursion comes in now you're going to again apply the same thing now this right here is a recurrence and we've solved several forms of recurrences but we haven't yet solved these type of recurrences question y plus two gotten to which one the blue or the red the final one well the two different ways are either you came along the red path and took a one or the blue path and he took a two so this recurrence right here is actually a famous one made famous by an Italian who is studying the number of rabbits that he would have in his field and this guy was named Fibonacci okay so of course if you have 98 steps you have a lot of ways to climb to the top of your apartment even if you have even if you have 20 steps to stories you have plenty of ways because this Fibonacci recurrence it actually grows this right here is the golden ratio and this this number grows as as basically fee to the end okay now how am I going to use this to here's a simple program to actually compute this number and I think someone over there found found this program as well and the way I the way I think the reason I think this is a really good introduction to dynamic programming let's think about if you wrote Fibonacci in this way what the running time of this algorithm would be alright so this would be the simple way this is exactly how the recurrence is specified and so we're implementing it exactly how the recurrence says in divide and conquer when we came up with an algorithm or a recurrence our implementation exactly mimicked the recurrence so this is though if we if that was our lesson this is what we're doing here let's take a look at what happens so let's say we start with stairs of 5 now that's going to make two recursive calls stairs of 4 and stairs of 3 but of course stairs of 4 is going to be evaluated first and then we're going to make recursive calls like this ok now notice that when the recursion comes all the way back up to s 4 we are then going to do the recursion for s 3 even though we've already computed here the way we've implemented it is actually going to make exactly the same calls if you count how many let's imagine that the running time of this program is actually all in the setting up of a recursive call so the function call in C it takes a little bit of you have to move your stack pointer and you have to do a little bit a little bit a little bit of stuff in order to expand your stack and make a recursive function call so imagine that's all the work that's going on here in order to compute SS stairs of five it's going to take 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 recursive calls if you generalize this if you compute stairs of n right what do you think how many recursive calls you think are you going to make right think for example s of 6 that's going to make a recursive call to s of Phi Vanessa for this you already know how many calls it's going to make and this is going to make some other number right so in this case it'll be 1 2 3 4 5 6 9 okay so s of 6 is going to be 9 plus 15 right s of 7 is going to be s of 6 plus s of 5 right so the number of recursive calls in this algorithm is also going to be related to the Fibonacci number and therefore it's going to be somewhere around P to the N so the point of this aspect of this part right here the point of this slide is to say if we were to implement the function that would compute the Fibonacci number the nth Fibonacci in the most naive or the most clear recursive formulation then the amount of work that we would do would be related to the Fibonacci number so it'd be exponential work to compute a function that's actually quite simple now as a computer scientist you must have you must have a natural instinct on the right thing to do what's the right thing to do here so as a mathematician you'd want to find a closed-form now in fact the closed form for Fibonacci does involve one over square root of five there is such a formula the thing is it's Fibonacci it's a discrete number right it's always going to be an integer the closed form involves a irrational number that you have to compute with so it's to get a very precise computation of the let's say thousandth Fibonacci number using the closed form requires very precise you know floating-point calculation so let's try to let's try to limit ourselves to two discrete methods that we've talked about so far perfect and that's exactly the number one rule of dynamic programming now one insight is that you'll often encounter problems like this where you continue to refer to values that you've already computed and so the way you're going to deal with those things is to not just recompute them on the fly but to be smart about it and remember those answers and refer to them when you need them so in fact this is a better animation so what you're suggesting is okay so we're going to handle the base case as we did before okay and if M contains n returned M of n otherwise basically you're going to set answer equal stares of n minus 1 plus stares of n minus 2 and then you're going to set and then return the answer this is just an implementation of exactly what you said initialize some memory at the beginning and then remember the answers that you compute so let's go through this example I will put that let's now see how this memoization will help in this case so if we had stairs of five we'll run through this line and this line our memory at this point let's put em right here it's all blank so we're going to execute this line right here which will make a recursive call to stairs four and stairs three but it's going to evaluate stairs four first question that's right we can do a slight optimization by changing this order but in fact we're going to come to something even better in the next slide so this is just a stepping stone to a much cleaner implementation what I want to do is of course illustrate the fact that saving these values of course is going to make the computation much much faster so this will compute stairs of three and stairs of two okay so finally when this recursive call calls s1 and s0 these will return one and zero and then this line right here the red line will set s2 to basically be one and it will return one here this will also return one since the base case and then at this point will fill out s3 question you're right good point so then all of my answers will be wrong so write this recursive call will then fill out s4 and then now when we come to s3 since we already have the answer this will return the right answer now why did I put this slide up here I wanted to show we started off with a clean recursive implementation of the stairs number and then we realize we're doing too much work because we're recomputing things we've already computed so we added a memory and in fact this is what our solution came out to be but notice that the way that we filled out our memory we started right here and then we filled out this value and then s3 II it depended on these last two values and so we filled out s three at this spot an S four it depended on these last two values so once these two values were computed we're able to compute s four so in fact if we just look at the order in which we fill em there's actually a much simpler way that the thing that you would probably actually implement in practice if I were to give this as a homework problem you would make some for loop and it would probably look like this stare 0 is equal to once there's a 1 is equal to 1 and then now for I is equal to 2 to n stairs I is equal to stairs I minus 1 plus right this is probably what you would have done right the only reason I went through this is because when we encounter more complicated examples examples that you might not immediately see that you could do this with you should still get used to the thought process the thought process is that we started with a purely recursive formulation we realized that we should memorize or memorize intermediate results that led us to this when we actually thought about it some more we realize that the order of that memoization is all that mattered we didn't have to make all these recursive calls we could just solve the problem by noting the way that the memoization array is filled and just fill in that array directly which led to this final algorithm so that those two ideas are already in dynamic programming the big ideas are that a problem has some recursive sub structure ok in this case it meant T of n was equal to ok so the point is that we could the optimization problem that we're trying to solve has some sort of recursive structure the solution of a problem of size n can be expressed as some function of the solutions of smaller problems and the second big idea is this memoization is that we keep track of intermediate results and going one step further we solve the intermediate problems in a specific order to maximize efficiency so let's highlight let's highlight this technique with our first Bona Fida example non-trivial example of dynamic programming and that is the woodcutter problem so if you like to do wood work you like to make furniture or make objects you know that when you take a log and cut it into lumber there's several ways you can do it so for example here you quarter-sawed if you cut the log like this and then take your boards like this it's called a quarter sawn log and it gives you a grain pattern that looks like that a much simpler and crude way to cut a log is to just regular saw it like this and then you'll see you'll see the grain structure basically looks more flat like that this is all to motivate the following optimization problem so suppose that you had just felt a very large piece of lumber like this like these two fellows right here and now you're deciding that you want to sell this lumber to very high end furniture makers you can see this log is like six feet in diameter and that people buy you know dining tables that are made of a single slab of wood it you know has a very nice grain pattern and probably the tree right there was 250 years old so you know you can imagine the kind of people that like to spend their money on such artifacts and so such a table is going to be very expensive you don't want to just cut this log up in any arbitrary way and the hedge-fund approach to this would be let's first investigate the spot market price for lumber so for example there are prices for one-inch boards 2 inch boards 3 inch boards etc let's call this p1 p2 p3 ok so P I is basically the spot price for on I inch wide slab of lumber P I is the spot price for an I inch wide slab of lumber and that suggests the following log coloured log cutter dilemma so the input to the problem the input to the problem is going to be the size of the input log so you have an N inch wide log that you need to cut you're also given the spot prices for all the slabs of with 1 with 2 with 3 etc and your goal as any capitalist is to maximize profits and that means that you want to find a set of cuts so there could be K cuts you want to find such that of course each of the cuts you only have n your log is only n inches wide and so the cuts that you make have to of course fit into the log and you want to maximize so let me give you an illustration of why this problem is not trivial so if we go back to this slide right here ok it's very conceivable so suppose you had suppose n was equal to 5 so the question is do you cut it as P 1 and P 4 P 2 and P 3 or basically P 5 so it could be that the most money you make is by splitting your 5 inch board into a board of size 2 inches and a board of size 3 inches in another situation it might be better to make a 4 inch board or in another situation it could just be that 5 is the best price okay and now if you have something like you know 200 if n is equal to 200 now you can sort of see that the the problem becomes much more complicated because do you do so if you have a very wide board you wouldn't know whether to cut them in all into one inch slabs or several to you sort of see the same flavor that we have in the staircase problem in that staircase problem I artificially said you can only take one step or two steps not three or four right but in this case question so indeed let's imagine that all of these have to be you can now you can basically generalize this to be a three-dimensional problem but now let's let's generalize it into let's just consider the very simple case where the only decision you make are the width of the planks they're all the same thickness but that's of course a natural generalization if you really have a big log you really need to figure out the right pieces to cut out of that but you can also imagine for example diamonds if you are a miner of diamonds when you get a big diamond you have to like first of all the diamond is raw you have to figure out you know when you have a big chunk of diamond people have to cut these diamonds so the first thing you have to do is figure out how many small diamonds you're going to make based on the fractures in the you know based on the imperfections of the stone etc you fracture this diamond into smaller pieces and then you individually polish them and so forth and of course you want to make the most money out of that raw diamond same sort of problem that that this is trying to reflect it's an optimization problem how do I split something big into smaller pieces that maximizes my revenue from them let's consider the simplest example this okay so does everybody have a feel for the for the complexity of the problem if you had n is equal to 200 and I give you prices from 1 to 200 you have to figure out what the best way to divide that log would be you can't try every single possible combination as we saw with the staircase problem just considering you know ones and twos and threes and for example gets you to too many combinations alright so so this is what I want to do I want to enter jous the way that you think about problems that are phrased like this and it's going to go back to what you did with the staircase problem what did we do to crack that nut we basically said what was the last action that I took when I got to the top of my staircase so now imagine that I have a log okay and imagine that I actually knew what the best solution was that best solution you have to imagine the best the very last cut that you make in the best solution let's call that I K what has to be true for I K to be the best solution it basically has to say that the best way to divide an N inch log must involve the very last cut was of length I K so what I'm going to make from the best solution for cutting this log is going to be the amount of money that I get for that slab plus plus what exactly and this is where the recursive structure is coming into play if I'm looking for the best way to cut the N inch log then my very last option my very last cut if we call that length I K it has to be such that the total amount of money that I get was the price I had from that last cut plus the best way of dealing with the log that was this wide right if there was a better way for dealing with this half then of course I would use that better way and get more money for that log okay so this observation it suggests an approach to a solution so we know that the best of n is going to be Pik plus the best of n minus I K and now we also know something which is how many possible how many possible cuts are there for you that last cut how many options do I have at that spot you have basically n right or n minus one so this suggests that the best way of dealing with n is going to be let's try every single possible cut the best way of splitting that n inch log so in other words the best way to cut a 200 inch log is basically to consider making a 1 inch cut and then cutting 190 inch 99 inch log is to consider these n options so the first step in solving these type of dynamic programming problems is to come up with an equation like this which reflects the recursive sub structure and now the second step is to analyze to remember how to use memoization because notice that B of 199 is also going to require 198 right because this is going to be 1 plus B of 198 2 plus B a 197 right so just like in the staircase problem this is going to be like a staircase problem but it's going to have a much much larger branching factor in stairs you only tried minus 1 and minus 2 right here you're going to be trying every single possibility at every step of the tree ok so we're coming we're getting close we're getting towards a solution if we think about the way in stairs we had a memory M that kept track of prior solutions now think about write the equation tells us that position n is going to require essentially looking at all of the previous positions right and so what that suggests is that the way to solve this problem is to start at this end and incrementally compute each of these values because the eye position it's going to require the previous I minus 1 positions so let's start by computing from the extreme left and incrementally updating this table right so that suggests an approach like this so we say that best of one is basically going to be P of 1 + best of 0 so this is just going to be P of 1 now best of 2 is basically going to be it's going to depend on those two values it's going to be the max of P 2 plus B 0 or P 1 plus B 1 and you fill that position in right there right and now B 3 is going to be the max of P 3 plus B 0 P 2 plus B 1 B 1 plus B 2 spend a minute with your neighbor based on this insight right the algorithm for computing the for solving the long cutter dilemma alright let's regroup and take a look at one possible solution here so what would the idea is that we're going to start in this array right here this array B is going to store the best way to cut a log of size I and so of course if you have a log of with 0 the most money you can make from that log is 0 if it was anything more I would be very wealthy person so we're going to start here with B 0 is equal to 0 and then we're going to iteratively update this where essentially we're going to go from 1 to N and bi is going to be the max of PJ plus B of I minus J ok this is what the mathematical expression was if you were to just write that into a c loop you would essentially initialize bi to some very negative value like negative infinity and then just loop from 1 to I where you create some temp variable which computes PJ plus this value and of course if this value is greater than what you currently have you store that value now what is the running time of this algorithm how many times does it does this loop run n times and notice that this loop right here is going to go from 1 to I all right so the running time is going to be the first time it's going to go through the loop once then it's going to go through it twice the last time it's going to go through the loop n minus 1 times this summation should be familiar it should be roughly theta N squared any questions about this question can you do it better and I would have to think about it I would have to think about it with these type of problems it's conceivable you could go to end log in or and I'm not sure and but the point for this class is just these are stepping stones just like with stairs we did that in order and there's actually a way to do that much better to compute the nth Fibonacci number so there might be a better way to do this but what I want to introduce just with these simple examples is this idea of dynamic programming if we recap what did we do we started the problem staring into this combinatorial explosion of we could have like 14 of these types of things or 12 of that and if you're to think about it in some ad hoc way you'd be overwhelmed with the number of ways you can divide that log and how would you how would you keep track of all of those ways we step back and think and thought you know what the very last action the very last cut that we're going to make on that log has to be of some width let's call it and let's think about that it has to be able wit such that when I leave the rest of that block and cut that rest of the block optimally the number I get is the maximum and that led us to this expression this optimal expression right here and once we came to this conclusion right here we figured out a clever way of implementing it in an array like this that gave us an N squared algorithm for the problem those are the three steps think about the very last step come up with a recursively come up with a solution that illustrates the recursive sub structure and then come up with a way of organizing that the sub problem so that you solve them in the right order so that the solution becomes simple question in the back one second one second I've just figured out how to make those microphones work so push the grey button and say your question so that it gets recorded very good suggestion so what you're saying is let's look at the average value per inch and then pick the width it has the highest one and continue in that way and that's a very good idea that approach is called a greedy algorithm and a greedy algorithm is not going to work in this case in fact your first instinct with many of these dynamic programming problems is to use a greedy algorithm in the homework I try to go through this theme by the last problem essentially says consider a greedy approach and show an example of why that doesn't work so the same situation will arise here you won't get an optimal solution basically because of rounding issues I could come up with a problem instance where some width has the highest average price but if you were to use just entirely that if you're just to use that with you would have some leftover that gives you an like a globally inferior solution question very good question very good question so again I will repeat the question if you don't push the button please remind me to repeat the question do we have to just return the actual value of the log or do we actually need to return the cuts that you need to make what I'm going to suggest is a one-line addition to this algorithm will actually produce that list so oftentimes in these dynamic programming algorithms just computing the actual optimal solution is enough to figure out what the right choices are so what I'm going to suggest is that this spot right here in fact let me let's keep another array called choice inside this inner loop right here we're going to keep another variable choice I and it reflects whichever whichever K was chosen for the max here we just keep track of what that K was so essentially whatever K set the maximum right here we keep track of what that index of that K was so now what we can do is look at choice of n that's going to tell us what the maximum the the actual width of the maximum value at that choice it tells us exactly what the choice is that we made at that end step then if let's say that was like four then we can go to n minus four and look at the choice that was made if that's yep that'll tell us the best choice and so forth so in other words this is just going to keep track of a point a set of pointers which gives you the chain that led to the best actual outcome very good question question that's a good question so in this case and P has to be positive otherwise there is a no no that's not true there are no constraints on the pricing matrix here even if there if you can imagine if the prices were negative you would never select that because then you'd be selling a chunk of wood and actually having to pay someone to take it for you so it wouldn't you're better off from doing nothing yes question okay so this right here the particular value of K that resulted in the max at this step the particular value of K that resulted in the max during this computation so while you were going through this this is a loop right this is a loop right here let's say I've changed variables here but whichever value of J's J went from 1 to I at some point this loop had its maximum that index where it was maximum I'm going to call J star and now in this slide I'm going to change variables and call it K star does that make sense this is a note to myself I'm going to work out an example and try to post it for some like let's say larger scale problems so you can sort of see okay yeah this is just the smallest number it's just a convention because I want I want the very first I want the very first step right here in order to set it to T but this probably this loop will work if you set this to zero as well this one you push the button yes great question choice n would be the choice that you made it position n let's imagine that that choice was four then what you would do after you know that the very last cut you made was of with four you would then go to choice of n minus four and see what choice you made at that spot and you would run that all the way down until you get to zero and those are all the choices that you had to make in order to get an optimal cut great questions well some of the spots in the array be empty there every single spot will be filled because this loop is starting from I to 1 to n so it's going to go through every spot and it's going to set festivai to something the next example I'm only going to introduce in the last five minutes it's slightly it's going to get more complicated than this log cutter it's going to be a two-dimensional version of dynamic programming every one of these examples is going to grow in complexity just by a little bit let me set up the problem in the last few minutes of class so we all remember matrix multiplication from divide-and-conquer if you have a matrix of this size let's say this is R 1 and this is C 1 this is R 2 and C 2 first question how big is the resulting matrix how many rows will there be in this resulting matrix R 1 and how many columns C 2 very good so how many operations are going to be needed to compute this matrix right this little red dot is going to take C 1 operations right C 1 has to be C 1 has to equal R 2 for this to be well-defined so that red dot is going to take C 1 operations and how many dots will there be R 1 times C 2 that's the number of operations which we already know roughly and cubed now imagine you have three matrices you want to to apply because matrix multiplication is associative you can multiply them either these two first or you can multiply them this way so do these two first and then that one or these two first and then that one and why might this matter question exactly so depending on the order that you choose one way might be dramatically more expensive than the other let me try to illustrate with an example here so imagine a 1 a 2 and a 3 are set up in this particular way if we were to multiply these 2 first we would create an intermediate array that's of size 10 by 5 okay and then we'd multiply these two let's figure out how many operations this would take this would take 10 times 100 times 5 in order to multiply these right here and then in order to multiply these 2 right here it would take what 10 times 5 times 50 so what do we have here this is 5000 and this right here is 2500 so the total number of operations is going to be 7,500 remember this number because the following number is going to be much longer suppose we do it this way these two multiplied first we're going to produce an intermediate value of size what 100 by 50 right so just multiplying these two right here is going to take 100 times 5 times 50 okay and already you can see that we're we've blown the budget right because this number right here is 25,000 so just multiplying in the wrong order already you would have been you would have been you could have solved it three times already in the time that if you took the wrong order right again multiplying these two right here is going to take 10 times 100 times 50 which is going to be 50,000 so the total number of operations is going to be much larger okay so what's the point of this the order in which you multiply these matrices matter what's the best order that's the next problem we're going to solve I'll see you on Thursday

Channel: Algos Lecture

Views: 57,921

Rating: 4.9348269 out of 5

Keywords:

Id: sF7hzgUW5uY

Length: 42min 44sec (2564 seconds)

Published: Sun Oct 13 2013