1 00:00:00,000 --> 00:00:03,756 So the time has arrived to begin our study of dynamic programming. 2 00:00:03,756 --> 00:00:06,430 So this is a general algorithm design paradigm. 3 00:00:06,430 --> 00:00:10,926 As I mentioned at the beginning of the course, it has a number of justly famous 4 00:00:10,926 --> 00:00:13,715 applications. However, I'm not going to tell you just 5 00:00:13,715 --> 00:00:18,154 yet what it is that makes an algorithm dynamic programming. Rather, our plan is, 6 00:00:18,154 --> 00:00:22,707 over the next few videos, to develop from scratch an algorithm for a non trivial, 7 00:00:22,707 --> 00:00:26,861 concrete computational problem. The problem is finding the maximum weight 8 00:00:26,861 --> 00:00:31,020 independent set and a path graph. This concrete problem is going to force 9 00:00:31,020 --> 00:00:35,459 us to develop a number of new ideas. And, once we've finished solving the 10 00:00:35,459 --> 00:00:39,500 problem, at that point, we'll zoom out, and I'll point out what are the 11 00:00:39,500 --> 00:00:43,241 characteris-, characteristics of our solution which make it a dynamic 12 00:00:43,241 --> 00:00:46,597 programming algorithm. Then, armed with both a sort of formula 13 00:00:46,597 --> 00:00:50,558 for developing the dynamic programming algorithms, as well as a concrete 14 00:00:50,558 --> 00:00:54,519 instantiation, we'll move onto a number of further, and in general harder 15 00:00:54,519 --> 00:00:58,316 applications of the paradigm. Indeed, even more than usual, the dynamic 16 00:00:58,316 --> 00:01:00,901 programming paradigm takes practice to perfect. 17 00:01:00,901 --> 00:01:05,083 In my experience, students find it counterintuitive at first, and they often 18 00:01:05,083 --> 00:01:09,099 struggle to apply the paradigm to problems that they haven's seen before. 19 00:01:09,099 --> 00:01:12,748 But here's the good news, dynamic programming is relatively formulaic, 20 00:01:12,748 --> 00:01:16,590 certainly more so than our recent study of greedy algorithms, and it's something 21 00:01:16,590 --> 00:01:19,760 that you can get a hang of. So with sufficient practice, and that's 22 00:01:19,760 --> 00:01:23,411 exactly what I'll be giving you in the next couple of weeks, you should find 23 00:01:23,411 --> 00:01:28,531 yourself with a powerful and quite widely applicable new tool in your programmer 24 00:01:28,531 --> 00:01:32,028 tool box. So let me introduce you to the concave, 25 00:01:32,028 --> 00:01:35,336 concrete problem we're going to study over the next few videos. 26 00:01:35,336 --> 00:01:38,420 It's a graph problem but a very simple graph problem. 27 00:01:38,420 --> 00:01:42,702 In fact, we're going to restrict our attention merely to path graphs. 28 00:01:42,702 --> 00:01:47,511 That's graphs that consist solely of a path on some number n of vertices. 29 00:01:47,511 --> 00:01:52,517 The only other part of the input is a single non-negative number per vertex. 30 00:01:52,517 --> 00:01:57,301 We're going to call these weights. For example here's a path graph on four 31 00:01:57,301 --> 00:02:02,236 vertices, and let's give the vertices the weights one, four, five, and four. 32 00:02:02,236 --> 00:02:07,719 The responsibility of the algorithm is going to be to output an independent set. 33 00:02:07,719 --> 00:02:12,928 What that means is a subset of the graph's vertices, so that no two vertices 34 00:02:12,928 --> 00:02:16,629 are adjacent. So in the context of a simple path graph, 35 00:02:16,629 --> 00:02:21,563 it just means you gotta return some of the vertices and always avoiding 36 00:02:21,563 --> 00:02:26,782 consecutive pairs of vertices. So when you have a path of four vertices, 37 00:02:26,782 --> 00:02:29,969 examples of independent sets include the empty set, 38 00:02:29,969 --> 00:02:32,531 any single vertex, vertices one and three, 39 00:02:32,531 --> 00:02:35,531 vertices two and four, and vertices one and four. 40 00:02:35,531 --> 00:02:39,031 You could not, for example, return vertices two and three. 41 00:02:39,031 --> 00:02:41,906 Because those were adjacent. That is forbidden. 42 00:02:41,906 --> 00:02:45,843 Now, to make this interesting, we're going to want just, not any old 43 00:02:45,843 --> 00:02:49,342 independent set, but the one whose sum of vertex weights 44 00:02:49,342 --> 00:02:53,280 is as large as possible. That's the max weight independence set 45 00:02:53,280 --> 00:02:56,317 problem. So what I'm going to do next is use this 46 00:02:56,317 --> 00:03:00,052 concrete problem as an opportunity to review the various algorithm design 47 00:03:00,052 --> 00:03:03,836 paradigms that we've seen so far. Along the way we'll see that none of them 48 00:03:03,836 --> 00:03:07,874 actually work very well for this problem. And that's going to motivate us to devise 49 00:03:07,874 --> 00:03:10,599 a new approach, and that approach is going to turn out to 50 00:03:10,599 --> 00:03:12,205 be dynamic programming. . 51 00:03:12,205 --> 00:03:15,713 So there's always our standard punching bag, brute force search. 52 00:03:15,713 --> 00:03:20,167 This would entail iterating through all of the independent sets and remembering 53 00:03:20,167 --> 00:03:24,399 the one with maximum total weights. Of course it's correct, no question about 54 00:03:24,399 --> 00:03:27,406 that, but as usual this would require exponential time. 55 00:03:27,406 --> 00:03:31,805 Even in just a path graph, the number of independent sets is exponential in the 56 00:03:31,805 --> 00:03:33,420 number of vertices, n. . 57 00:03:35,120 --> 00:03:37,701 So what other algorithm design paradigms do we know? 58 00:03:37,701 --> 00:03:41,475 Well we just finished a big segment on greedy algorithms, we could certainly 59 00:03:41,475 --> 00:03:44,305 think about that. You know, pretty much most problems it's 60 00:03:44,305 --> 00:03:47,780 easy to propose greedy algorithms, and this one's no exception . 61 00:03:47,780 --> 00:03:51,554 I think the most natural greedy algorithm you might try to use to compute a 62 00:03:51,554 --> 00:03:55,017 maximally independent set would be well. What's the myopic decision? 63 00:03:55,017 --> 00:03:57,424 Well, you want to get as much weight overall. 64 00:03:57,424 --> 00:04:01,691 So, in each step, you want to just pick the vertex with the highest weight that 65 00:04:01,691 --> 00:04:05,247 you haven't already chosen. Now, of course you have to worry about 66 00:04:05,247 --> 00:04:07,928 feasibility. Remember, we're not allowed to output 67 00:04:07,928 --> 00:04:11,539 adjacent or consecutive vertices. So, if any vertex is ruled out by 68 00:04:11,539 --> 00:04:14,548 adjacency, we ignore it. And amongst those that preserve 69 00:04:14,548 --> 00:04:18,050 feasibility, we include the highest weight one in our set so far. 70 00:04:18,050 --> 00:04:22,475 Well, let me redraw the four node path graph we had in the last slide and let me 71 00:04:22,475 --> 00:04:25,130 ask you. What would this greedy algorithm compute 72 00:04:25,130 --> 00:04:29,335 on the four node path, and how does that compare to the optimal solution, the 73 00:04:29,335 --> 00:04:31,880 independent set with the maximum total weight? 74 00:04:35,260 --> 00:04:37,913 So the correct answer is the second one. Let's see why. 75 00:04:37,913 --> 00:04:41,352 So let's start with the optimal solution, the maximum independence set. 76 00:04:41,352 --> 00:04:45,233 Remember independence sets are forbidden from choosing adjacent or consecutive 77 00:04:45,233 --> 00:04:47,494 vertices. so in this case the only sensible 78 00:04:47,494 --> 00:04:51,326 solutions to consider are the first and third vertex, the second and fourth or 79 00:04:51,326 --> 00:04:54,127 the first and fourth. Of these, the best is the second and 80 00:04:54,127 --> 00:04:57,222 fourth for a total of eight. So what about the greedy algorithm? 81 00:04:57,222 --> 00:05:01,103 Well, you know, we just had this period of time where we got really spoiled with 82 00:05:01,103 --> 00:05:04,543 the success of greedy algorithms. especially the minimum span entry 83 00:05:04,543 --> 00:05:06,803 problem. But let me remind you, you know, greedy 84 00:05:06,803 --> 00:05:09,260 algorithms, you know, they're often good heuristics. 85 00:05:09,260 --> 00:05:11,348 They're often not guaranteed to be correct. 86 00:05:11,348 --> 00:05:15,282 And so I'm happy to have this opportunity to quickly remind you again, of that 87 00:05:15,282 --> 00:05:18,537 drawback of greedy algorithms. They're quite frequently not correct. 88 00:05:18,537 --> 00:05:21,742 So this is another such case, so what will the greedy algorithm do? 89 00:05:21,742 --> 00:05:24,511 Well, it begins by picking the max weight vertex over all. 90 00:05:24,511 --> 00:05:26,745 So that would be this vertex with weight five. 91 00:05:26,745 --> 00:05:30,631 That unfortunately blocks the algorithm from picking either of the two vertices 92 00:05:30,631 --> 00:05:33,642 that has weight four. The only remaining option that preserves 93 00:05:33,642 --> 00:05:36,506 feasibility is to pick. The vertex of weight one. 94 00:05:36,506 --> 00:05:40,280 So that gives us an indepenedent set of weight six. 95 00:05:40,280 --> 00:05:44,399 So this greedy algorithm is not correct. You could of course try to devise other 96 00:05:44,399 --> 00:05:48,466 types of algorithms, but I don't know of any greedy approach that will actually 97 00:05:48,466 --> 00:05:52,025 solve this problem optimally. So that's a bummer, but we still haven't 98 00:05:52,025 --> 00:05:56,363 exhausted our algorithm design paradigms. remember, you know, we learned this quite 99 00:05:56,363 --> 00:06:00,080 powerful divide and conquer approach early on in part one of this class. 100 00:06:00,080 --> 00:06:02,611 And you know, it seems like it could work here. 101 00:06:02,611 --> 00:06:06,225 We had all these successful applications where the input was an array. 102 00:06:06,225 --> 00:06:09,840 We broke it into two halves. We were cursed on both sides and combined 103 00:06:09,840 --> 00:06:12,319 the results. And here, you know, path graphs don't 104 00:06:12,319 --> 00:06:14,539 look so different than an array of numbers. 105 00:06:14,539 --> 00:06:18,515 So the obvious approach for divide and conquer is to break the path into two 106 00:06:18,515 --> 00:06:20,890 paths, each of half the length of the original, 107 00:06:20,890 --> 00:06:25,498 recursively compute a maximum weighted independent set of each, and then somehow 108 00:06:25,498 --> 00:06:28,738 combine the results. With the issues with the divide and 109 00:06:28,738 --> 00:06:33,720 conquer approach are already apparent, just in our simple four vertex example. 110 00:06:33,720 --> 00:06:38,320 So if we recurse on the left half, that is the first two vertices, and we compute 111 00:06:38,320 --> 00:06:42,579 a max weight independence set, that's just going to be the second vertex by 112 00:06:42,579 --> 00:06:45,249 itself. And if we independently recurse on the 113 00:06:45,249 --> 00:06:49,735 right hand side, on the vertices three and four, the maximum weight independence 114 00:06:49,735 --> 00:06:53,049 set on right half is going to be the vertex of weight five. 115 00:06:53,049 --> 00:06:57,369 And now when we, the recursion's complete and we get our sub-solutions back, we 116 00:06:57,369 --> 00:07:00,027 have the second vertex and we have third vertex, 117 00:07:00,027 --> 00:07:03,460 but the problem is the union of those two solutions conflicts. 118 00:07:03,460 --> 00:07:05,786 Right? We cannot simultaneously output the 119 00:07:05,786 --> 00:07:08,444 second and third vertices. Those are consecutive, 120 00:07:08,444 --> 00:07:10,770 those are adjacent, and that's not allowed. 121 00:07:10,770 --> 00:07:15,047 Moreover, you know, in a four note graph. It's sort of easy to see how to repair 122 00:07:15,047 --> 00:07:18,034 this conflict. But in a big graph with say thousands of 123 00:07:18,034 --> 00:07:22,379 nodes, if you have a conflict right where the two sub-problems meet, it is not at 124 00:07:22,379 --> 00:07:26,397 all obvious how you would quickly fix that and get a feasible and optimal 125 00:07:26,397 --> 00:07:30,259 solution to the original problem. Now in some sense the divide and conquer 126 00:07:30,259 --> 00:07:34,095 paradigm is more powerful or better suited for this problem than the greedy 127 00:07:34,095 --> 00:07:38,234 approach, in that I do know of divide and conquer algorithms that could solve this 128 00:07:38,234 --> 00:07:40,505 problem optimally that run in quadratic time. 129 00:07:40,505 --> 00:07:44,038 But doing better than that in a divide and conquer matter seems quite 130 00:07:44,038 --> 00:07:46,360 challenging. And the dynamic programming based 131 00:07:46,360 --> 00:07:49,489 algorithm we'll develop will solve the problem in linear time. 132 00:07:49,489 --> 00:07:50,600 That's coming up next.