1 00:00:00,000 --> 00:00:04,286 So, having out iterated through all of our algorithm design paradigms and 2 00:00:04,286 --> 00:00:08,749 noticing that none of them seem to work very well for computing the maximum 3 00:00:08,749 --> 00:00:13,389 weight independent set of a path graph, we're going to develop some ideas for a 4 00:00:13,389 --> 00:00:16,619 new paradigm. And the key approach in this new paradigm 5 00:00:16,619 --> 00:00:20,260 is to first reason about the structure of an optimal solution. 6 00:00:21,280 --> 00:00:26,347 What I mean by this is we're going to seek out statements of the following 7 00:00:26,347 --> 00:00:29,515 form. The optimal solution, whatever it may be, 8 00:00:29,515 --> 00:00:33,879 has to possess a certain form. It has to have been built up from an 9 00:00:33,879 --> 00:00:37,680 optimal solution to a sub-problem in a prescribed way. 10 00:00:38,980 --> 00:00:43,160 So in fact, in much of our discussion of both divide and conquer and greedy 11 00:00:43,160 --> 00:00:45,780 algorithms, this kind of reasoning was implicit. 12 00:00:45,780 --> 00:00:49,069 With dynamic programming, we're going to make it systematic. 13 00:00:49,069 --> 00:00:53,473 For example, implicit in the correctness of many of divide and conquer algorithm 14 00:00:53,473 --> 00:00:57,933 is the fact that an optimal solution to the whole problem has to be expressible, 15 00:00:57,933 --> 00:01:01,835 has to be constructable in a prescribed way from solutions to smaller 16 00:01:01,835 --> 00:01:04,809 sub-problems. So, what's the motivation for doing this 17 00:01:04,809 --> 00:01:09,309 thought experiment, trying to understand what the optimal solution could possibly 18 00:01:09,309 --> 00:01:12,065 look like? Well, the plan is we're going to narrow 19 00:01:12,065 --> 00:01:16,565 the possible candidates for the optimal solution down to a relatively small set 20 00:01:16,565 --> 00:01:19,490 of candidates. With a small set, we can get away with 21 00:01:19,490 --> 00:01:25,433 brute force search to pick the best one. So, one lesson you learn once you get 22 00:01:25,433 --> 00:01:29,754 good at dynamic programming, is that it's not at all circular to reason about the 23 00:01:29,754 --> 00:01:31,994 very object that you're trying to compute. 24 00:01:31,994 --> 00:01:36,261 Remember, the goal here is to devise an algorithm to compute an optimal solution. 25 00:01:36,261 --> 00:01:40,635 And now, I'm telling you to do a thought experiment as if you had already computed 26 00:01:40,635 --> 00:01:43,409 it, as if I had handed it to you on a silver platter. 27 00:01:43,409 --> 00:01:46,182 But that kind of daydreaming can be very productive. 28 00:01:46,182 --> 00:01:49,170 And thinking hey, what if I did have an optimal solution? 29 00:01:49,170 --> 00:01:51,966 What could I say about it? What would it look like? 30 00:01:51,966 --> 00:01:56,328 Observations of that form can actually light up a trail to the computation of 31 00:01:56,328 --> 00:01:59,851 that exact object and we'll see that in the next couple videos. 32 00:01:59,851 --> 00:02:03,934 Alright so that's enough loft, lofty philosophy for now, lets get concrete. 33 00:02:03,934 --> 00:02:07,290 Okay, so we've got this path graph, the vertices have weights. 34 00:02:07,290 --> 00:02:11,708 We want the max weight independent set. Let's again do this thought experiment. 35 00:02:11,708 --> 00:02:15,511 What if someone handed to us, what could we say about it's structure? 36 00:02:15,511 --> 00:02:19,929 We'll be using the following notation when we reason about this maximum weight 37 00:02:19,929 --> 00:02:24,170 independent set. S denotes the vertices in that optimal 38 00:02:24,170 --> 00:02:29,985 solution, in that max weight independent set and we're going to let V sub n denote 39 00:02:29,985 --> 00:02:33,740 the right most, the final vertex of the input graph. 40 00:02:35,780 --> 00:02:40,418 So, here's a content-free statement. This last vertex of the path, V sub n. 41 00:02:40,418 --> 00:02:44,670 Either it's an S or it isn't. So, that's going to give us two cases, 42 00:02:44,670 --> 00:02:47,376 when we reason about the optimal solution. 43 00:02:47,376 --> 00:02:52,015 Let's start with the case where Vn is excluded from the optimal solution 44 00:02:52,015 --> 00:02:55,043 capital S. So, let's let G prime denote the path 45 00:02:55,043 --> 00:02:59,747 graph you get by plucking off Vn, plucking off the right-most vertex from 46 00:02:59,747 --> 00:03:05,572 the original graph G. So, let's make a couple of trivial 47 00:03:05,572 --> 00:03:08,469 observations. So, first of all, this set, capital S, 48 00:03:08,469 --> 00:03:12,332 it's an independent set in G. It doesn't include the last vertex. 49 00:03:12,332 --> 00:03:17,040 So, we can regard this set as equally well as an independent set of the smaller 50 00:03:17,040 --> 00:03:20,420 graph G prime. If it didn't contain consecutive vertices 51 00:03:20,420 --> 00:03:23,979 in G, nor does it in G prime. But actually, we can say more. 52 00:03:23,979 --> 00:03:26,752 Not only is S any old independent set in G prime. 53 00:03:26,752 --> 00:03:31,910 It has to be an optimal, that is, maximum weight independent set in G prime. 54 00:03:31,910 --> 00:03:34,747 Why? Well, if there was something better than 55 00:03:34,747 --> 00:03:39,841 S in G prime, we could take that exact same independent set S star regarded as 56 00:03:39,841 --> 00:03:44,677 an independent set in G and, of course, it would still be better than S in G. 57 00:03:44,677 --> 00:03:49,900 But that contradicts our assumption that S was a max weight independent set in G. 58 00:03:52,580 --> 00:03:56,947 So summarizing, if the max weight independent set S of the original path 59 00:03:56,947 --> 00:04:01,740 graph G does not include the right-most vertex, it can be very simply described 60 00:04:01,740 --> 00:04:05,198 in terms of an optimal solution to a smaller sub-problem. 61 00:04:05,198 --> 00:04:10,051 It literally is a max weight independent set of G prime, the path graph with one 62 00:04:10,051 --> 00:04:15,039 fewer vertex. Alright. So, case one is a warm up for 63 00:04:15,039 --> 00:04:18,821 case two, which is similar but slightly more complicated. 64 00:04:18,821 --> 00:04:23,481 Now, let's assume that the maximum independent S does, in fact, use the 65 00:04:23,481 --> 00:04:30,466 right-most vertex, Vn. Now, by the definition of an independent 66 00:04:30,466 --> 00:04:33,163 set, no two consecutive, no two adjacent 67 00:04:33,163 --> 00:04:37,728 vertices can be chosen. So, by virtue of choosing, choosing V sub 68 00:04:37,728 --> 00:04:43,330 n, the right-most vertex S, in this case, absolutely cannot include the penultimate 69 00:04:43,330 --> 00:04:47,272 vertex V sub n - 1. So, we want to know by G double prime, 70 00:04:47,272 --> 00:04:52,460 the path you get from G by plucking off both of the right-most two vertices. 71 00:04:56,880 --> 00:05:00,609 So now, let's do our best to mimic the argument in case one. 72 00:05:00,609 --> 00:05:04,766 In case one, we said well, S has to also be an independent set of G 73 00:05:04,766 --> 00:05:07,594 prime. Now, here that doesn't make sense, right? 74 00:05:07,594 --> 00:05:12,496 Here, S contains the last vertex so we can't talk about it even being a subset 75 00:05:12,496 --> 00:05:16,267 of any smaller graph. However, if we think about S except for 76 00:05:16,267 --> 00:05:20,981 the last vertex of V sub n, S with Vn removed is an independent set, in fact, 77 00:05:20,981 --> 00:05:25,568 of G double prime, because remember, S can't contain the second to last vertex. 78 00:05:25,568 --> 00:05:30,408 And once again, just like in case one we can say something stronger, S with Vn 79 00:05:30,408 --> 00:05:35,435 removed is not any old independent set of G double prime, it actually must be an 80 00:05:35,435 --> 00:05:38,884 optimal one. It must have maximum possible weight. The 81 00:05:38,884 --> 00:05:43,487 reasoning is similar. Suppose S with Vn removed was not the best possible 82 00:05:43,487 --> 00:05:47,902 independent set in G double prime. Then there's something else called an S 83 00:05:47,902 --> 00:05:51,030 star which is even better, has even bigger weight. 84 00:05:51,030 --> 00:05:55,245 How do we get a contradiction? Well, if we just add Vn to this even 85 00:05:55,245 --> 00:06:00,162 bigger independent set S star that lies in G double prime, we get a bonafide 86 00:06:00,162 --> 00:06:05,272 independent set of the entire graph G with overall weight even bigger than that 87 00:06:05,272 --> 00:06:08,210 of S, but that contradicts the optimality of S. 88 00:06:08,210 --> 00:06:12,978 So, for example you could imagine that this reported optimal solution capital S 89 00:06:12,978 --> 00:06:17,687 had total weight 1,100 in two parts, it had 1,000 weight coming from vertices in 90 00:06:17,687 --> 00:06:22,637 the G double prime, but it also had V sub n which had weight 100 on its own. And so 91 00:06:22,637 --> 00:06:27,466 now, in the contradiction, you say, well, suppose there was an independent set that 92 00:06:27,466 --> 00:06:31,691 had even more than 1,000 weight just in G double prime, say, 1,000 and 50. 93 00:06:31,691 --> 00:06:36,581 Well then, we just add this last vertex V sub n to that, we get an independent set 94 00:06:36,581 --> 00:06:39,116 with weight 1,150 and the original graph G. 95 00:06:39,116 --> 00:06:43,322 But that contradicts the fact that S was supposed to be off more with weight 96 00:06:43,322 --> 00:06:46,176 nearly 1,100. So, notice that the reason were using the 97 00:06:46,176 --> 00:06:50,646 graph G double prime in this argument is to make sure that no matter what S star 98 00:06:50,646 --> 00:06:53,015 is, no matter what this independent set of G 99 00:06:53,015 --> 00:06:56,139 double prime is. We can just add V into it blively and not 100 00:06:56,139 --> 00:06:57,755 worry about feasibility, right? 101 00:06:57,755 --> 00:07:01,848 So, the right-most vertex S star could possibly possess is the third to last 102 00:07:01,848 --> 00:07:05,133 vertex Vn - 2. So, there's no worries about feasibility 103 00:07:05,133 --> 00:07:08,580 when we extend it by adding in the right-most vertex V sub n. 104 00:07:10,900 --> 00:07:15,064 So, to make sure you don't lose the forest for the trees, let me just point, 105 00:07:15,064 --> 00:07:19,341 let me remind you what our high level plan was, and let me point out that we 106 00:07:19,341 --> 00:07:23,168 actually just executed that plan quite successfully in this problem. 107 00:07:23,168 --> 00:07:27,277 The plan was to narrow down the candidates for what the optimal solution 108 00:07:27,277 --> 00:07:30,034 could be. To reason about the form of the optimal 109 00:07:30,034 --> 00:07:33,355 solution and argue that it has to look in a particular way. 110 00:07:33,355 --> 00:07:35,887 What did we just prove on the previous slide? 111 00:07:35,887 --> 00:07:39,996 We said that the optimal solution actually can only be one of two things. 112 00:07:39,996 --> 00:07:45,248 Either it excludes the final vertex and it is nothing more than the max weight 113 00:07:45,248 --> 00:07:50,319 independent set of G prime, or if it includes the right-most vertex than it 114 00:07:50,319 --> 00:07:55,952 must be, a maximum weight independent set frp, G double prime augmented with this 115 00:07:55,952 --> 00:08:00,178 last vertex V sub n. There's only two possibilities for what 116 00:08:00,178 --> 00:08:05,741 the optimal solution could possibly look like, in terms of optimal solutions of 117 00:08:05,741 --> 00:08:10,574 smaller sub problems. So, a corollary of this is that if a 118 00:08:10,574 --> 00:08:14,802 little birdie told us which case we were in, whether or not V sub n, V sub n was 119 00:08:14,802 --> 00:08:19,151 in the optimal solution, we could just complete this by recursing on the 120 00:08:19,151 --> 00:08:22,897 appropriate sub-problem. The little birdie tells us the optimal 121 00:08:22,897 --> 00:08:26,038 solution doesn't have Vn we just recurse on G prime. 122 00:08:26,038 --> 00:08:30,930 If the little birdie tells us v sub n is in the optimal solution, we recurse on G 123 00:08:30,930 --> 00:08:33,769 double prime and then add V sub n to the result. 124 00:08:33,769 --> 00:08:38,179 Now, of course, there is no little birdie and we have no idea whether this 125 00:08:38,179 --> 00:08:41,800 right-most vertex is in the optimal solution or not. 126 00:08:41,800 --> 00:08:44,617 But hey, there is only two possibilities, right? 127 00:08:44,617 --> 00:08:47,925 Here is an idea. Maybe it seems crazy, but why not try 128 00:08:47,925 --> 00:08:52,420 both possibilities and just return whichever one is better? 129 00:08:52,420 --> 00:08:56,970 Why do I suggest that maybe this is crazy? Well, if you stare at this and you 130 00:08:56,970 --> 00:09:01,041 think about it and you think about the ramifications of trying both 131 00:09:01,041 --> 00:09:05,651 possibilities as you recursed down the graph, this may start feeling a little 132 00:09:05,651 --> 00:09:08,405 bit like brute force search. And, in fact it is. 133 00:09:08,405 --> 00:09:12,118 This is just a recursive organization of a brute force search. 134 00:09:12,118 --> 00:09:16,728 Nevertheless, as we'll see in the next video, if we're smart about eliminating 135 00:09:16,728 --> 00:09:20,560 redundancy, we can actually implement this idea in a linear time.