in this lecture, we're going to talk about a very important algorithm development technique called dynamic programming. Alright, so, dynamic programming is a very important class and a lot of algorithms, for example, we will learn about shortest path algorithms and graphs, algorithms in in computational biology. So these are usually take the flavor of dynamic programming algorithms, okay? So what is dynamic programming? So, dynamic programming, the programming and dynamic programming comes from a earlier word of programming, which means it stands for more scheduling or making decisions. All right? And dynamic programming as discipline was formulated in the early 40s and the 50's for solving a class of what are called optimization problems. All right? So, let me give you an example of an optimization problem that you will typically solve using dynamic programming. So, the optimization problem is like this, so, let's say you are a company, That sells rods, okay? So you're selling straight rods of certain length, okay? And and let's say steel rods of certain length. All right? And let's say there is a price table, so length of the road, And the price that you get for that rod. Let's say if you sell roads of length 3, you can get $1.80 for each rod, if you sell rods of length 4, you get $2.00 for each rod, for example. All right, and let's say that you're manufacturing rods that are of standard length capital L. So let's say L=10, okay? So you're manufacturing 10m rods, okay? But you can only sell 3m or 4m on the market, which means that you have to cut these rods somehow. All right? So, the question is how do I optimally cut, 10m rods into 3 or 4m rods, And this is the most important keyword, you're always maximizing or minimizing, in this case you are maximizing. What are you maximizing? Your maximizing the price that you get. So for example, there are many options that you have when given a 10m road on how you would cut it into 3m or 4me roads. So for example, here is some of the decisions you can make and the price you get for the payoff, You get for those decisions. So for example, let's take, you have 4m+4m and let me just remark that if you do this, then 2m goes to waste. Okay, so 2m will go to waste, but you have a 4m+4m rod. How much do you get for that? Well, I'll get $4. All right? How about 3m rods? And then here 1m goes to waste, How much price would you get for that? Well, you would get $1.80 cents, so you would get $5.40. How about, Two 3m rods, and one 4m rod? No waste, how much do you get? You get 360+2, you would get $5.60. All right? $5.60. Alright, so here we have three possible choices, let's say C1, C2 C3, you have more choices actually. But let's not worry about that, all right. So, I have given you three possible choices, and among these choices, I would definitely prefer the third choice because this is among the choices I've examined maximizing the bill. All right. So, the goal here is like this, have given a problem, I have given you some some choices you could make, and now the question is, what's the optimal choice? What's the optimal choice? What is the optimal choice, + how much payoff does it give me? Okay? How much payoff does it give me? Alright, is that good? So this is going to be the objective of my problem. And let's call this the rod cutting problem. All right, so one of the main ideas behind dynamic programming and dynamic programming is based on one very key idea. And this key idea is called the optimal sub structure, okay? And this is something that we will really have to understand through the course of this week. All right? Optimal, Sub structure, okay? And whenever you see optimal substructure in a problem, okay? And we'll have to train ourselves to see it, it's not a natural inborn talent to see optimal substructure in problems, okay? But once you see enough examples of dynamic programming and once you make conscious note of the optimal substructure in each of the examples you observe, let's say this week, you get to observe 5 or 6 examples. And in each of the examples, let's say you make note of the optimal sub structure, then it will be an idea that sinks into you and then it's much easier for you than to understand optimal substructure. But let me explain in the context of this road cutting problem. So, an optimal substructure, what do we do? So, first of all, we have a sequence of decisions to make. So we have a sequence of decisions. Not just one decision, so even though I'm saying you can view this as making one decision 4+4 or 3+3+3 or 3+3+4. Let me view it as a sequence of decisions, what does it mean? So, it means that given a rod of 10cm, I could make my first decision better to make a 3m, or I think I'm working with meters, so let me work with 10m. So, given a rod of 10m, I could make a 3m cut or 4m cut as my very first cut. Okay, 3m or my 4m. This is going to be my very first cut. All right? If I went with choice one, if I went with 1 here, then my remaining rod is 7m, and I have earned myself for making this choice, I have earned myself 180 so far. All right? If I made a 4m cut, then my remaining rod is 6m and I have made $2 so far, all right? So, this gives me the first decision I made 3m of 4m. And let's say I commit to this decision. Let's say I come into this decision. For some reason, I come into this decision. What do I have Left? I have left 7m worth of rod and I have left $1.80 worth of price or profit or revenue, all right? It's revenue, not profit here. All right now, what do I do? So, what I am left over is the same problem as the original, But with different data. What's this different data and the same thing here. Same problem as original, But with different data. What is this different data? Well, the only data that's different is the prices still remain the same in this problem. But the only thing that's different is now I am left with 7m worth of rod or I am left with 6m worth of rod. And now suppose I do what is the best? So, I do the best decision for the 6m. I do the best decision for the 7m. I do whatever is best for the 7m, okay? And I can compare which one gives me better pay off. So, for example, what's the best answer? When you are given 7m of rod? Well when you're given 7m of rod, you just cut it into 3m plus 4m. And that gives me $3.80. So, the best here gives me $3.80. If you're given 6m of rod, it's very easy. Cut it into 3m and 3m. So, that the best here is $3.60, okay? And now, since I know that I have to do the Best for the 6m and I get 2 dollars already. If I go down this branch, if I go down the 4m branch, I know I will get $5.60, okay? If I go down the 3m branch, the best I will get is 380 plus 180. I'll also get $5.60. So, in this lucky instance both the 3m and the 4m give me the same amount which is $5 and 60 cents, okay? But let us say we went with the 4m, so we went to the 4m. So, we conclude that the Best decision is $5.60. That's the best payoff I get. And the payoff is obtained by committing to first cutting the road to 4m and then recursively. So, recursively solving the same problem for a 6 meter or okay, very few finish solving it. Recursively you would find out that the best answer was to cut it into two rods of 3m, giving you a payoff of $3, 60 cents combined with $2 gives you $5.60. All right, so we are now ready to talk more about dynamic programming and optimal sub structure. So, optimal sub structure entails that there are two things that we need to do, okay? So, in the context of a problem like this, an optimization problem, what is optimal sub structure? Optimal substructure says the following. So, first of all, I have to make a sequence of decisions. Not just a single decision. I have to make a sequence of decisions. Number one, do I have to make a sequence of decisions in this broad cutting problem? Yes, I have to make a sequence of decisions. Number two, If I come into one. So, given what, where I am right now in solving the problem, if I commit to a decision, okay? If I come into making one decision right now, then the remaining left. Our problem is an instance of the original problem. This is super important. So, here, if I have 10 m of rod, my decisions are either I can cut 3m off or I can cut 4m off. Well, let me cut 4m off. I'm left with 6m of rod. Well, there's $2 of payoff for that, which I will consider, but I'm left at 6m and now I have to solve a sub problem for 6m worth of front. All right, and the last and the final and the most important point as well is that the final solution involves solving step to this step. The sub problem in step to optimally and combining that or did you know, decision? Let me illustrate this, all right. So, what does it mean if I solved a 6m problem optimally? Well, the optimal solution for this was 3m, 3m. And then if I attack this original decision of cutting 4m rod, that's the optimal for the original problem and that contains the optimal for the sub problems, all right? So, I haven't shown you yet how to solve the road cutting problem. But what I have shown you is that I have defined this notion of an optimal sub structure. What does it mean? That means three things. One is that the decisions you're making are sequential. Which means you're making one decision after another, after another, after another after another. So, you're making a sequence of decisions. If I commit to a decision at the current stage where I am right now, if I come into a decision what is left over is an instance of the original problem. I have to resolve an instance of the original problem maybe with smaller data. And finally, the final solution involves taking this little sub problem solving it as an instance of the original problem and combining the solution that I get for the sub problem with the decision I made to get to that sub problem. If I combine them just like here, 3m and 3m is the answer to the sub problem. 4m is the decision I made to get to that sub problem. If I get to that, then the optimal solution looks like that, okay? And if if a problem establishes these three, it's called having the optimal substructure property. All right. So once we have the optimal substructure property, you should think about dynamic programming. In fact, a lot of times when you have to make a sequence of decisions, you have to think about dynamic programming and then you make a test whether the decisions can be sequenced in a way that 2 and 3 hold. And more often than not they will hold and you can go ahead and start to use dynamic programming. So now I'm going to talk about how do we make a dynamic programming algorithm? Once we have convinced ourselves that the problem has optimal substructure, okay? I'll talk about that coming up. So now we will talk about more about the rod cutting problem. [COUGH] So you have a rod of size L. And you have a sequence of decisions you could make L1 which is the size of a rod you could sell for price P1. L2 is the size you could sell for price P2. And let's call it L sub N, you could sell for price P7. So let's call this the price table. Okay. Now, my goal is to cut this rod L into some number of L1 rods plus some number of L2 rods plus some number of Ln rods plus some. Okay? Where the profit I make or the revenue to be more precise is n1p1 plus n sub n p [INAUDIBLE]. All right. So this is going to be something that I'm going to maximize revenue. It's very important to know the difference between revenue and profit. All right. So now you have the inputs to the problem RL, the total size and the price table. All right. And the output, you have to say, what's the maximum revenue? And how do I cut the rod to obtain maximum revenue? So what is max revenue Attainable And as a follow on to that, how do I attain it in some sense? What sequence of decisions do I make to obtain? Okay, so in dynamic programming, there are many steps to solve this problem. So first step is identify. Okay, identify. So let me write down the steps here. First step is, identify optimal substructure We did in the previous discussion and the optimal substructure was like this. So if I had a long rod of lengthy L. Okay, if I had a rod of length L I could commit to one of n decisions. L1 through Ln. So those are the decisions I could commit to right now. Okay. And if I committed to L1, I make an instantaneous revenue of P1 plus the sub problem I'm left with is a rod of size L-L1. Okay. If I committed to Ln, I commit to Pn. And what is a sub problem I'm left with, a rod of size L-Ln. So I better solve and find the answer for this sub problem. So now we have identified the optimal substructure. I hope it's clear how we've identified the optimal substructure. It's a sequence of decisions. So you make one decision right now and that allows you to identify the optimal substructure. Okay, so now I'm going to focus just on the first part of this problem. What is the maximum revenue attainable? So what's the maximum revenue attainable? And once I figure out what's the maximum revenue attainable, I promise we'll get to this question of how do we attain it? All right. So leave Question 2 aside for now and then let's talk about the Question 1, what is the maximum revenue attainable? And so that leads us to the second step of dynamic programming, which is right down a reference For the optimal value. Okay? This is very important. You write down a for the optimal value, not for the sequence of decisions you get for the optimal value. What will happen? And I promise you will see this in a second is once I get the optimal value, the sequence of decisions to get to the optimal value will also be made for me. All right. So let me write down just a reference for the optimal value. So in this case let me call this optimal value function max revenue. Okay. I'm not going to write down revenue, R-E-V-E-N-U-E. I hope you can fill that out. All right. What are the inputs to it? The inputs to it? Are the length of the rod, all right? That's it. That's all I need to know. Okay, the price table, I'll keep it on the side. If you wish I could keep it as an input, but I'll just keep the price table on the side. So the maximum revenue, just takes us an input the length of the rod L. All right? Now, what does this look like? So it looks like this, so maximum revenue of L is going to be, So first of all, if L equals equals zero. Okay? So if a rod has length zero then max revenue of L is Is going to be zero. I can get nothing out of it. If I have nothing, I can get nothing out of it. Another point is if L is less than zero, if a rod goes to negative length, the max revenue Should be very bad. Okay, because negative length rods do not exist in physics, so I should not be giving you revenue for negative length rod. In other words, it may be the case that instead of me selling you a rod, I owe someone a rod and that's not allowed in this problem. So I'm going to say max revenue of capital L is minus infinity, and let me put a note to revisit this. So this is the best case. All right. So what is going to be the the remaining stuff? So the remaining stuff is going to be like this. Right? So max revenue of L, what are the decisions I can make? So the decisions I can make are, it's going to be max of, Victoria is going to give me the best option of max revenue of L-L1. So let me choose the first option and add P1 to the problem. Max of L-L2 And, let me say 0, and let me explain what decisions give me this. So this decision says, So first decision is make a cut of size L1. Second decision is coming to a cut of size L2. And the last decision is coming to a cut, Size L sub N, okay? And then I put in a 0 here. You might be wondering why did I have to put in a 0 here. Well, the 0 is also a decision which says just waste, okay? So this is a decision where I simply decide just to waste, The rod, which means I get no revenue. So if I do cut the rod and just throw it away as waste, I get no revenue and that's a decision as well, okay? So here we have all the possible decisions I can make. L1 through Ln, and one of the decisions I didn't talk about, which is waste, in which case I immediately get no revenue, I'm done, all right. So now you see how the optimal sub structure is reflected in this recurrence. So optimal sub structure, Okay? Optimal substructure is reflected in this recurrence. How is it reflected? It says well, to get the maximum revenue for a rod of size L, let me try all the options I have given to me, which is cut it for size L1 for L2, L3, L4, Ln or just waste the rod. Which was a decision I should have written in this table, but it's kind of implicit in the problem, waste 0, all right? So I get no money for wasting. All right, so just waste the rod and you get 0. So these are all the decisions I'm allowed to make, if I make the decision 1, then I make an instantaneous profit of P1, I make an instantaneous profit of P1, and the leftover rod has size L- L1. Now, how do I find out what's the maximum revenue for leftover rod of size L- L1? We'll solve the same problem, max revenue of L- L1, and magically hopefully that returns the maximum revenue if I had a lot of size L- L1 and tack on P1 and then you get the maximum revenue for L. And whichever of these options provides me the best answer, is going to be the best answer for the original problem, all right? So here is the recurrence, okay? And I can actually implement this recurrence, so I'm not going to do this for other cases, but just let me write down and convince you that well, this is actually it, almost it. We have solved the problem, but what you will find out is if I just implemented this recurrence it's going to be really, really bad. So the fine maximum revenue of L to be what? To be, first let me do the base cases, if L equals equals 0, return 0, if L less than 0 return minus infinity, okay? And I'll explain to you how this minus infinity comes in a second, all right? What else? If L less than 0 and then otherwise, we have to just do each of these options. So it's going to be for Ri, Pi in my price table, I'm doing it and python like notation, compute max revenue equals max of max revenue, okay? Coma P sub I plus max Rev of L- L Li. And then let me give it a different name, let me call it, Max so far. And initialize max so far at the beginning to be 0. Why is that? Because I'm allowed to say it's marks of 0 comma, so I'll initialize it 0, and this 4 loop, implements this these series of max the 0 is the initial value, okay? And return, Max so far. That's the preference 4 max revenue. Now the problem is, I invite you to run this recurrence, what you will find out is that this recurrence is going to be really, really bad, okay? So we'll have to do something about how to speed this recurrence up. So if you just implement this recurrence, [COUGH] it solves this first problem. What is the max revenue attainable? You do solve it, but it's going to be really, really bad, in terms of running time because each max revenue of L is going to come up with so many different sub problems of max revenue, L. And one thing I'll convince you is that you're going to do a lot of repeated work. So you're going to do a lot of, especially in this step, we're going to do a lot of repeated work. And let me convince you that you're going to do a lot of repeated work coming right up, all right? By examining this recurrence slightly in more detail.
