Understanding Dynamic Programming Concepts

all right welcome back to double-oh-six today we start a totally new section of the class up till now we've mostly been showing you really cool and powerful algorithms sorting algorithms graph algorithms data structures trees lots of good stuff that you can apply to solve tons of algorithmic problems either by reducing to the things data structures that we we showed you or reducing to the graph problems that we showed you or by modifying those algorithms a bit today we're going to start a new section on algorithmic design how to from scratch come up with a polynomial time algorithm to solve a problem so this is a and in particular we're going to talk about a algorithmic design paradigm called dynamic programming which is extremely powerful it's probably the most powerful algorithmic design paradigm very general can solve lots of problems it's a particular type of recursive algorithm design and in general this class all of algorithms is about recursive algorithm design at some level because we want to write constant size pieces of code that solve problems of arbitrary size we have some problem size n and we're trying to write you know 100 lines of code or whatever some constant amount that doesn't depend on the problem size we have one algorithm that solves all instances of the problem and so we have to write code that is recursive or uses loops or somehow reuses the instructions that we give the computer and you may know you can convert any algorithm based on loops into an algorithm using recursion and we're going to take the recursive view today in particular because it fits very well with our proof by induction technique which we've used throughout this class but also because it gives us some structure on how different subproblems relate in something called a sub problem graph that we'll be talking about today and so we're going to start out with in general how do we design recursive algorithms that's sort of the overall encompassing everything we have thought very hard to come up with a cool acronym for this paradigm which we invented called sort bot thanks jason and so we'll talk it's not actually for sorting it's just an acronym for subproblems relations topological order base case original problem and time but it's an acronym that will help you remember all the steps you need in order to specify a recursive algorithm and dynamic programming is going to build on this template by adding one new idea called memoization which is just the idea of reusing work that you've done before and that's going to let us solve tons of problems and let's see i don't uh let's get into it so we'll start out today with sort bots so here is sort bot down the column here this is a recursive algorithm design paradigm and in general what we're going to do is take the problem that we actually want to solve and split it up into lots of possible sub problems and so the first part is to define what the heck are the sub problems in general we'll want some polynomial number of them but it's pretty open-ended what these look like and the hardest part usually in deceptive defining a recursive algorithm is figuring out what the sub problems should be usually they're related to the problem you want to solve often the problem you want to solve this is actually near the last step the original problem you're trying to solve is often one of these sub problems and then you use the smaller sub problems in order to build up the final original problem but sometimes at the end you need to take a bunch of sub problems and combine it into your original problem you can think one analogy you can think of here is divide and conquer algorithms which also had this kind of style but more generally we're going to relate different subproblem solutions with some recursive structure some recursive recurrence relation this is just a recursive algorithm that defines how to solve one problem in terms of smaller sub-problems for some notion of smaller and this is given by the topological order so if we think of the sub problems as a graph and we draw an edge between so the vertices of the graph are sub problems the edges are the dependencies between those sub problems then what we'd like is the topological ordering the topological sort problem we talked about in the context of dfs or dag shortest paths uh what we would like is that this uh the sub problems and the calls the recursive calls between them in this recursive relation forms a dag we want it to be acyclic otherwise you have an infinite loop in your recursive calls if you have a cycle you're just go you'll never terminate and so to spec to make sure that our these dependencies between subproblems given by this recurrence relation is a cyclic uh one way to do that is to specify a topological order okay or you could prove it some other way but often it's just a for loop to say just do it in this order then of course any recursive structure needs base cases so that's a useful step not to forget um we want to solve the original problem using these sub problems and then we analyze our running time at the end so six easy steps actually the hardest ones are these two which are interrelated and what we're going to see over the next four lectures this is the first of four lectures on dynamic programming is lots of examples of applying this paradigm over and over together with the memoization idea which we'll get to soon let's see an example first of an algorithm we've already seen which is merge sort so a divide and conquer algorithm phrased in this with this structure of sort bot so for the subproblems so original problem is to sort the elements of a and some sub problems that we solve along the way are sorting different subarrays of a so for every well not for every i and j but for some i and js we sort the items from i up to j minus 1. so i'm going to define that subproblem to be s of i j so this is something that i might want to solve the original problem that i want to solve is s of 0 comma n where n is the length of the array so that's what i actually care about in the end but we're going to solve that by writing it recursively in terms of sorting different subarrays as follows this is the recurrence relation i've written it very simply here of course there's a merge algorithm which is uh somewhat complicated but it's we we saw the two finger linear time merge algorithm given two sorted arrays so this is supposed to be the sorted array version of the items i through m m is the middle element between i and j and the sorted array of the items from m up to j if we merge those that gives us the sorted array from i up to j and that's exactly what merge sort does so this is in general this relation is just some algorithm for if you if you're given the solutions to some smaller sub problems how do i solve uh the sub problem that i want to solve and so we need to make sure that this problem is bigger than the ones that we recursively call on and that we don't get an infinite cyclic group of recursions and here a valid topological order is to say solve these problems in order where j minus i the length of the subarray is increasing and then you can check because m is strictly between i and j as long as we're not in a base case then we know uh we can these subarrays will be smaller than this one and so this increasing order gives us a valid topological order on all of the problems all the sub problems uh we have a base case which is if we don't want to sort anything that's the empty array i already said the original problem and then running time is i mean there's no better way to solve it than the recurrence that we already saw how to solve so this is just another way to think of n log n merge sort in this labeled framework of sort bot let's get to another problem that does not fit recursion so well but we can make it better so this we're going to start with a very simple problem which is computing fibonacci numbers it's really just a toy problem to illustrate a very powerful idea which is memoization so the problem i'm interested in is i'm given a particular number n and i want to compute the nth fibonacci number and in case you forgot the nth fibonacci number is given by this recurrence fn is fn minus one plus fn minus two with base case uh let's say f1 equals f2 equals one and so we'd like to compute this this seems this is a recurrence so it seems very natural to write it as a recursive algorithm so let's try to do it we start with what are the sub-problems the obvious sub-problems are just the various fibonacci numbers fi for i between one and n so they're n of these sub problems cool let's see we want a relation between them well maybe i'll just to distinguish the problems from the fibonacci numbers let me write f of i this is a function an algorithm we're going to define and it's defined to be the goal we're trying to get is the i fibonacci number given i and then we can write the recurrence relation on these guys just uh f of i equals f of i minus 1 plus f of i minus 2. so in other words recursively compute those fibonacci numbers then add them together that's an algorithm next is t for topological order here of course we just want to compute these in order of increasing i from the base cases up another way i like to write this is as a for loop for i equals one to n maybe we'll see why but this gives an explicit order of to compute these sub-problems and all right base case is just the same as the fibonacci numbers but i guess i should write parentheses the original problem we want to solve is f n and the time all right here's where things get interesting or bad so what is the running time of this recursive algorithm as i've stated it so far the running time is given by a recurrence let's write the recurrence so in order to compute f of n uh i recursively compute f of i minus 1 or f of n minus 1 here and i recursively compute f of n minus 2 so that will take t of n minus 2 this first step will take t of n minus 1. and now i need to solve this recurrence uh this is not a recurrence that falls to the master method it doesn't have a divided by so we have to think about it a little bit but we don't have to think about it too hard because this recurrence is the same as this recurrence which is the same as this recurrence i've written it three times now and so the solution to this is the nth fibonacci number uh oh sorry it's a little bit worse because in addition to those recursions i also spend constant time to do the addition maybe more than constant time but if we just count the number of additions we do it will be plus plus one additions okay but this is bigger than the nth fibonacci number and if you know anything about fibonacci numbers they grow exponentially they're about golden ratio to the n i'm wearing golden ratio in case you forgot the number so that's bad because golden ratio is bigger than one so this is exponential growth as we know especially in this time exponential growth is bad and algorithms exponential growth is bad because we can only solve very small problems with exponential growth very small n so this is a terrible way to compute the nth fibonacci number exponential bad okay so don't do this but there's a very tiny tweak to this algorithm that makes it really good which is memoization and this is a big idea it is the big idea of dynamic programming it's a funny word probably made up by a computer scientist um instead of memorization it's memoization because we're going to write things down in a memo pad is the idea and it's a very simple idea which is just remember and reuse solutions to sub-problems so let's draw the recursion tree for this recursive algorithm as we've done it so far so at the top we let me make a little bit of space at the top we are calling f of n and then that calls f of n minus 1 and f of n minus two and it does an addition up here and then this calls f of n minus two and this calls f of n minus three this calls f of n minus three and this calls f of n minus 4. okay and we notice that this sub problem is the same as this sub problem so to compute f of n minus 1 i need f of n minus 3 and also to compute f of n minus 2 i need f of n minus 3. so why are we computing it twice let's just do it once when we solve it let's write it in a table somewhere and then when we need it again we'll just reuse that value question f of n minus 2 is also shared so let me use a different symbol f of n minus 2 is already here so this was at the same level but we also get shared reuse between different levels in fact i wouldn't even call f of n minus 3 because this whole part doesn't need to be computed a second time if i already computed it here it doesn't matter which one comes first let's say this one comes first once this is done i can write it down and reuse it over here okay but actually and then in here we're going to call f of n minus 3 so there's still a another computation of f of n minus 3. when that one's done i won't need to do any do this recursively okay so magically this is going to make this algorithm efficient with this very simple tweak let me write down the tweak more explicitly i won't write code here but just describe it as a data structure so we're going to maintain our good friend the dictionary which is abstract data type or interface we could use different data structures to do it but we're going to map sub problems to their solutions at least the ones that we've solved already and usually we can do this with just a direct access array though you could use a hash table just get expected bounds so uh when we write the code for our recursive function so in general once we have a sort bot description we can turn this into code right we define f of i and it says am i in a base case if so return this otherwise do this recursive call that's our recursive algorithm but we're going to do a little more now at first we're going to check whether this sub problem that we're trying to solve has already been solved and if so we return that stored solution that's the easy case but it might not exist and then we'll we'll compute it in the usual way so what the code then would look like to define f of i is first we check is i in our in our data structure this is usually called the memo so we say is this sub problem is i in my memo data structure if so just return memo of i done no recursion necessary otherwise check if i'm a base case if so done otherwise recurse so recursively call f of i minus 1 and f minus 2. and in this recursion we can see that after we call f of i minus 1 in fact it will have already computed f of i minus 2. so while this call is recursive this one will immediately terminate because i minus 2 will already be in the memo table and so if you think about what happens in fact we'll just have recursion down the left branch of this thing and all the right branches will be free we can just look things up in the memo table so what is the overall running time for fibonacci this should be order n why is it order n this is number of additions come back to that in a second in general the way to analyze an algorithm like this that uses memorization is we just count how many different sub-problems are there because once we solve the sub-problem we will never solve it again that's the whole idea of a memo table so we will solve each sub-problem at most once and so we just need to count how much time does it take to solve every subproblem and here you can see it's constant either it's a base case and it takes constant time or we recursively call these things but those are different sub problems so we're going to count those later and then the work that's actually done by this recurrence is a single addition so in fact it's n additions to compute f n will be exactly n additions so it turns out to be very nice closed form in this case um it should be exactly n sub problems to compute f of n and because we start stop at one and each one has one addition involved i guess not the base case so maybe n minus two okay definitely order n uh now there's this one subtlety uh which let's forget about dynamic programming for a moment and go back to good old lecture one and two talking about the word ram model of computation um a question here that usually doesn't matter in this class usually we assume additions take constant time and we usually do that because it's usually true and in general our model is that w bit additions where w is our machine word size takes constant time but for this problem and this problem only pretty much for fibonacci numbers i happen to know that the fibonacci numbers grow exponentially so to write them down actually requires uh theta n bits because they are some constant to the n power and so they're actually really big uh potential n is probably bigger than w usually you think of problems that are much bigger than 64 or whatever your word size happens to be we do assume that w is at least log n but n is probably bigger than w might be bigger or smaller we don't know and in general to do an n bit addition these are n bit additions is going to take a ceiling of n over w time so in the end we will spend this times n because we have to do that many of them which is n plus n squared over w time so a bit of a weird running time but it's polynomial whereas this original recursive algorithm was exponential here using this one simple idea of just remembering the work we've done suddenly this exponential time algorithm becomes polynomial why because we have few sub-problems we had n sub-problems for each subproblem we could write a recurrence relation that if we already knew the solutions to smaller sub-problems we could compute this bigger problem very efficiently this happened to be constant time or constant additions n over w time but as long as this is polynomial and this is polynomial we're happy because we we have this nice formula that the time it takes is at most the sum over all sub problems of the relation time okay so i'm referring to subproblems the number of them and the time it takes to evaluate this ignoring the recursive calls that's important this is the uh non-recursive part in the notes i call this non-recursive work so this formula gives us a way to bound the running time of one of these algorithms if we use memoization without memoization this is not true fibonacci took exponential time but if we add memoization we know that we only solve each sub problem once and so we just need to see for each one how much did it cost me to compute it assuming all the recursion work is free because that's already taken into account by the summation so in particular this summation is at most the number of sub-problems times the time per sub-problem which in this case is order n we could try to apply that analysis to merge sort because after all this is also a recursive algorithm it happens to not benefit from memoization but we could throw in memorization it wouldn't hurt us but if you think about the call graph here which is like s of zero n which calls s of n of zero n over two and s of n over two n and so on it has the same picture but there's actually no common substructure here you'll never see a repeated sub-problem because this range is completely disjoint from this range but you could throw in memorization and try to analyze in the same way and say well how many sub problems are there well looks like there's there's n choices for i and not quite n choices but in general it's at most n squared different choices in fact it's the triangular number sum of i equals 1 to n of i different possible choices for i and j but this is theta n squared sub problems which seems not so good and then how much time are we spending for per sub problem well to solve s of i j we have to merge about that many elements we know merge takes linear time and so this takes uh theta j minus i time to evaluate and so uh what we'd like to do is sum over all the sub-problems of j minus i this is the uh not triangular number but the tetrahedral number i guess and so we end up that the running time is at most n cubed great um so it's true that n log n is less than or equal to n cubed but obviously not terribly useful this algorithm by the way we already know how to analyze it is indeed n log n and the running time turns out to be theta n log n so sometimes this is this equation is not what you want to use but often it's good enough and especially if you just want to get a polynomial upper bound and then you can try to optimize it later this will give you a polynomial upper bound as long as the number of subproblems is polynomial and the time per subproblem is polynomial and indeed n cubed is polynomial it's not a great polynomial but this is a an alternate way to analyze merge sort obviously don't do this for merge sort but it illustrates the technique good so far any questions all right uh let me remember where we are cool so the next thing i'd like to do is uh show you one more algorithm that we've already seen in this class that fits very nicely into this structure arguably is a dynamic program and that is uh dag shortest paths oh so just to close the loop here when i say dynamic programming i mean recursion with memoization i mean we take we we write a recursive piece of code which is like def f of some args um some you know sub-problem specification we check is the sub-problem uh in the memo table if so uh return memo of subproblem and otherwise check if it's a base case if and solve it if it's a base case and otherwise write the uh recurrence recurse via relation and set the memo table of the subproblem to be one of those things okay so this is the generic dynamic program and implicitly i'm writing fibonacci in that way and all of the dynamic programs have this implicit structure where i start with a memo table which is empty and i always just check if i'm in the memo table if i am i return it otherwise i compute according to this recursive relation by recursively calling f and that's it so this is every dp algorithm is going to have that structure and it's just using recursion and memorization together okay so now let's apply that technique to think about the dag shortest paths problem the problem was i give you a dag i give you a source vertex s single source shortest paths compute the shortest path weight from s to every vertex that's the goal of the problem and we saw a way to solve that which is dag relaxation i'm going to show you a different way which turns out to be basically the same but upside down or flipped left to right depending which way you direct your edges so what are our sub problems well here actually they're kind of spelled out for us we want to compute delta of sv for all v so that is uh size of these sub-problems that turns out to be enough for this overall problem and the original problem we want to solve is all of the sub problems we solve all the sub problems we're done and then we have uh i think we wrote this at some point during the dag shortest paths lecture we have a recursive relation saying that the the shortest way to get from s to v is the minimum of the shortest path to get to some vertex u plus the weight of the edge from u to v why because if we look at a vertex v unless we started there we came from somewhere and so we can consider all of the possible choices for the previous vertex u and if you start at s and get to v you must go through one of them and so this is finding the best way among all the choices of you uh what's the best way to get to you and then take the edge from u to v for all edges uv and this is adjacency minus we don't usually think of that usually we look at adjacency plus the outgoing edges this is the incoming edges and so u is an incoming uv is an incoming edge into v okay if we take that minimum and of course the possible there there is no way to get to v and so i'll also throw infinity into this set take the min of that set that will give me the shortest path weight in an acyclic graph from s to v and great this is recursive right this was a sub problem these are sub problems which are smaller i guess there's no clear notion of smaller here except we already know the clear notion of smaller is the topological order of our dag because our graph is acyclic we know it has a topological order we know how to compute it with dfs and so that guarantees uh there's a topological order to compute these problems and in fact the the relationship between problems is exactly the given graph g in order to compute the shortest path weight from s to v i need to know the shortest pathway from s to all of the incoming vertices to v and so this is uh i guess in the call graph this vertex calls this vertex but i'll direct the edge this way to say that this vertex requires uh this vertex needs to be computed before this one and so then i can compute them in a topological order okay we have a base case which is delta of ss equals zero and the running time is again we can use this formula and say let's just sum over all the sub-problems of the non-recursive work in our recurrence relation and so it's computing this min if i gave you these deltas for free and i gave you these weights which we know from our weight data structure how long does it take to compute this min well however many things there are and how many numbers were were mining which is the size of the incoming adjacency list plus one for that infinity and so if you compute this sum sum of incoming edges to every vertex that's all the edges so this is v plus e okay so in fact this algorithm is morally the same algorithm is the one that we saw in the dag shortest path lecture which was computer topological order and process vertices in that order and relax edges going out from vertices so here uh so in in that algorithm we would have uh tried to relax this edge if if there's a better path to v and the first one certainly is better than infinity so the first one we relax uh indeed uh the next edge if this is a if this gave a better path from s to v then we would relax that edge and update the weight here and do the same here in the end we're just computing this min in the relaxation algorithm but doing it step by step in the in the relaxation algorithm tag relaxation we for each incoming edge to v we update d of v if it's better and so if you if you repeatedly update if you're better that ends up computing a min okay so this is the same algorithm just kind of flipped backwards uh a funny thing although we wrote down the topological order of the subproblem graph here is the topological order of g because the sub-problem graph is g the algorithm doesn't actually have to compute one it's doing it automatically for free if you think about this algorithm a generic dp algorithm which is check whether we're in a memo table if so return otherwise recurse or base case this actually is a depth for search through the sub-problem graph technically through the reverse of the subproblem graph if i draw an edge so from small to big so if i'm just saying i orient the edges from my smaller sub problems to the ones that need it then i'm actually definitely searching backwards in this graph because the bigger problem calls the smaller problem and the memo table is serving as the have i visited this vertex already check in dfs so this is actually a dfs algorithm plus we're doing some computation to actually solve the sub problems we care about so implicit in this algorithm we are doing a dfs and at the same time we're doing this shortest path computation uh in the finishing order of that dfs traversal because all the edges are backwards this is the same as the reverse finishing order if the graph is forwards so in the end we're computing a topological order because uh dynamic programming includes in it uh depth first search oh a lot of words but it's kind of cool that this framework just solves dag shortest paths without much work i mean we we did a lot of work in shorts paths to prove that this relation is true but once you know it's true the algorithm part is is pretty much free you just write down sort bot and you're done okay this brings us to in general at this point we have seen two examples of dynamic programming i guess technically merge sort you can think of as a dynamic program but it doesn't actually reuse anything so it's not interesting and indeed that gave us a really bad bound we've definitely seen bag shortest paths and fibonacci numbers as two interesting examples and what the next remainder of this lecture and the next three lectures are going to be about is more and more examples of dynamic programming and how you can use it to solve increasingly general problems so far we've just solved an easy problem and a problem we already knew how to solve let's go to a new problem which is bowling bowling is popular in boston this boston likes to play candlepin bowling which is a bit unusual uh today we're going to play an even more unusual bowling game one that i made up based on a bowling game that henry dudeny made up in 1908 so ancient bowling i might call it or i think linear bowling is what i might call it i'll just call it bowling here and now i'm going to attempt to draw a bowling pin not bad that might get progressively worse so imagine n identical bowling pins please pretend these are identical and i have a ball which is approximately the same size as a bowling pin these bowling pins are pretty close together i should have left a little gap here and you're a really good bowler now unfortunately these bowling pins are on a line and you're bowling from way down at infinity so when you bowl um you can only hit one pin or two pins or zero pins but probably you want to hit some pins uh so if you pull straight at a pin you will just hit that one pin and if you bowl in the middle between two pins you will knock down that's a ball sorry you will knock down two pins okay this is your model of bowling model of computation now what makes this interesting is that the pins have values pin i has value yeah this is obviously a toy problem uh though this problem this type of bowling does go back to 1908 it was also a toy problem in that setting so each of these uh bowling pins has some number on it let's say one nine nine let me do a slightly more interesting example maybe another one here uh and a two and a five and a five something like this okay uh or maybe make a little more interesting let's put some negative numbers on here okay and the model uh so you're at the carnival bowling each pin has different potentially different values and the model is if you hit one pin i then you get vi points so that's straightforward to make it interesting when you hit two pins you get the product so if i hit two pins it's always i and i plus one for some i you get vi times vi plus one points this is the the game you're playing and it doesn't really matter that this is a product uh product is just some weird function that's hard to imagine if you stare at this long enough you should convince yourself that the optimal solution is probably to so for each of these numbers i could leave it singleton or pair it with its left neighbor or pair it with its right neighbor but the pairings can't overlap because once i hit a pin it's gone it's knocked over and it disappears so because of these nines which are very high value what i'd probably like to do is hit both of them together so pair them up because 9 times 9 is 81 that's really big much better than hitting them individually or hitting 9 times 1 or 9 times 2. one and one is kind of funny because it's actually better to hit them individually that will give you two points whereas if i pair them up i only get one point two and minus five that seems bad negative ten points my goal is to maximize score do you have to hit all the pins let's say no you don't have to hit all the pins so i could skip the minus fives but in fact here uh because they're adjacent minus five times minus five is good that's 25 points so uh the optimal solution for this particular instance are to hit all the pins these positive uh these together these together if i added for example another pin of minus three here i would choose not to hit that pin good question so you just play until you are tired when you decide to stop playing how can i maximize your score there are many variations this game all of them basically any variation not literally every variation but many many variations of this problem can all be solved quickly with dynamic programming but let's solve this particular one okay um so now we're really in algorithmic design mode we need to think about sort bot and in particular we need to think about what would the subproblems be here and at this point we don't have a lot of of help so i should probably give you some tools if i want to solve a problem like this the input is a sequence of numbers right it's a sequence data structure maybe it's an array of numbers which is this v v array and let's see um a general tool for subproblem design which will cover most of the problems maybe all of the problems that we see in this class for dynamic programming here's a trick if your input is a sequence here's some good sub problems to consider uh we could do all prefixes so let's call the sequence x so we could do x prefix means up to a given i for all i we could do all the suffixes x from i onward for all i or we could do substrings which are the consecutive items from i to j i don't write subsequence here subsequence means you can emit items in the middle so substring you have to start at some position and do all the things up to j uh so these are nice easy to express in python notation and these are great because they're polynomial right if i have n things if the length of my sequence x is n then there are n sequences n prefixes technically n plus one so let's do theta n prefixes they're theta and suffixes and they're theta and squared substrings because there's n roughly n choices for i and j separately sorry subsequences good right i didn't write subsequences because in fact there are exponentially many subsequences right it's 2 to the n for every item i could choose it or not so i don't want to parametrize i don't want my sub problems to be sub sequences because that's guaranteed well then you're guaranteed to get an exponential number of sub-problems which is bad we'd like to bound the number of sub-problems by a polynomial so these are three natural ways to get uh polynomial bounds now prefixes and suffixes are obviously better because there's fewer of them linear instead of quadratic and usually almost every problem you'll encounter prefixes and suffixes are equally good it doesn't really matter which one you choose so maybe you like to think of well we'll get to it's you just choose whichever is more comfortable for you but sometimes it's not enough and we'll have to go to substrings that won't be for another lecture or two okay today i claim that prefixes or suffixes are uh enough to solve the bowling problem so what we're going to do is think about i prefer suffixes usually because i like to work from left to right from the beginning to the end so we're going to think of a suffix of the bowling pins and so what is the sub problem on a suffix well a natural version is just to solve the original problem bowling how do i maximize my score if all i were given were these pins suppose the pins to the left of i didn't exist how would i maximize my score on the remaining pins or for this suffix given these four pins what would i do and there's some weird sub problems here right if i just gave you the last pin what would you do nothing that's clearly different from what i would do globally here but i claim if i can solve all suffixes i can solve my original problem because one of the suffixes is the whole sequence so let's do it sort bot for bowling so here's our dynamic program uh the sub problems are suffixes so um all right b of i is the maximum score we could get possible with our starting if we started a game with pins um i i plus one up to n minus one okay which is a suffix of the pins very important whenever you write a dynamic program to define what your sub-problems are don't just say how to compute them but first say what is the goal of the subproblem this is a common mistake to forget to state what you're trying to do so now i have to find b of i um now what is the original thing i'm trying to solve i like to you can you can also put in sort by you could put the o earlier also then it's actually spell sort so why don't i do that for fun the original problem we're trying to solve is b of zero right because that is all of the pins the suffix starting at zero is everything so if we can solve that we're done next is r for relate this is the test of did i get the sub problems right is whether i can write a recurrence relation so let's try to do it we want to compute b of i so we have pin i here and then the remaining pins and the big idea here is to just think about the nice thing about suffixes is if i take off something from the beginning i still have a suffix remember my goal is to take this sub problem which is the suffix starting at i and reduce it to a smaller sub problem which means a smaller suffix so i'd like to clip off a couple one or two items here and then the remaining problem will be one of my sub problems i'll be able to recursively call b of something smaller than i or sorry b of something larger than i will be a smaller subsequence because we're starting later okay so what could i do well the idea is to just look at pin eye and think what what could i do to pin i i could not hit it ever with a ball i could skip it that's one option what would be my score then well i if i skip pin i that leaves the remaining pins which is just a smaller suffix so that is uh b of i plus one i'm going to write a max out here because i'd like to maximize my score and one of the options is forget about pin i just solve the rest another option is i throw a ball and i exactly hit pin i that's a thing i could do and it would it would leave exactly the same remainder so another option is b of i plus 1 plus v i uh why would i prefer this over this well if v i is negative i'd prefer this but if u is positive i'd actually prefer this over that okay so you're going to figure out which is which is better just locally but then there's another thing i can do which is maybe i hit this pin in a pair with some other pin now there's no pin to the left of this one we're assuming we only have the suffix and so the only other thing i can do is throw a ball and hit i together with i plus one and then i get the product now what pins remain i plus two on still a suffix so if i remove one or two items of course i still get a suffix in this case b of i plus two and then the number of points that i add on are vi times vi plus one so this is a max of three things so how long does it take me to compute it i claim constant time if i don't count the time it takes to compute these other subproblems which are smaller because they are smaller suffixes further to the right uh then i'm doing you know a couple of additions product max these are all nice numbers they will assume that they live in a w bit word um because they're only doing constant size products that's good uh so this takes constant constant non-recursive work how many sub-problems are but suffixes so it's a linear number of sub-problems and so the time i'm going to end up needing is the number of sub-problems n times the non-recursive work i do per sub problem which is constant and so this is linear time great now i didn't finish sort bot so there's another t which is to make sure that there is a topological order and that is in decreasing i order or i might write that as a for loop for i equals n n minus 1. this is the order that i would compute uh my problems because the suffix starting at n is the empty suffix the suffix starting at zero that's the one i actually want to compute that's the final suffix i should be computing and then we have a b for base case which is that first case b of n equals uh zero because there's no pins so i don't get any points sad okay so this is it we just take these components plug them into this recursive memoized algorithm and we have a linear time algorithm i want to briefly mention a different way you could plug together those pieces which is called bottom up dp which is uh let's do it for this example so if i have um let's see let me start with the base case b of n equals zero but now it's an assignment and i'm going to do the for loop from the topological order for i equals m n minus 1 to 0. now i'm going to do the relation b of i equals max of b of i plus 1 and b of i plus uh 1 plus v i and v of i plus 2 plus v i v i plus 1. technically this only works if i is strictly less than n minus 1. so i should have an if i is less than n minus 1 for that last part because i can only do i can only hit two pins if there's at least two pins left and then return b of zero so what i just did is a transformation from this sort bot template into a non-recursive algorithm a for loop algorithm where i wrote my base case first then i did my topological order then i did my relation then at the end i did my base not base case the original problem and provided you can write your topological order as some for loops this is actually a great way to write down a dp as code if i were going to implement this algorithm i would write it this way because this is super fast no recursive calls just one for loop in fact this is almost a trivial algorithm it's amazing that this solves the bowling problem it's in some sense considering every possible strategy i could for bowling these pins what we're using is what we like to call local brute force where when we think about pin i we look at all of the possible things i could do to pin i here there's really only three options of what i could do now normally if i if i tried all the options for pin i and then all the options for i plus 1 and i plus 2 and so on that would be exponential it'd be 3 times 3 times 3 that's bad but because i can reuse these sub problems it turns out to only be linear time it's almost like magic dp dp dp is essentially an idea of using local brute force and by defining a small number of sub problems up front and as long as i stay within those sub problems as long as i'm always recursing into this polynomial space i end up only doing polynomial work even though i'm in some sense exploring exponentially many options and it's it's because what i do for this pin doesn't depend too much to what i do to a pin much later and there's a lot of intuition going on here for what uh when dp works but we're going to see a lot more examples of that coming up and i just want to mention that the intuition for how to write a recurrence like this is to think about in the case of suffixes you always want to think about the first item or maybe the first couple items the case of prefixes you always think about the last item and for sub strings it's could be any item maybe in the middle if i remove an item from the middle of the substring i get two substrings so i can recurse here or in general what we want to do is identify some feature of the solution that if we knew that feature we would be done we would reduce to a smaller sub problem in this case we just say well what are the possible things i could do to the first pin there are three options if i knew which option it was i would be done i could recurse and do my addition now i don't know which thing i want to do so just try them all and take the max and if you're maximizing you take the max if you're minimizing you take them in sometimes you take an or or an and there might be some combination function for optimization problems where you're trying to maximize or minimize something like shortest paths we're trying to minimize we put them in here so usually it's min or max and this is extremely powerful uh all you need to do the hard part is this inspired design part where you say what do i need to know that would let me solve my problem if you can identify that and the number of choices for what you need to know is polynomial then you will be able to get a polynomial dynamic program that's the intuition we'll see a lot more examples in the next three lectures

all right welcome back to double-oh-six today we start a totally new section of the class up till now we&#39;ve mostly been showing you really cool and powerful algorithms sorting algorithms graph algorithms data structures trees lots of good stuff that you can apply to solve tons of algorithmic problems either by reducing to the things data structures that we we showed you or reducing to the graph problems that we showed you or by modifying those algorithms a bit today we&#39;re going to start a new section on algorithmic design how to from scratch come up with a polynomial time algorithm to solve a problem so this is a and in particular we&#39;re going to talk about a algorithmic design paradigm called dynamic programming which is extremely powerful it&#39;s probably the most powerful algorithmic design paradigm very general can solve lots of problems it&#39;s a particular type of recursive algorithm design and in general this class all of algorithms is about recursive algorithm design at some level because we want to write constant size pieces of code that solve problems of arbitrary size we have some problem size n and we&#39;re trying to write you know 100 lines of code or whatever some constant amount that doesn&#39;t depend on the problem size we have one algorithm that solves all instances of the problem and so we have to write code that is recursive or uses loops or somehow reuses the instructions that we give the computer and you may know you can convert any algorithm based on loops into an algorithm using recursion and we&#39;re going to take the recursive view today in particular because it fits very well with our proof by induction technique which we&#39;ve used throughout this class but also because it gives us some structure on how different subproblems relate in something called a sub problem graph that we&#39;ll be talking about today and so we&#39;re going to start out with in general how do we design recursive algorithms that&#39;s sort of the overall encompassing everything we have thought very hard to come up with a cool acronym for this paradigm which we invented called sort bot thanks jason and so we&#39;ll talk it&#39;s not actually for sorting it&#39;s just an acronym for subproblems relations topological order base case original problem and time but it&#39;s an acronym that will help you remember all the steps you need in order to specify a recursive algorithm and dynamic programming is going to build on this template by adding one new idea called memoization which is just the idea of reusing work that you&#39;ve done before and that&#39;s going to let us solve tons of problems and let&#39;s see i don&#39;t uh let&#39;s get into it so we&#39;ll start out today with sort bots so here is sort bot down the column here this is a recursive algorithm design paradigm and in general what we&#39;re going to do is take the problem that we actually want to solve and split it up into lots of possible sub problems and so the first part is to define what the heck are the sub problems in general we&#39;ll want some polynomial number of them but it&#39;s pretty open-ended what these look like and the hardest part usually in deceptive defining a recursive algorithm is figuring out what the sub problems should be usually they&#39;re related to the problem you want to solve often the problem you want to solve this is actually near the last step the original problem you&#39;re trying to solve is often one of these sub problems and then you use the smaller sub problems in order to build up the final original problem but sometimes at the end you need to take a bunch of sub problems and combine it into your original problem you can think one analogy you can think of here is divide and conquer algorithms which also had this kind of style but more generally we&#39;re going to relate different subproblem solutions with some recursive structure some recursive recurrence relation this is just a recursive algorithm that defines how to solve one problem in terms of smaller sub-problems for some notion of smaller and this is given by the topological order so if we think of the sub problems as a graph and we draw an edge between so the vertices of the graph are sub problems the edges are the dependencies between those sub problems then what we&#39;d like is the topological ordering the topological sort problem we talked about in the context of dfs or dag shortest paths uh what we would like is that this uh the sub problems and the calls the recursive calls between them in this recursive relation forms a dag we want it to be acyclic otherwise you have an infinite loop in your recursive calls if you have a cycle you&#39;re just go you&#39;ll never terminate and so to spec to make sure that our these dependencies between subproblems given by this recurrence relation is a cyclic uh one way to do that is to specify a topological order okay or you could prove it some other way but often it&#39;s just a for loop to say just do it in this order then of course any recursive structure needs base cases so that&#39;s a useful step not to forget um we want to solve the original problem using these sub problems and then we analyze our running time at the end so six easy steps actually the hardest ones are these two which are interrelated and what we&#39;re going to see over the next four lectures this is the first of four lectures on dynamic programming is lots of examples of applying this paradigm over and over together with the memoization idea which we&#39;ll get to soon let&#39;s see an example first of an algorithm we&#39;ve already seen which is merge sort so a divide and conquer algorithm phrased in this with this structure of sort bot so for the subproblems so original problem is to sort the elements of a and some sub problems that we solve along the way are sorting different subarrays of a so for every well not for every i and j but for some i and js we sort the items from i up to j minus 1. so i&#39;m going to define that subproblem to be s of i j so this is something that i might want to solve the original problem that i want to solve is s of 0 comma n where n is the length of the array so that&#39;s what i actually care about in the end but we&#39;re going to solve that by writing it recursively in terms of sorting different subarrays as follows this is the recurrence relation i&#39;ve written it very simply here of course there&#39;s a merge algorithm which is uh somewhat complicated but it&#39;s we we saw the two finger linear time merge algorithm given two sorted arrays so this is supposed to be the sorted array version of the items i through m m is the middle element between i and j and the sorted array of the items from m up to j if we merge those that gives us the sorted array from i up to j and that&#39;s exactly what merge sort does so this is in general this relation is just some algorithm for if you if you&#39;re given the solutions to some smaller sub problems how do i solve uh the sub problem that i want to solve and so we need to make sure that this problem is bigger than the ones that we recursively call on and that we don&#39;t get an infinite cyclic group of recursions and here a valid topological order is to say solve these problems in order where j minus i the length of the subarray is increasing and then you can check because m is strictly between i and j as long as we&#39;re not in a base case then we know uh we can these subarrays will be smaller than this one and so this increasing order gives us a valid topological order on all of the problems all the sub problems uh we have a base case which is if we don&#39;t want to sort anything that&#39;s the empty array i already said the original problem and then running time is i mean there&#39;s no better way to solve it than the recurrence that we already saw how to solve so this is just another way to think of n log n merge sort in this labeled framework of sort bot let&#39;s get to another problem that does not fit recursion so well but we can make it better so this we&#39;re going to start with a very simple problem which is computing fibonacci numbers it&#39;s really just a toy problem to illustrate a very powerful idea which is memoization so the problem i&#39;m interested in is i&#39;m given a particular number n and i want to compute the nth fibonacci number and in case you forgot the nth fibonacci number is given by this recurrence fn is fn minus one plus fn minus two with base case uh let&#39;s say f1 equals f2 equals one and so we&#39;d like to compute this this seems this is a recurrence so it seems very natural to write it as a recursive algorithm so let&#39;s try to do it we start with what are the sub-problems the obvious sub-problems are just the various fibonacci numbers fi for i between one and n so they&#39;re n of these sub problems cool let&#39;s see we want a relation between them well maybe i&#39;ll just to distinguish the problems from the fibonacci numbers let me write f of i this is a function an algorithm we&#39;re going to define and it&#39;s defined to be the goal we&#39;re trying to get is the i fibonacci number given i and then we can write the recurrence relation on these guys just uh f of i equals f of i minus 1 plus f of i minus 2. so in other words recursively compute those fibonacci numbers then add them together that&#39;s an algorithm next is t for topological order here of course we just want to compute these in order of increasing i from the base cases up another way i like to write this is as a for loop for i equals one to n maybe we&#39;ll see why but this gives an explicit order of to compute these sub-problems and all right base case is just the same as the fibonacci numbers but i guess i should write parentheses the original problem we want to solve is f n and the time all right here&#39;s where things get interesting or bad so what is the running time of this recursive algorithm as i&#39;ve stated it so far the running time is given by a recurrence let&#39;s write the recurrence so in order to compute f of n uh i recursively compute f of i minus 1 or f of n minus 1 here and i recursively compute f of n minus 2 so that will take t of n minus 2 this first step will take t of n minus 1. and now i need to solve this recurrence uh this is not a recurrence that falls to the master method it doesn&#39;t have a divided by so we have to think about it a little bit but we don&#39;t have to think about it too hard because this recurrence is the same as this recurrence which is the same as this recurrence i&#39;ve written it three times now and so the solution to this is the nth fibonacci number uh oh sorry it&#39;s a little bit worse because in addition to those recursions i also spend constant time to do the addition maybe more than constant time but if we just count the number of additions we do it will be plus plus one additions okay but this is bigger than the nth fibonacci number and if you know anything about fibonacci numbers they grow exponentially they&#39;re about golden ratio to the n i&#39;m wearing golden ratio in case you forgot the number so that&#39;s bad because golden ratio is bigger than one so this is exponential growth as we know especially in this time exponential growth is bad and algorithms exponential growth is bad because we can only solve very small problems with exponential growth very small n so this is a terrible way to compute the nth fibonacci number exponential bad okay so don&#39;t do this but there&#39;s a very tiny tweak to this algorithm that makes it really good which is memoization and this is a big idea it is the big idea of dynamic programming it&#39;s a funny word probably made up by a computer scientist um instead of memorization it&#39;s memoization because we&#39;re going to write things down in a memo pad is the idea and it&#39;s a very simple idea which is just remember and reuse solutions to sub-problems so let&#39;s draw the recursion tree for this recursive algorithm as we&#39;ve done it so far so at the top we let me make a little bit of space at the top we are calling f of n and then that calls f of n minus 1 and f of n minus two and it does an addition up here and then this calls f of n minus two and this calls f of n minus three this calls f of n minus three and this calls f of n minus 4. okay and we notice that this sub problem is the same as this sub problem so to compute f of n minus 1 i need f of n minus 3 and also to compute f of n minus 2 i need f of n minus 3. so why are we computing it twice let&#39;s just do it once when we solve it let&#39;s write it in a table somewhere and then when we need it again we&#39;ll just reuse that value question f of n minus 2 is also shared so let me use a different symbol f of n minus 2 is already here so this was at the same level but we also get shared reuse between different levels in fact i wouldn&#39;t even call f of n minus 3 because this whole part doesn&#39;t need to be computed a second time if i already computed it here it doesn&#39;t matter which one comes first let&#39;s say this one comes first once this is done i can write it down and reuse it over here okay but actually and then in here we&#39;re going to call f of n minus 3 so there&#39;s still a another computation of f of n minus 3. when that one&#39;s done i won&#39;t need to do any do this recursively okay so magically this is going to make this algorithm efficient with this very simple tweak let me write down the tweak more explicitly i won&#39;t write code here but just describe it as a data structure so we&#39;re going to maintain our good friend the dictionary which is abstract data type or interface we could use different data structures to do it but we&#39;re going to map sub problems to their solutions at least the ones that we&#39;ve solved already and usually we can do this with just a direct access array though you could use a hash table just get expected bounds so uh when we write the code for our recursive function so in general once we have a sort bot description we can turn this into code right we define f of i and it says am i in a base case if so return this otherwise do this recursive call that&#39;s our recursive algorithm but we&#39;re going to do a little more now at first we&#39;re going to check whether this sub problem that we&#39;re trying to solve has already been solved and if so we return that stored solution that&#39;s the easy case but it might not exist and then we&#39;ll we&#39;ll compute it in the usual way so what the code then would look like to define f of i is first we check is i in our in our data structure this is usually called the memo so we say is this sub problem is i in my memo data structure if so just return memo of i done no recursion necessary otherwise check if i&#39;m a base case if so done otherwise recurse so recursively call f of i minus 1 and f minus 2. and in this recursion we can see that after we call f of i minus 1 in fact it will have already computed f of i minus 2. so while this call is recursive this one will immediately terminate because i minus 2 will already be in the memo table and so if you think about what happens in fact we&#39;ll just have recursion down the left branch of this thing and all the right branches will be free we can just look things up in the memo table so what is the overall running time for fibonacci this should be order n why is it order n this is number of additions come back to that in a second in general the way to analyze an algorithm like this that uses memorization is we just count how many different sub-problems are there because once we solve the sub-problem we will never solve it again that&#39;s the whole idea of a memo table so we will solve each sub-problem at most once and so we just need to count how much time does it take to solve every subproblem and here you can see it&#39;s constant either it&#39;s a base case and it takes constant time or we recursively call these things but those are different sub problems so we&#39;re going to count those later and then the work that&#39;s actually done by this recurrence is a single addition so in fact it&#39;s n additions to compute f n will be exactly n additions so it turns out to be very nice closed form in this case um it should be exactly n sub problems to compute f of n and because we start stop at one and each one has one addition involved i guess not the base case so maybe n minus two okay definitely order n uh now there&#39;s this one subtlety uh which let&#39;s forget about dynamic programming for a moment and go back to good old lecture one and two talking about the word ram model of computation um a question here that usually doesn&#39;t matter in this class usually we assume additions take constant time and we usually do that because it&#39;s usually true and in general our model is that w bit additions where w is our machine word size takes constant time but for this problem and this problem only pretty much for fibonacci numbers i happen to know that the fibonacci numbers grow exponentially so to write them down actually requires uh theta n bits because they are some constant to the n power and so they&#39;re actually really big uh potential n is probably bigger than w usually you think of problems that are much bigger than 64 or whatever your word size happens to be we do assume that w is at least log n but n is probably bigger than w might be bigger or smaller we don&#39;t know and in general to do an n bit addition these are n bit additions is going to take a ceiling of n over w time so in the end we will spend this times n because we have to do that many of them which is n plus n squared over w time so a bit of a weird running time but it&#39;s polynomial whereas this original recursive algorithm was exponential here using this one simple idea of just remembering the work we&#39;ve done suddenly this exponential time algorithm becomes polynomial why because we have few sub-problems we had n sub-problems for each subproblem we could write a recurrence relation that if we already knew the solutions to smaller sub-problems we could compute this bigger problem very efficiently this happened to be constant time or constant additions n over w time but as long as this is polynomial and this is polynomial we&#39;re happy because we we have this nice formula that the time it takes is at most the sum over all sub problems of the relation time okay so i&#39;m referring to subproblems the number of them and the time it takes to evaluate this ignoring the recursive calls that&#39;s important this is the uh non-recursive part in the notes i call this non-recursive work so this formula gives us a way to bound the running time of one of these algorithms if we use memoization without memoization this is not true fibonacci took exponential time but if we add memoization we know that we only solve each sub problem once and so we just need to see for each one how much did it cost me to compute it assuming all the recursion work is free because that&#39;s already taken into account by the summation so in particular this summation is at most the number of sub-problems times the time per sub-problem which in this case is order n we could try to apply that analysis to merge sort because after all this is also a recursive algorithm it happens to not benefit from memoization but we could throw in memorization it wouldn&#39;t hurt us but if you think about the call graph here which is like s of zero n which calls s of n of zero n over two and s of n over two n and so on it has the same picture but there&#39;s actually no common substructure here you&#39;ll never see a repeated sub-problem because this range is completely disjoint from this range but you could throw in memorization and try to analyze in the same way and say well how many sub problems are there well looks like there&#39;s there&#39;s n choices for i and not quite n choices but in general it&#39;s at most n squared different choices in fact it&#39;s the triangular number sum of i equals 1 to n of i different possible choices for i and j but this is theta n squared sub problems which seems not so good and then how much time are we spending for per sub problem well to solve s of i j we have to merge about that many elements we know merge takes linear time and so this takes uh theta j minus i time to evaluate and so uh what we&#39;d like to do is sum over all the sub-problems of j minus i this is the uh not triangular number but the tetrahedral number i guess and so we end up that the running time is at most n cubed great um so it&#39;s true that n log n is less than or equal to n cubed but obviously not terribly useful this algorithm by the way we already know how to analyze it is indeed n log n and the running time turns out to be theta n log n so sometimes this is this equation is not what you want to use but often it&#39;s good enough and especially if you just want to get a polynomial upper bound and then you can try to optimize it later this will give you a polynomial upper bound as long as the number of subproblems is polynomial and the time per subproblem is polynomial and indeed n cubed is polynomial it&#39;s not a great polynomial but this is a an alternate way to analyze merge sort obviously don&#39;t do this for merge sort but it illustrates the technique good so far any questions all right uh let me remember where we are cool so the next thing i&#39;d like to do is uh show you one more algorithm that we&#39;ve already seen in this class that fits very nicely into this structure arguably is a dynamic program and that is uh dag shortest paths oh so just to close the loop here when i say dynamic programming i mean recursion with memoization i mean we take we we write a recursive piece of code which is like def f of some args um some you know sub-problem specification we check is the sub-problem uh in the memo table if so uh return memo of subproblem and otherwise check if it&#39;s a base case if and solve it if it&#39;s a base case and otherwise write the uh recurrence recurse via relation and set the memo table of the subproblem to be one of those things okay so this is the generic dynamic program and implicitly i&#39;m writing fibonacci in that way and all of the dynamic programs have this implicit structure where i start with a memo table which is empty and i always just check if i&#39;m in the memo table if i am i return it otherwise i compute according to this recursive relation by recursively calling f and that&#39;s it so this is every dp algorithm is going to have that structure and it&#39;s just using recursion and memorization together okay so now let&#39;s apply that technique to think about the dag shortest paths problem the problem was i give you a dag i give you a source vertex s single source shortest paths compute the shortest path weight from s to every vertex that&#39;s the goal of the problem and we saw a way to solve that which is dag relaxation i&#39;m going to show you a different way which turns out to be basically the same but upside down or flipped left to right depending which way you direct your edges so what are our sub problems well here actually they&#39;re kind of spelled out for us we want to compute delta of sv for all v so that is uh size of these sub-problems that turns out to be enough for this overall problem and the original problem we want to solve is all of the sub problems we solve all the sub problems we&#39;re done and then we have uh i think we wrote this at some point during the dag shortest paths lecture we have a recursive relation saying that the the shortest way to get from s to v is the minimum of the shortest path to get to some vertex u plus the weight of the edge from u to v why because if we look at a vertex v unless we started there we came from somewhere and so we can consider all of the possible choices for the previous vertex u and if you start at s and get to v you must go through one of them and so this is finding the best way among all the choices of you uh what&#39;s the best way to get to you and then take the edge from u to v for all edges uv and this is adjacency minus we don&#39;t usually think of that usually we look at adjacency plus the outgoing edges this is the incoming edges and so u is an incoming uv is an incoming edge into v okay if we take that minimum and of course the possible there there is no way to get to v and so i&#39;ll also throw infinity into this set take the min of that set that will give me the shortest path weight in an acyclic graph from s to v and great this is recursive right this was a sub problem these are sub problems which are smaller i guess there&#39;s no clear notion of smaller here except we already know the clear notion of smaller is the topological order of our dag because our graph is acyclic we know it has a topological order we know how to compute it with dfs and so that guarantees uh there&#39;s a topological order to compute these problems and in fact the the relationship between problems is exactly the given graph g in order to compute the shortest path weight from s to v i need to know the shortest pathway from s to all of the incoming vertices to v and so this is uh i guess in the call graph this vertex calls this vertex but i&#39;ll direct the edge this way to say that this vertex requires uh this vertex needs to be computed before this one and so then i can compute them in a topological order okay we have a base case which is delta of ss equals zero and the running time is again we can use this formula and say let&#39;s just sum over all the sub-problems of the non-recursive work in our recurrence relation and so it&#39;s computing this min if i gave you these deltas for free and i gave you these weights which we know from our weight data structure how long does it take to compute this min well however many things there are and how many numbers were were mining which is the size of the incoming adjacency list plus one for that infinity and so if you compute this sum sum of incoming edges to every vertex that&#39;s all the edges so this is v plus e okay so in fact this algorithm is morally the same algorithm is the one that we saw in the dag shortest path lecture which was computer topological order and process vertices in that order and relax edges going out from vertices so here uh so in in that algorithm we would have uh tried to relax this edge if if there&#39;s a better path to v and the first one certainly is better than infinity so the first one we relax uh indeed uh the next edge if this is a if this gave a better path from s to v then we would relax that edge and update the weight here and do the same here in the end we&#39;re just computing this min in the relaxation algorithm but doing it step by step in the in the relaxation algorithm tag relaxation we for each incoming edge to v we update d of v if it&#39;s better and so if you if you repeatedly update if you&#39;re better that ends up computing a min okay so this is the same algorithm just kind of flipped backwards uh a funny thing although we wrote down the topological order of the subproblem graph here is the topological order of g because the sub-problem graph is g the algorithm doesn&#39;t actually have to compute one it&#39;s doing it automatically for free if you think about this algorithm a generic dp algorithm which is check whether we&#39;re in a memo table if so return otherwise recurse or base case this actually is a depth for search through the sub-problem graph technically through the reverse of the subproblem graph if i draw an edge so from small to big so if i&#39;m just saying i orient the edges from my smaller sub problems to the ones that need it then i&#39;m actually definitely searching backwards in this graph because the bigger problem calls the smaller problem and the memo table is serving as the have i visited this vertex already check in dfs so this is actually a dfs algorithm plus we&#39;re doing some computation to actually solve the sub problems we care about so implicit in this algorithm we are doing a dfs and at the same time we&#39;re doing this shortest path computation uh in the finishing order of that dfs traversal because all the edges are backwards this is the same as the reverse finishing order if the graph is forwards so in the end we&#39;re computing a topological order because uh dynamic programming includes in it uh depth first search oh a lot of words but it&#39;s kind of cool that this framework just solves dag shortest paths without much work i mean we we did a lot of work in shorts paths to prove that this relation is true but once you know it&#39;s true the algorithm part is is pretty much free you just write down sort bot and you&#39;re done okay this brings us to in general at this point we have seen two examples of dynamic programming i guess technically merge sort you can think of as a dynamic program but it doesn&#39;t actually reuse anything so it&#39;s not interesting and indeed that gave us a really bad bound we&#39;ve definitely seen bag shortest paths and fibonacci numbers as two interesting examples and what the next remainder of this lecture and the next three lectures are going to be about is more and more examples of dynamic programming and how you can use it to solve increasingly general problems so far we&#39;ve just solved an easy problem and a problem we already knew how to solve let&#39;s go to a new problem which is bowling bowling is popular in boston this boston likes to play candlepin bowling which is a bit unusual uh today we&#39;re going to play an even more unusual bowling game one that i made up based on a bowling game that henry dudeny made up in 1908 so ancient bowling i might call it or i think linear bowling is what i might call it i&#39;ll just call it bowling here and now i&#39;m going to attempt to draw a bowling pin not bad that might get progressively worse so imagine n identical bowling pins please pretend these are identical and i have a ball which is approximately the same size as a bowling pin these bowling pins are pretty close together i should have left a little gap here and you&#39;re a really good bowler now unfortunately these bowling pins are on a line and you&#39;re bowling from way down at infinity so when you bowl um you can only hit one pin or two pins or zero pins but probably you want to hit some pins uh so if you pull straight at a pin you will just hit that one pin and if you bowl in the middle between two pins you will knock down that&#39;s a ball sorry you will knock down two pins okay this is your model of bowling model of computation now what makes this interesting is that the pins have values pin i has value yeah this is obviously a toy problem uh though this problem this type of bowling does go back to 1908 it was also a toy problem in that setting so each of these uh bowling pins has some number on it let&#39;s say one nine nine let me do a slightly more interesting example maybe another one here uh and a two and a five and a five something like this okay uh or maybe make a little more interesting let&#39;s put some negative numbers on here okay and the model uh so you&#39;re at the carnival bowling each pin has different potentially different values and the model is if you hit one pin i then you get vi points so that&#39;s straightforward to make it interesting when you hit two pins you get the product so if i hit two pins it&#39;s always i and i plus one for some i you get vi times vi plus one points this is the the game you&#39;re playing and it doesn&#39;t really matter that this is a product uh product is just some weird function that&#39;s hard to imagine if you stare at this long enough you should convince yourself that the optimal solution is probably to so for each of these numbers i could leave it singleton or pair it with its left neighbor or pair it with its right neighbor but the pairings can&#39;t overlap because once i hit a pin it&#39;s gone it&#39;s knocked over and it disappears so because of these nines which are very high value what i&#39;d probably like to do is hit both of them together so pair them up because 9 times 9 is 81 that&#39;s really big much better than hitting them individually or hitting 9 times 1 or 9 times 2. one and one is kind of funny because it&#39;s actually better to hit them individually that will give you two points whereas if i pair them up i only get one point two and minus five that seems bad negative ten points my goal is to maximize score do you have to hit all the pins let&#39;s say no you don&#39;t have to hit all the pins so i could skip the minus fives but in fact here uh because they&#39;re adjacent minus five times minus five is good that&#39;s 25 points so uh the optimal solution for this particular instance are to hit all the pins these positive uh these together these together if i added for example another pin of minus three here i would choose not to hit that pin good question so you just play until you are tired when you decide to stop playing how can i maximize your score there are many variations this game all of them basically any variation not literally every variation but many many variations of this problem can all be solved quickly with dynamic programming but let&#39;s solve this particular one okay um so now we&#39;re really in algorithmic design mode we need to think about sort bot and in particular we need to think about what would the subproblems be here and at this point we don&#39;t have a lot of of help so i should probably give you some tools if i want to solve a problem like this the input is a sequence of numbers right it&#39;s a sequence data structure maybe it&#39;s an array of numbers which is this v v array and let&#39;s see um a general tool for subproblem design which will cover most of the problems maybe all of the problems that we see in this class for dynamic programming here&#39;s a trick if your input is a sequence here&#39;s some good sub problems to consider uh we could do all prefixes so let&#39;s call the sequence x so we could do x prefix means up to a given i for all i we could do all the suffixes x from i onward for all i or we could do substrings which are the consecutive items from i to j i don&#39;t write subsequence here subsequence means you can emit items in the middle so substring you have to start at some position and do all the things up to j uh so these are nice easy to express in python notation and these are great because they&#39;re polynomial right if i have n things if the length of my sequence x is n then there are n sequences n prefixes technically n plus one so let&#39;s do theta n prefixes they&#39;re theta and suffixes and they&#39;re theta and squared substrings because there&#39;s n roughly n choices for i and j separately sorry subsequences good right i didn&#39;t write subsequences because in fact there are exponentially many subsequences right it&#39;s 2 to the n for every item i could choose it or not so i don&#39;t want to parametrize i don&#39;t want my sub problems to be sub sequences because that&#39;s guaranteed well then you&#39;re guaranteed to get an exponential number of sub-problems which is bad we&#39;d like to bound the number of sub-problems by a polynomial so these are three natural ways to get uh polynomial bounds now prefixes and suffixes are obviously better because there&#39;s fewer of them linear instead of quadratic and usually almost every problem you&#39;ll encounter prefixes and suffixes are equally good it doesn&#39;t really matter which one you choose so maybe you like to think of well we&#39;ll get to it&#39;s you just choose whichever is more comfortable for you but sometimes it&#39;s not enough and we&#39;ll have to go to substrings that won&#39;t be for another lecture or two okay today i claim that prefixes or suffixes are uh enough to solve the bowling problem so what we&#39;re going to do is think about i prefer suffixes usually because i like to work from left to right from the beginning to the end so we&#39;re going to think of a suffix of the bowling pins and so what is the sub problem on a suffix well a natural version is just to solve the original problem bowling how do i maximize my score if all i were given were these pins suppose the pins to the left of i didn&#39;t exist how would i maximize my score on the remaining pins or for this suffix given these four pins what would i do and there&#39;s some weird sub problems here right if i just gave you the last pin what would you do nothing that&#39;s clearly different from what i would do globally here but i claim if i can solve all suffixes i can solve my original problem because one of the suffixes is the whole sequence so let&#39;s do it sort bot for bowling so here&#39;s our dynamic program uh the sub problems are suffixes so um all right b of i is the maximum score we could get possible with our starting if we started a game with pins um i i plus one up to n minus one okay which is a suffix of the pins very important whenever you write a dynamic program to define what your sub-problems are don&#39;t just say how to compute them but first say what is the goal of the subproblem this is a common mistake to forget to state what you&#39;re trying to do so now i have to find b of i um now what is the original thing i&#39;m trying to solve i like to you can you can also put in sort by you could put the o earlier also then it&#39;s actually spell sort so why don&#39;t i do that for fun the original problem we&#39;re trying to solve is b of zero right because that is all of the pins the suffix starting at zero is everything so if we can solve that we&#39;re done next is r for relate this is the test of did i get the sub problems right is whether i can write a recurrence relation so let&#39;s try to do it we want to compute b of i so we have pin i here and then the remaining pins and the big idea here is to just think about the nice thing about suffixes is if i take off something from the beginning i still have a suffix remember my goal is to take this sub problem which is the suffix starting at i and reduce it to a smaller sub problem which means a smaller suffix so i&#39;d like to clip off a couple one or two items here and then the remaining problem will be one of my sub problems i&#39;ll be able to recursively call b of something smaller than i or sorry b of something larger than i will be a smaller subsequence because we&#39;re starting later okay so what could i do well the idea is to just look at pin eye and think what what could i do to pin i i could not hit it ever with a ball i could skip it that&#39;s one option what would be my score then well i if i skip pin i that leaves the remaining pins which is just a smaller suffix so that is uh b of i plus one i&#39;m going to write a max out here because i&#39;d like to maximize my score and one of the options is forget about pin i just solve the rest another option is i throw a ball and i exactly hit pin i that&#39;s a thing i could do and it would it would leave exactly the same remainder so another option is b of i plus 1 plus v i uh why would i prefer this over this well if v i is negative i&#39;d prefer this but if u is positive i&#39;d actually prefer this over that okay so you&#39;re going to figure out which is which is better just locally but then there&#39;s another thing i can do which is maybe i hit this pin in a pair with some other pin now there&#39;s no pin to the left of this one we&#39;re assuming we only have the suffix and so the only other thing i can do is throw a ball and hit i together with i plus one and then i get the product now what pins remain i plus two on still a suffix so if i remove one or two items of course i still get a suffix in this case b of i plus two and then the number of points that i add on are vi times vi plus one so this is a max of three things so how long does it take me to compute it i claim constant time if i don&#39;t count the time it takes to compute these other subproblems which are smaller because they are smaller suffixes further to the right uh then i&#39;m doing you know a couple of additions product max these are all nice numbers they will assume that they live in a w bit word um because they&#39;re only doing constant size products that&#39;s good uh so this takes constant constant non-recursive work how many sub-problems are but suffixes so it&#39;s a linear number of sub-problems and so the time i&#39;m going to end up needing is the number of sub-problems n times the non-recursive work i do per sub problem which is constant and so this is linear time great now i didn&#39;t finish sort bot so there&#39;s another t which is to make sure that there is a topological order and that is in decreasing i order or i might write that as a for loop for i equals n n minus 1. this is the order that i would compute uh my problems because the suffix starting at n is the empty suffix the suffix starting at zero that&#39;s the one i actually want to compute that&#39;s the final suffix i should be computing and then we have a b for base case which is that first case b of n equals uh zero because there&#39;s no pins so i don&#39;t get any points sad okay so this is it we just take these components plug them into this recursive memoized algorithm and we have a linear time algorithm i want to briefly mention a different way you could plug together those pieces which is called bottom up dp which is uh let&#39;s do it for this example so if i have um let&#39;s see let me start with the base case b of n equals zero but now it&#39;s an assignment and i&#39;m going to do the for loop from the topological order for i equals m n minus 1 to 0. now i&#39;m going to do the relation b of i equals max of b of i plus 1 and b of i plus uh 1 plus v i and v of i plus 2 plus v i v i plus 1. technically this only works if i is strictly less than n minus 1. so i should have an if i is less than n minus 1 for that last part because i can only do i can only hit two pins if there&#39;s at least two pins left and then return b of zero so what i just did is a transformation from this sort bot template into a non-recursive algorithm a for loop algorithm where i wrote my base case first then i did my topological order then i did my relation then at the end i did my base not base case the original problem and provided you can write your topological order as some for loops this is actually a great way to write down a dp as code if i were going to implement this algorithm i would write it this way because this is super fast no recursive calls just one for loop in fact this is almost a trivial algorithm it&#39;s amazing that this solves the bowling problem it&#39;s in some sense considering every possible strategy i could for bowling these pins what we&#39;re using is what we like to call local brute force where when we think about pin i we look at all of the possible things i could do to pin i here there&#39;s really only three options of what i could do now normally if i if i tried all the options for pin i and then all the options for i plus 1 and i plus 2 and so on that would be exponential it&#39;d be 3 times 3 times 3 that&#39;s bad but because i can reuse these sub problems it turns out to only be linear time it&#39;s almost like magic dp dp dp is essentially an idea of using local brute force and by defining a small number of sub problems up front and as long as i stay within those sub problems as long as i&#39;m always recursing into this polynomial space i end up only doing polynomial work even though i&#39;m in some sense exploring exponentially many options and it&#39;s it&#39;s because what i do for this pin doesn&#39;t depend too much to what i do to a pin much later and there&#39;s a lot of intuition going on here for what uh when dp works but we&#39;re going to see a lot more examples of that coming up and i just want to mention that the intuition for how to write a recurrence like this is to think about in the case of suffixes you always want to think about the first item or maybe the first couple items the case of prefixes you always think about the last item and for sub strings it&#39;s could be any item maybe in the middle if i remove an item from the middle of the substring i get two substrings so i can recurse here or in general what we want to do is identify some feature of the solution that if we knew that feature we would be done we would reduce to a smaller sub problem in this case we just say well what are the possible things i could do to the first pin there are three options if i knew which option it was i would be done i could recurse and do my addition now i don&#39;t know which thing i want to do so just try them all and take the max and if you&#39;re maximizing you take the max if you&#39;re minimizing you take them in sometimes you take an or or an and there might be some combination function for optimization problems where you&#39;re trying to maximize or minimize something like shortest paths we&#39;re trying to minimize we put them in here so usually it&#39;s min or max and this is extremely powerful uh all you need to do the hard part is this inspired design part where you say what do i need to know that would let me solve my problem if you can identify that and the number of choices for what you need to know is polynomial then you will be able to get a polynomial dynamic program that&#39;s the intuition we&#39;ll see a lot more examples in the next three lectures

Transcript for:Understanding Dynamic Programming Concepts

Transcript for:
Understanding Dynamic Programming Concepts