1 00:00:00,000 --> 00:00:02,875 Hey, so guess what? We just designed our first dynamic 2 00:00:02,875 --> 00:00:06,294 programming algorithm. That linear time algorithm for computing 3 00:00:06,294 --> 00:00:10,744 the max weight independence set in a path graph is indeed an instantiation of the 4 00:00:10,744 --> 00:00:14,651 general dynamic programming paradigm. Now I've deferred articulating the 5 00:00:14,651 --> 00:00:18,775 general principles of that paradigm until now because I think they are best 6 00:00:18,775 --> 00:00:22,899 understood through concrete examples. Now that we have one to relate them to, 7 00:00:22,899 --> 00:00:25,449 let me tell you about these guiding principles. 8 00:00:25,449 --> 00:00:28,380 We will in the coming lectures see many more examples. 9 00:00:35,120 --> 00:00:40,487 So the key that unlocks the potential of the dynamic programming paradigm for 10 00:00:40,487 --> 00:00:45,373 solving a problem is to identify a suitable collection of sub-problems. 11 00:00:45,373 --> 00:00:49,640 And these, sub-problems have to satisfy a number of properties. 12 00:00:49,640 --> 00:00:55,094 In our algorithm for computing max weight independent sets and path graphs, we had 13 00:00:55,094 --> 00:00:58,885 N plus one sub problems, one for each prefix of the graph. 14 00:00:58,885 --> 00:01:03,940 So formally, our Ithi sub problem in our algorithm, it was to compute the max 15 00:01:03,940 --> 00:01:09,461 weight independent set of G sub I, of the path graph consisting only of the first I 16 00:01:09,461 --> 00:01:14,339 vertices. So the first property that you want your 17 00:01:14,339 --> 00:01:17,397 collection of subproblems to possess is it shouldn't be too big. 18 00:01:17,397 --> 00:01:19,738 It shouldn't have too many different subproblems. 19 00:01:19,738 --> 00:01:23,131 The reason being is, in the best case scenario, you're going to be spending 20 00:01:23,131 --> 00:01:26,810 constant time solving each of those subproblems, so the number of subproblems 21 00:01:26,810 --> 00:01:29,534 is a lower bound than the running time of your algorithm. 22 00:01:29,534 --> 00:01:32,210 Now, in the Maximum Independent Set example, we did great. 23 00:01:32,210 --> 00:01:35,650 We had merely a linear number of subproblems, and we did indeed get away 24 00:01:35,650 --> 00:01:39,329 with a mere constant work for each of those subproblems, giving us our linear 25 00:01:39,329 --> 00:01:45,403 running time bound overall. The second property you want and this 26 00:01:45,403 --> 00:01:49,693 one's really the kicker, is there should be a notion of smaller subproblems and 27 00:01:49,693 --> 00:01:52,842 larger subproblems. In the context of independence sets of 28 00:01:52,842 --> 00:01:55,394 path graphs this was really easy to understand. 29 00:01:55,394 --> 00:01:59,630 The subproblems were prefixes of the original graph and the more vertices you 30 00:01:59,630 --> 00:02:03,268 had, the bigger the subproblem. So in general, in dynamic programming, 31 00:02:03,268 --> 00:02:07,395 you systematically solve all of the subproblems beginning with the smallest 32 00:02:07,395 --> 00:02:10,218 ones and moving on to larger and larger subproblems. 33 00:02:10,218 --> 00:02:14,020 And for this to work, it better be the case that, at a given subproblem. 34 00:02:14,020 --> 00:02:19,074 Given the solutions to all of the smaller sub problems it's easier to confer what 35 00:02:19,074 --> 00:02:21,725 the solution to the current sub problem is. 36 00:02:21,725 --> 00:02:26,224 That is solutions to previous sub problems are sufficient to quickly and 37 00:02:26,224 --> 00:02:29,800 correctly compute the solution to the current sub problem. 38 00:02:33,060 --> 00:02:37,167 The way this relationship between larger and smaller subproblems is usually 39 00:02:37,167 --> 00:02:41,438 expressed is via recurrence and it states what the optimal solution to a given 40 00:02:41,438 --> 00:02:45,546 subproblem is as a function of the optimal solutions to smaller subproblems. 41 00:02:45,546 --> 00:02:49,599 And this is exactly how things played out in our independent set algorithm. 42 00:02:49,599 --> 00:02:53,491 We did indeed have a recurrence. It just said, that the optimal value, the 43 00:02:53,491 --> 00:02:55,870 maxwood independence head value for G sub I. 44 00:02:55,870 --> 00:03:00,183 Was the better of two candidates. And we justified this using our thought 45 00:03:00,183 --> 00:03:02,961 experiment. Either you just inherit the maximum 46 00:03:02,961 --> 00:03:07,629 independence set value from the preceding sub problem from the I-1 sub problem. 47 00:03:07,629 --> 00:03:11,766 Or you take the optimal solution from two sub problems back from GI-2. 48 00:03:11,766 --> 00:03:14,602 And you extend it by the current vertex, V sub I. 49 00:03:14,602 --> 00:03:19,152 That is, you add the [INAUDIBLE] vertices weight to the weight of the optimal 50 00:03:19,152 --> 00:03:24,714 solution from two sub problems back. So this is a pattern we're going to see 51 00:03:24,714 --> 00:03:28,310 over and over again. We'll define subproblems for various 52 00:03:28,310 --> 00:03:32,221 computational problems. And we'll use re, recurrence to express 53 00:03:32,221 --> 00:03:37,268 how the optimal solution of a given subproblem depends only on the solutions 54 00:03:37,268 --> 00:03:42,018 to smaller subproblems. So just like in our independent set 55 00:03:42,018 --> 00:03:45,916 example once you have such a recurrence it naturally leads to a table filling 56 00:03:45,916 --> 00:03:49,913 algorithm where each entry in your table corresponds to the optimal solution to 57 00:03:49,913 --> 00:03:53,661 one sub-problem and you use your recurrence to just fill it in moving from 58 00:03:53,661 --> 00:03:55,860 the smaller sub-problems to the larger ones. 59 00:03:57,380 --> 00:04:00,710 So the third property, you probably won't have to worry about much. 60 00:04:00,710 --> 00:04:04,595 Usually this just takes care of itself. But needless to say, after you've done 61 00:04:04,595 --> 00:04:08,329 the work of solving all of your sub problems, you better be able to answer 62 00:04:08,329 --> 00:04:12,242 the original question. This property is usually automatically 63 00:04:12,242 --> 00:04:16,873 satisfied because in most cases, not all, but in most cases the original problem is 64 00:04:16,873 --> 00:04:19,471 simply the biggest of all of your subproblems. 65 00:04:19,471 --> 00:04:23,141 Notice this is exactly how things worked in the independent sets. 66 00:04:23,141 --> 00:04:26,473 Our biggest subproblem G sub N was just the original graph. 67 00:04:26,473 --> 00:04:28,732 So once we fill up the whole table, boom. 68 00:04:28,732 --> 00:04:33,420 Waiting for us in the final entry was the desired solution to the original problem. 69 00:04:35,820 --> 00:04:39,052 So I realize, you know this is a little abstract at the moment. 70 00:04:39,052 --> 00:04:43,066 We've only have one concrete example to relate to these abstract concepts. 71 00:04:43,066 --> 00:04:47,080 I encourage you to revisit this again after we see more examples and we will 72 00:04:47,080 --> 00:04:52,188 see many more examples. Something that all of the forthcoming 73 00:04:52,188 --> 00:04:57,065 examples should make clear is the power and flexibility of a dynamic programming 74 00:04:57,065 --> 00:05:00,076 paradigm. This is really just a technique that you 75 00:05:00,076 --> 00:05:03,852 have got to know. Now when you're trying to devise your own 76 00:05:03,852 --> 00:05:07,799 dynamic programming algorithms, the key, the heart of the matter is to figure out 77 00:05:07,799 --> 00:05:11,204 what the right sub problems are. If you nail the sub problems usually 78 00:05:11,204 --> 00:05:14,115 everything else falls into place in a fairly formulaic way. 79 00:05:14,115 --> 00:05:18,062 Now if you've got a black belt in dynamic programming you might be able to just 80 00:05:18,062 --> 00:05:20,789 stare at a problem. And intuitively know what the right 81 00:05:20,789 --> 00:05:24,168 collection of subproblems are. And then, boom, you're off to the races. 82 00:05:24,168 --> 00:05:27,250 But, of course, you know? For white belts in dynamic programming, 83 00:05:27,250 --> 00:05:29,387 there's still a lot of training to be done. 84 00:05:29,387 --> 00:05:33,363 So rather, in the forthcoming examples. Rather than just plucking the subproblems 85 00:05:33,363 --> 00:05:35,848 from the sky. We're going to go through the same kind 86 00:05:35,848 --> 00:05:38,034 of process that we did for independent sets. 87 00:05:38,034 --> 00:05:41,961 And try to figure out how you would ever come up with these subproblems in the 88 00:05:41,961 --> 00:05:44,346 first place? By reasoning about the structure of 89 00:05:44,346 --> 00:05:47,179 optimal solutions. That's a process you should be able to 90 00:05:47,179 --> 00:05:51,205 mimic in your own attempts at applying this paradigm to problems that come up in 91 00:05:51,205 --> 00:06:00,900 your own projects. So, perhaps you were hoping that once you 92 00:06:00,900 --> 00:06:05,642 saw the ingredients of dynamic programming, all would become clearer why 93 00:06:05,642 --> 00:06:09,792 on earth it's called dynamic programming and probably it's not. 94 00:06:09,792 --> 00:06:12,411 So, this is an anachronistic use of the word 95 00:06:12,411 --> 00:06:14,833 programming. It doesn't mean coding in the way I'm 96 00:06:14,833 --> 00:06:18,562 sure almost all of you think of it. It's the same anachronism in phrases like 97 00:06:18,562 --> 00:06:22,243 mathematical or linear programming. It more refers to a planning process, but 98 00:06:22,243 --> 00:06:25,682 you know for the full story let's go ahead and turn to Richard Bellman 99 00:06:25,682 --> 00:06:28,103 himself. He's more or less the inventor of dynamic 100 00:06:28,103 --> 00:06:31,881 programming, you will see his Bellman-Ford Algorithm a little bit later 101 00:06:31,881 --> 00:06:34,254 in the course. So he answers this question in his 102 00:06:34,254 --> 00:06:37,984 autobiography and he's says, he talks about when he invented it in the 1950's 103 00:06:37,984 --> 00:06:41,084 and he says those were not good years for mathematical research. 104 00:06:41,084 --> 00:06:45,190 He was working at a place called Rand, he says we had a very interesting gentleman 105 00:06:45,190 --> 00:06:48,463 in Washington named Wilson who was the Secretary of Defense. 106 00:06:48,463 --> 00:06:52,390 And he actually had a pathological fear and hatred of the word research. 107 00:06:52,390 --> 00:06:55,336 I'm not using the term lightly. I'm using it precisely. 108 00:06:55,336 --> 00:06:59,482 His face would suffuse, he would turn red, and he would get violent if people 109 00:06:59,482 --> 00:07:03,693 used the term research in his presence. You can imagine how we felt then about 110 00:07:03,693 --> 00:07:07,004 the term mathematical. So the Rand Corporation was employed by 111 00:07:07,004 --> 00:07:10,583 the Air Force, and the Air Force had Wilson as its boss, essentially. 112 00:07:10,583 --> 00:07:14,802 Hence, I felt I had to do something to shield Wilson and the Air Force from the 113 00:07:14,802 --> 00:07:18,488 fact that I was really doing mathematics inside the Rand Corporation. 114 00:07:18,488 --> 00:07:22,494 What title, what name could I choose? In the first place I was interested in 115 00:07:22,494 --> 00:07:26,072 planning and decision making, but planning, it's not a good word for 116 00:07:26,072 --> 00:07:28,850 various reasons. I decided therefore to use the word, 117 00:07:28,850 --> 00:07:31,946 Programming. Dynamic has a very interesting property 118 00:07:31,946 --> 00:07:36,352 as an adjective, in that it's poss, impossible to use the word dynamic in a 119 00:07:36,352 --> 00:07:39,627 pejorative sense. Try thinking of some combination that 120 00:07:39,627 --> 00:07:42,187 will possibly give it a pejorative meaning. 121 00:07:42,187 --> 00:07:46,044 It's impossible. Thus I thought dynamic programming was a 122 00:07:46,044 --> 00:07:49,587 good name. It was something not even a congressman 123 00:07:49,587 --> 00:07:53,980 could object to so I used it as an umbrella for my activities.