1 00:00:00,000 --> 00:00:00,050 2 00:00:00,050 --> 00:00:01,770 The following content is provided 3 00:00:01,770 --> 00:00:04,000 under a Creative Commons license. 4 00:00:04,000 --> 00:00:06,860 Your support will help MIT OpenCourseWare continue 5 00:00:06,860 --> 00:00:10,720 to offer high quality educational resources for free. 6 00:00:10,720 --> 00:00:13,330 To make a donation or view additional materials 7 00:00:13,330 --> 00:00:15,770 from hundreds of MIT courses, visit 8 00:00:15,770 --> 00:00:21,340 MIT OpenCourseWare at ocw.mit.edu 9 00:00:21,340 --> 00:00:22,840 PROFESSOR: How about I propose this? 10 00:00:22,840 --> 00:00:26,810 We go through knapsack because it's 11 00:00:26,810 --> 00:00:29,260 on the Pset, not knapsack but a variation of it. 12 00:00:29,260 --> 00:00:31,510 If we have time, we do a couple variations. 13 00:00:31,510 --> 00:00:33,600 14 00:00:33,600 --> 00:00:34,870 If not, maybe not. 15 00:00:34,870 --> 00:00:37,127 And if we have time, we do at a distance. 16 00:00:37,127 --> 00:00:38,710 Let's see what happens after knapsack. 17 00:00:38,710 --> 00:00:39,438 18 00:00:39,438 --> 00:00:40,354 AUDIENCE: [INAUDIBLE]? 19 00:00:40,354 --> 00:00:41,305 20 00:00:41,305 --> 00:00:43,180 PROFESSOR: How many people got the difference 21 00:00:43,180 --> 00:00:44,970 between polynomial and pseudo polynomial? 22 00:00:44,970 --> 00:00:47,270 23 00:00:47,270 --> 00:00:49,440 OK, so we should definitely do knapsack. 24 00:00:49,440 --> 00:00:56,764 25 00:00:56,764 --> 00:00:58,680 AUDIENCE: Constant factors, they don't matter. 26 00:00:58,680 --> 00:00:59,554 Oh wait. [INAUDIBLE]. 27 00:00:59,554 --> 00:01:00,552 Yeah, they do. 28 00:01:00,552 --> 00:01:02,760 PROFESSOR: So the thing is it's not constant factors. 29 00:01:02,760 --> 00:01:04,720 That s there is not a constant. 30 00:01:04,720 --> 00:01:07,724 31 00:01:07,724 --> 00:01:08,640 AUDIENCE: [INAUDIBLE]. 32 00:01:08,640 --> 00:01:16,402 33 00:01:16,402 --> 00:01:17,860 PROFESSOR: So the knapsack problem. 34 00:01:17,860 --> 00:01:24,810 35 00:01:24,810 --> 00:01:26,050 So the way I look at it. 36 00:01:26,050 --> 00:01:26,850 You're a thief. 37 00:01:26,850 --> 00:01:29,110 You somehow made your way into a vault. 38 00:01:29,110 --> 00:01:31,884 That vault has n items. 39 00:01:31,884 --> 00:01:34,280 AUDIENCE: Way better than camping. 40 00:01:34,280 --> 00:01:44,310 PROFESSOR: Each item has a weight of si pounds, 41 00:01:44,310 --> 00:01:46,430 and after you get out of the vault, 42 00:01:46,430 --> 00:01:48,180 assuming you make it alive and everything, 43 00:01:48,180 --> 00:01:50,850 you can sell it for vi dollars on the market, 44 00:01:50,850 --> 00:01:54,540 so this is how much money you get out of it, vi. 45 00:01:54,540 --> 00:01:59,640 46 00:01:59,640 --> 00:02:03,200 Well, now the problem is the only thing you have with you 47 00:02:03,200 --> 00:02:09,870 as you enter that vault is one knapsack that 48 00:02:09,870 --> 00:02:11,865 can carry at most s pounds. 49 00:02:11,865 --> 00:02:13,720 50 00:02:13,720 --> 00:02:16,200 If you try to put more stuff in it, 51 00:02:16,200 --> 00:02:18,620 so if you try to load it up with more than s pounds, 52 00:02:18,620 --> 00:02:21,830 it's going to break as you try to escape from the vault 53 00:02:21,830 --> 00:02:23,530 and stuff is going to fall on the floor, 54 00:02:23,530 --> 00:02:26,670 and then many laser beams will shred you to pieces, 55 00:02:26,670 --> 00:02:28,120 so that's undesirable. 56 00:02:28,120 --> 00:02:29,160 57 00:02:29,160 --> 00:02:32,440 So we can only load the knapsack with s pounds. 58 00:02:32,440 --> 00:02:34,000 Now, given this restriction, we want 59 00:02:34,000 --> 00:02:36,130 to make as much money as possible 60 00:02:36,130 --> 00:02:38,780 out of the whole thing, so we want 61 00:02:38,780 --> 00:02:40,940 to load up the knapsack optimally. 62 00:02:40,940 --> 00:02:43,710 63 00:02:43,710 --> 00:02:44,924 Does this make sense? 64 00:02:44,924 --> 00:02:45,715 Everyone remembers? 65 00:02:45,715 --> 00:02:47,840 66 00:02:47,840 --> 00:02:48,665 Good. 67 00:02:48,665 --> 00:02:52,312 So two ways to solve it, graphs and dynamic programming. 68 00:02:52,312 --> 00:02:53,270 We're going to do both. 69 00:02:53,270 --> 00:02:56,920 Who wants to go for graphs first? 70 00:02:56,920 --> 00:02:59,370 Who wants-- OK, never mind. 71 00:02:59,370 --> 00:03:00,505 Majority has been achieved. 72 00:03:00,505 --> 00:03:04,170 73 00:03:04,170 --> 00:03:06,524 How do we represent this? 74 00:03:06,524 --> 00:03:08,190 First off, let's represent the solution. 75 00:03:08,190 --> 00:03:09,230 76 00:03:09,230 --> 00:03:11,700 Our solution is which items we chose, right? 77 00:03:11,700 --> 00:03:23,470 78 00:03:23,470 --> 00:03:25,355 So we can phrase this as n decisions. 79 00:03:25,355 --> 00:03:31,160 80 00:03:31,160 --> 00:03:33,080 Each decision is a true/false decision, 81 00:03:33,080 --> 00:03:37,070 and it indicates if you take that item with you or not. 82 00:03:37,070 --> 00:03:43,432 So di says, do I take item i? 83 00:03:43,432 --> 00:03:45,200 84 00:03:45,200 --> 00:03:47,040 So now this looks more like a game. 85 00:03:47,040 --> 00:03:49,150 You are on a TV, there's a game show, 86 00:03:49,150 --> 00:03:50,590 and you get asked n questions. 87 00:03:50,590 --> 00:03:53,540 Do you want to take this item with you, yes or no? 88 00:03:53,540 --> 00:03:55,760 If you somehow manage to get items 89 00:03:55,760 --> 00:03:58,652 that are more than s pounds heavy, you get shot, 90 00:03:58,652 --> 00:04:00,360 you don't make it to the end of the game. 91 00:04:00,360 --> 00:04:04,506 Otherwise, when you leave the game, 92 00:04:04,506 --> 00:04:05,880 you make some money and the money 93 00:04:05,880 --> 00:04:09,354 that you make depends on what items you took with you. 94 00:04:09,354 --> 00:04:11,020 So now this looks like the game problems 95 00:04:11,020 --> 00:04:13,810 that we used to solve with graphs in that you have 96 00:04:13,810 --> 00:04:15,620 decisions, those decisions are moves, 97 00:04:15,620 --> 00:04:17,839 and they get you through a graph of states. 98 00:04:17,839 --> 00:04:19,480 99 00:04:19,480 --> 00:04:21,490 Now, let's see what's in the state. 100 00:04:21,490 --> 00:04:23,065 What do we need to keep track of? 101 00:04:23,065 --> 00:04:25,690 First, we need to keep track of what item we're thinking about, 102 00:04:25,690 --> 00:04:26,190 right? 103 00:04:26,190 --> 00:04:27,117 104 00:04:27,117 --> 00:04:29,700 And then there's something else that we need to keep track of. 105 00:04:29,700 --> 00:04:35,260 106 00:04:35,260 --> 00:04:37,230 AUDIENCE: How much capacity we have. 107 00:04:37,230 --> 00:04:38,536 PROFESSOR: Yep, very good. 108 00:04:38,536 --> 00:04:39,910 So the reason I need that is when 109 00:04:39,910 --> 00:04:42,600 I'm deciding whether I'm taking an item or not, 110 00:04:42,600 --> 00:04:45,140 I want to know if I'm going to get shot or not. 111 00:04:45,140 --> 00:04:47,940 If I take too much stuff, I'm not going to make it, 112 00:04:47,940 --> 00:04:51,380 so I need to know if this item fits in my backpack or not. 113 00:04:51,380 --> 00:04:55,515 That's equivalent to knowing how much weight I have left. 114 00:04:55,515 --> 00:04:58,700 115 00:04:58,700 --> 00:05:00,640 So s pounds. 116 00:05:00,640 --> 00:05:06,245 Let's say this is capacity, how much weight 117 00:05:06,245 --> 00:05:07,930 left in my backpack's capacity. 118 00:05:07,930 --> 00:05:13,200 This is equivalent to how much weight I have accumulated, 119 00:05:13,200 --> 00:05:15,447 the total weight of my items. 120 00:05:15,447 --> 00:05:17,932 121 00:05:17,932 --> 00:05:21,570 Weight of the items I have taken so far. 122 00:05:21,570 --> 00:05:28,430 123 00:05:28,430 --> 00:05:32,880 So the sum of the weights of the taken items. 124 00:05:32,880 --> 00:05:33,505 125 00:05:33,505 --> 00:05:34,630 AUDIENCE: [INAUDIBLE] left. 126 00:05:34,630 --> 00:05:36,040 127 00:05:36,040 --> 00:05:38,482 Isn't it the total minus? 128 00:05:38,482 --> 00:05:40,440 PROFESSOR: Well, I'm saying they're equivalent, 129 00:05:40,440 --> 00:05:43,250 so if you know one, you can compute the other. 130 00:05:43,250 --> 00:05:44,330 They're not equal. 131 00:05:44,330 --> 00:05:45,450 132 00:05:45,450 --> 00:05:48,340 Knowing one lets you know the other one, 133 00:05:48,340 --> 00:05:51,470 but this is more useful in terms of putting the graph together, 134 00:05:51,470 --> 00:05:52,302 I claim. 135 00:05:52,302 --> 00:05:53,720 136 00:05:53,720 --> 00:05:55,435 We'll see if that is true or not as we 137 00:05:55,435 --> 00:05:56,685 try to put the graph together. 138 00:05:56,685 --> 00:05:58,000 139 00:05:58,000 --> 00:05:58,970 So what's a node? 140 00:05:58,970 --> 00:05:59,595 What's an edge? 141 00:05:59,595 --> 00:06:02,170 142 00:06:02,170 --> 00:06:10,040 AUDIENCE: An edge is putting in one more item, 143 00:06:10,040 --> 00:06:11,665 and a node is a state. 144 00:06:11,665 --> 00:06:17,040 145 00:06:17,040 --> 00:06:21,130 PROFESSOR: So what the weight going to be on an edge? 146 00:06:21,130 --> 00:06:22,780 If the edge means I'm taking an item, 147 00:06:22,780 --> 00:06:26,020 then the weight is going to be what? 148 00:06:26,020 --> 00:06:28,320 AUDIENCE: The weight of the item you're adding. 149 00:06:28,320 --> 00:06:31,100 150 00:06:31,100 --> 00:06:33,410 AUDIENCE: The earning associated with that. 151 00:06:33,410 --> 00:06:34,670 PROFESSOR: Yeah. 152 00:06:34,670 --> 00:06:37,570 I like this better because in the end, 153 00:06:37,570 --> 00:06:40,460 my goal is to maximize earnings, right? 154 00:06:40,460 --> 00:06:44,030 And I'm going to feed my graph to a shortest path algorithm. 155 00:06:44,030 --> 00:06:47,360 Maximize earnings, minimize path weight. 156 00:06:47,360 --> 00:06:49,490 They're the same issue, flip sign. 157 00:06:49,490 --> 00:06:57,044 So I'm going to say this is the value of the item almost. 158 00:06:57,044 --> 00:06:57,960 Does this work or not? 159 00:06:57,960 --> 00:07:00,060 160 00:07:00,060 --> 00:07:01,290 Negative value of the item. 161 00:07:01,290 --> 00:07:04,140 I have to flip the sign to turn it from a maximization problem 162 00:07:04,140 --> 00:07:06,090 to a minimization problem. 163 00:07:06,090 --> 00:07:10,020 So shortest path will give me the shortest path. 164 00:07:10,020 --> 00:07:12,580 That's going to correspond to making the least 165 00:07:12,580 --> 00:07:15,150 amount of money if I don't add this minus sign. 166 00:07:15,150 --> 00:07:18,280 167 00:07:18,280 --> 00:07:19,448 So what's a node? 168 00:07:19,448 --> 00:07:24,030 169 00:07:24,030 --> 00:07:26,162 AUDIENCE: Is it a unique set of items? 170 00:07:26,162 --> 00:07:26,870 PROFESSOR: Sorry? 171 00:07:26,870 --> 00:07:28,240 AUDIENCE: A unique set of items. 172 00:07:28,240 --> 00:07:28,823 PROFESSOR: OK. 173 00:07:28,823 --> 00:07:33,540 So the state in a node is going to have 174 00:07:33,540 --> 00:07:37,012 i, which is the item that I'm looking at, because this way, 175 00:07:37,012 --> 00:07:38,720 I'm going to have one node for each item. 176 00:07:38,720 --> 00:07:45,530 177 00:07:45,530 --> 00:07:48,900 And what else did I say I need to keep track of? 178 00:07:48,900 --> 00:07:50,844 179 00:07:50,844 --> 00:07:52,790 AUDIENCE: The weight of the taken items. 180 00:07:52,790 --> 00:07:53,415 PROFESSOR: Yep. 181 00:07:53,415 --> 00:08:01,240 182 00:08:01,240 --> 00:08:02,910 Weight of taken. 183 00:08:02,910 --> 00:08:08,360 184 00:08:08,360 --> 00:08:10,380 So this is sort of like the gas problem 185 00:08:10,380 --> 00:08:12,640 where you have to keep track of how much gas you have 186 00:08:12,640 --> 00:08:15,090 as well as where you are on the map. 187 00:08:15,090 --> 00:08:17,140 Sorry if it brings bad memories. 188 00:08:17,140 --> 00:08:20,190 Let's talk about an example so that we can draw a graph for it 189 00:08:20,190 --> 00:08:22,830 and see what things look like. 190 00:08:22,830 --> 00:08:27,700 So say we have three items, and say our backpack 191 00:08:27,700 --> 00:08:28,990 has five pounds. 192 00:08:28,990 --> 00:08:34,250 193 00:08:34,250 --> 00:08:41,110 And my three items are a golden statue, 194 00:08:41,110 --> 00:08:44,885 value $10, weight, four pounds. 195 00:08:44,885 --> 00:08:47,960 196 00:08:47,960 --> 00:08:50,885 These are 1800 dollars when money actually 197 00:08:50,885 --> 00:08:52,010 used to be worth something. 198 00:08:52,010 --> 00:08:55,660 199 00:08:55,660 --> 00:09:02,370 Crystal ball, you can sell this for $4, 200 00:09:02,370 --> 00:09:08,809 and it weighs two pounds, and someone in the previous section 201 00:09:08,809 --> 00:09:10,350 wanted a fountain pen, so we're going 202 00:09:10,350 --> 00:09:16,890 to use a fountain pen that's worth $7. 203 00:09:16,890 --> 00:09:18,180 204 00:09:18,180 --> 00:09:20,250 Culture is worth a lot of money, right? 205 00:09:20,250 --> 00:09:22,670 And weighs three pounds. 206 00:09:22,670 --> 00:09:24,170 Really ancient fountain pen. 207 00:09:24,170 --> 00:09:25,177 208 00:09:25,177 --> 00:09:26,760 I don't know how people wrote with it. 209 00:09:26,760 --> 00:09:28,580 210 00:09:28,580 --> 00:09:30,450 So how do we draw the graph for this? 211 00:09:30,450 --> 00:09:34,690 212 00:09:34,690 --> 00:09:41,250 AUDIENCE: We'd make a tree where each level the tree 213 00:09:41,250 --> 00:09:45,135 is take item i, or don't take item i. 214 00:09:45,135 --> 00:09:47,035 Make a big binary tree. 215 00:09:47,035 --> 00:09:47,985 Does that make sense? 216 00:09:47,985 --> 00:09:51,440 217 00:09:51,440 --> 00:09:54,200 PROFESSOR: So if each level of the tree 218 00:09:54,200 --> 00:09:56,097 says whether I'm taking an item or not, 219 00:09:56,097 --> 00:09:57,930 and then I have two descendants, then that's 220 00:09:57,930 --> 00:09:59,545 going to be 2 to the number of items. 221 00:09:59,545 --> 00:10:00,346 222 00:10:00,346 --> 00:10:01,720 So that's going to be exponential 223 00:10:01,720 --> 00:10:03,460 in the number of items, whereas we're 224 00:10:03,460 --> 00:10:07,240 going to end up in a solution where the running time is 225 00:10:07,240 --> 00:10:08,880 proportional to the number of items. 226 00:10:08,880 --> 00:10:12,536 227 00:10:12,536 --> 00:10:13,910 AUDIENCE: [INAUDIBLE]. 228 00:10:13,910 --> 00:10:17,080 PROFESSOR: I mean, it makes sense in some cases, 229 00:10:17,080 --> 00:10:19,280 if you have fractional costs or something. 230 00:10:19,280 --> 00:10:21,450 By the way, all these weights are integers. 231 00:10:21,450 --> 00:10:22,680 Sorry I didn't mention that. 232 00:10:22,680 --> 00:10:30,830 233 00:10:30,830 --> 00:10:31,360 My bad. 234 00:10:31,360 --> 00:10:34,890 235 00:10:34,890 --> 00:10:38,160 But I like the idea of having some sort of levels based 236 00:10:38,160 --> 00:10:45,440 on items, so let's say I'm going to have a starting node, 237 00:10:45,440 --> 00:10:48,300 and then I'm going to have some sort of layer for item one, 238 00:10:48,300 --> 00:10:51,625 some sort of layer for item two, and some sort of layer 239 00:10:51,625 --> 00:10:57,510 for item three, some sort of vertical layer. 240 00:10:57,510 --> 00:10:59,010 How many nodes do I have in a layer? 241 00:10:59,010 --> 00:11:02,076 242 00:11:02,076 --> 00:11:04,110 One node for each possible weight 243 00:11:04,110 --> 00:11:07,550 because I promised that in a node, I keep track of the item 244 00:11:07,550 --> 00:11:10,680 that I'm considering and the weight of the items I've 245 00:11:10,680 --> 00:11:11,490 taken so far. 246 00:11:11,490 --> 00:11:12,500 247 00:11:12,500 --> 00:11:14,320 How many possible weights do I have here? 248 00:11:14,320 --> 00:11:19,897 249 00:11:19,897 --> 00:11:20,896 AUDIENCE: Three weights. 250 00:11:20,896 --> 00:11:22,600 251 00:11:22,600 --> 00:11:25,800 PROFESSOR: So my backpack holds five pounds, so what 252 00:11:25,800 --> 00:11:27,250 are the possible sums I can get? 253 00:11:27,250 --> 00:11:27,750 How many? 254 00:11:27,750 --> 00:11:31,810 255 00:11:31,810 --> 00:11:32,990 AUDIENCE: 4, 2, 3, 5. 256 00:11:32,990 --> 00:11:34,350 257 00:11:34,350 --> 00:11:36,370 PROFESSOR: So far, I heard 2 3, 4, 5, 6. 258 00:11:36,370 --> 00:11:37,670 Who wants to bid more? 259 00:11:37,670 --> 00:11:39,800 260 00:11:39,800 --> 00:11:40,930 AUDIENCE: Not more than 6. 261 00:11:40,930 --> 00:11:42,399 262 00:11:42,399 --> 00:11:43,940 PROFESSOR: So the answer is 6, right? 263 00:11:43,940 --> 00:11:47,230 The possible weights are from 0, which is an empty knapsack, 264 00:11:47,230 --> 00:11:51,480 until weight 5, which is a full knapsack. 265 00:11:51,480 --> 00:11:52,750 266 00:11:52,750 --> 00:11:59,410 So weight 0, 1, 2, 3, 4, 5, 6, and I'm 267 00:11:59,410 --> 00:12:01,091 going to start drawing the nodes. 268 00:12:01,091 --> 00:12:03,481 269 00:12:03,481 --> 00:12:04,939 AUDIENCE: You could have weight 10. 270 00:12:04,939 --> 00:12:07,745 271 00:12:07,745 --> 00:12:09,370 PROFESSOR: We're never going to fill up 272 00:12:09,370 --> 00:12:11,230 a knapsack with more than 5. 273 00:12:11,230 --> 00:12:13,106 Otherwise, we're going to die. 274 00:12:13,106 --> 00:12:14,840 AUDIENCE: Why do we have 6, then? 275 00:12:14,840 --> 00:12:16,720 PROFESSOR: Because I can't thank. 276 00:12:16,720 --> 00:12:17,720 277 00:12:17,720 --> 00:12:18,220 Thank you. 278 00:12:18,220 --> 00:12:20,490 279 00:12:20,490 --> 00:12:23,360 So this node, the first node. 280 00:12:23,360 --> 00:12:25,045 Weight in the backpack, 0. 281 00:12:25,045 --> 00:12:26,500 282 00:12:26,500 --> 00:12:28,320 We're looking at item one. 283 00:12:28,320 --> 00:12:29,820 It's connected to the starting node. 284 00:12:29,820 --> 00:12:31,910 285 00:12:31,910 --> 00:12:33,580 What outgoing edges do I have? 286 00:12:33,580 --> 00:12:35,060 287 00:12:35,060 --> 00:12:36,440 What do I do with item one? 288 00:12:36,440 --> 00:12:37,910 I can take it or not take it. 289 00:12:37,910 --> 00:12:47,380 290 00:12:47,380 --> 00:12:49,754 AUDIENCE: You connect the edges 4, 2, 3. 291 00:12:49,754 --> 00:12:53,233 292 00:12:53,233 --> 00:12:54,899 Am I answering a different question? 293 00:12:54,899 --> 00:12:57,190 AUDIENCE: If it's item one, shouldn't it have a weight? 294 00:12:57,190 --> 00:12:59,440 PROFESSOR: So those have two numbers in them, i and j. 295 00:12:59,440 --> 00:13:00,290 296 00:13:00,290 --> 00:13:00,790 Sorry. 297 00:13:00,790 --> 00:13:03,060 They're in the wrong order here. 298 00:13:03,060 --> 00:13:03,900 1, 0. 299 00:13:03,900 --> 00:13:05,080 So I'm looking at item one. 300 00:13:05,080 --> 00:13:07,382 So far, I have zero pounds in my backpack. 301 00:13:07,382 --> 00:13:09,840 Looking at item two with zero pounds, looking at item three 302 00:13:09,840 --> 00:13:10,810 with zero pounds. 303 00:13:10,810 --> 00:13:12,040 304 00:13:12,040 --> 00:13:15,020 Looking at item one with one pound in my backpack, 305 00:13:15,020 --> 00:13:17,849 item two with one pound, item three with one pound, 306 00:13:17,849 --> 00:13:18,640 so on and so forth. 307 00:13:18,640 --> 00:13:26,760 308 00:13:26,760 --> 00:13:29,120 So if I'm looking at item one, and I 309 00:13:29,120 --> 00:13:33,440 have zero pounds in my backpack so far, what happens if I don't 310 00:13:33,440 --> 00:13:34,250 take item one? 311 00:13:34,250 --> 00:13:35,210 Where do I end up? 312 00:13:35,210 --> 00:13:36,626 313 00:13:36,626 --> 00:13:37,254 AUDIENCE: 2, 0. 314 00:13:37,254 --> 00:13:37,920 PROFESSOR: Yeah. 315 00:13:37,920 --> 00:13:40,160 So I'm looking at item two after I'm done deciding, 316 00:13:40,160 --> 00:13:43,160 what do I do with item one, and if I don't take item one, 317 00:13:43,160 --> 00:13:46,160 then I'm not going to have anything in my backpack. 318 00:13:46,160 --> 00:13:52,240 So this edge corresponds to we don't just take one. 319 00:13:52,240 --> 00:13:53,730 What if I want to take item one? 320 00:13:53,730 --> 00:13:54,590 Where do I land? 321 00:13:54,590 --> 00:13:56,578 322 00:13:56,578 --> 00:13:58,570 AUDIENCE: 2, 4. 323 00:13:58,570 --> 00:13:59,700 PROFESSOR: All right. 324 00:13:59,700 --> 00:14:00,820 2, 3. 325 00:14:00,820 --> 00:14:01,430 2, 4. 326 00:14:01,430 --> 00:14:04,000 327 00:14:04,000 --> 00:14:06,610 So if I did take item one, then I 328 00:14:06,610 --> 00:14:08,490 had zero pounds in my backpack before. 329 00:14:08,490 --> 00:14:12,350 Now I have four pounds, and I'm still considering item two. 330 00:14:12,350 --> 00:14:13,490 What about edge weights? 331 00:14:13,490 --> 00:14:17,780 332 00:14:17,780 --> 00:14:19,940 What's the weight of the edge that 333 00:14:19,940 --> 00:14:21,080 says I don't take item one? 334 00:14:21,080 --> 00:14:24,664 What's the weight of the edge that says I do take item one? 335 00:14:24,664 --> 00:14:25,580 AUDIENCE: [INAUDIBLE]. 336 00:14:25,580 --> 00:14:28,298 337 00:14:28,298 --> 00:14:29,215 AUDIENCE: Minus 10. 338 00:14:29,215 --> 00:14:30,090 PROFESSOR: All right. 339 00:14:30,090 --> 00:14:31,440 340 00:14:31,440 --> 00:14:33,290 0 and minus 10. 341 00:14:33,290 --> 00:14:36,010 That minus lets us get the shortest path. 342 00:14:36,010 --> 00:14:37,360 Now, suppose I'm in 2, 0. 343 00:14:37,360 --> 00:14:38,650 What are the outgoing edges? 344 00:14:38,650 --> 00:14:41,814 345 00:14:41,814 --> 00:14:48,757 AUDIENCE: It's the same as making a giant binary tree, 346 00:14:48,757 --> 00:14:49,257 right? 347 00:14:49,257 --> 00:14:55,090 348 00:14:55,090 --> 00:15:01,100 PROFESSOR: It's not going to be a tree because I 349 00:15:01,100 --> 00:15:03,370 can have multiple paths from a root to some node. 350 00:15:03,370 --> 00:15:05,998 351 00:15:05,998 --> 00:15:09,740 AUDIENCE: But this looks like it's taking the same complexity 352 00:15:09,740 --> 00:15:13,548 as building a tree if you were to carefully build the tree so 353 00:15:13,548 --> 00:15:15,928 that you don't have unfeasible solutions on the tree. 354 00:15:15,928 --> 00:15:19,284 355 00:15:19,284 --> 00:15:21,700 PROFESSOR: Then you're actually doing dynamic programming. 356 00:15:21,700 --> 00:15:23,783 You're not building the tree if you're doing that. 357 00:15:23,783 --> 00:15:25,747 358 00:15:25,747 --> 00:15:27,080 You're still converging to this. 359 00:15:27,080 --> 00:15:28,330 360 00:15:28,330 --> 00:15:30,950 You're probably thinking this and you said binary 361 00:15:30,950 --> 00:15:33,387 decision tree, or at least that's what I understood. 362 00:15:33,387 --> 00:15:35,220 You're probably thinking of the right thing. 363 00:15:35,220 --> 00:15:38,450 364 00:15:38,450 --> 00:15:41,950 We can see if we're thinking the same thing when we end up 365 00:15:41,950 --> 00:15:43,600 looking at the running time. 366 00:15:43,600 --> 00:15:44,510 Yes? 367 00:15:44,510 --> 00:15:49,110 AUDIENCE: The goal here is to have the most valuable items 368 00:15:49,110 --> 00:15:52,274 possible in the bag in terms of money? 369 00:15:52,274 --> 00:15:52,940 PROFESSOR: Yeah. 370 00:15:52,940 --> 00:15:58,930 PROFESSOR: So the negative 10 weight 371 00:15:58,930 --> 00:16:02,390 that you have there was because that item was $10. 372 00:16:02,390 --> 00:16:03,209 PROFESSOR: Yep. 373 00:16:03,209 --> 00:16:05,750 And in the end, we're going to give the graph to the shortest 374 00:16:05,750 --> 00:16:06,970 path algorithm. 375 00:16:06,970 --> 00:16:09,580 So yes, speaking of the goal, what's the answer here, 376 00:16:09,580 --> 00:16:10,199 by the way? 377 00:16:10,199 --> 00:16:10,740 AUDIENCE: 11. 378 00:16:10,740 --> 00:16:11,597 379 00:16:11,597 --> 00:16:12,180 PROFESSOR: 11. 380 00:16:12,180 --> 00:16:13,260 How do I get 11? 381 00:16:13,260 --> 00:16:15,184 382 00:16:15,184 --> 00:16:16,850 AUDIENCE: By getting the last two items. 383 00:16:16,850 --> 00:16:18,600 PROFESSOR: So I take the ball and the pen 384 00:16:18,600 --> 00:16:21,615 and I get 11, right? 385 00:16:21,615 --> 00:16:24,217 386 00:16:24,217 --> 00:16:25,300 Everyone on the same page? 387 00:16:25,300 --> 00:16:28,460 388 00:16:28,460 --> 00:16:30,480 So I'm at item two. 389 00:16:30,480 --> 00:16:32,030 I have zero pounds in my backpack. 390 00:16:32,030 --> 00:16:33,588 What are my outgoing edges? 391 00:16:33,588 --> 00:16:36,860 AUDIENCE: To 3, 0 and to 3, 2. 392 00:16:36,860 --> 00:16:38,156 393 00:16:38,156 --> 00:16:39,170 Wait, sorry. 394 00:16:39,170 --> 00:16:40,100 That's the third item. 395 00:16:40,100 --> 00:16:41,145 396 00:16:41,145 --> 00:16:42,270 PROFESSOR: No, second item. 397 00:16:42,270 --> 00:16:42,770 You're good. 398 00:16:42,770 --> 00:16:44,720 399 00:16:44,720 --> 00:16:48,336 AUDIENCE: Shouldn't it be 3, 3 because the third item 400 00:16:48,336 --> 00:16:49,270 has three pounds? 401 00:16:49,270 --> 00:16:51,270 PROFESSOR: I said I'm looking at the second item 402 00:16:51,270 --> 00:16:53,080 and then I'm deciding where I'm going. 403 00:16:53,080 --> 00:16:54,720 So this graph has a problem in that 404 00:16:54,720 --> 00:16:56,570 when I get to the third item, what do I do? 405 00:16:56,570 --> 00:17:00,580 So I need one more layer here, which means that I'm done. 406 00:17:00,580 --> 00:17:04,483 AUDIENCE: I was saying that it's the outgoing edge from 2, 0, 407 00:17:04,483 --> 00:17:06,410 it's the weight of the taken item, 408 00:17:06,410 --> 00:17:09,720 so if you decide to take the third item, 409 00:17:09,720 --> 00:17:13,361 shouldn't the outgoing edge go to 3, 3, not 3, 2? 410 00:17:13,361 --> 00:17:15,819 PROFESSOR: But when I'm at layer two, 411 00:17:15,819 --> 00:17:17,764 I'm only looking at item two. 412 00:17:17,764 --> 00:17:19,430 So I'm looking at the items in sequence. 413 00:17:19,430 --> 00:17:22,150 First I have to decide, am I taking item one? 414 00:17:22,150 --> 00:17:25,060 Then I decide, am I taking item two, and then I'm deciding, 415 00:17:25,060 --> 00:17:26,690 am I taking item three? 416 00:17:26,690 --> 00:17:28,359 While I'm here, I don't see item three. 417 00:17:28,359 --> 00:17:29,720 I only see item two. 418 00:17:29,720 --> 00:17:32,564 AUDIENCE: Aren't those weights on the left side, though? 419 00:17:32,564 --> 00:17:33,230 PROFESSOR: Yeah. 420 00:17:33,230 --> 00:17:34,490 These are backpack weights. 421 00:17:34,490 --> 00:17:38,390 422 00:17:38,390 --> 00:17:42,915 So down here, these are pounds and these are items. 423 00:17:42,915 --> 00:17:50,544 424 00:17:50,544 --> 00:17:51,960 What are the weights on the edges? 425 00:17:51,960 --> 00:17:54,355 426 00:17:54,355 --> 00:17:55,792 0 and negative 1. 427 00:17:55,792 --> 00:17:57,977 428 00:17:57,977 --> 00:17:58,560 PROFESSOR: OK. 429 00:17:58,560 --> 00:18:00,590 430 00:18:00,590 --> 00:18:02,390 How about this other node, 2, 4? 431 00:18:02,390 --> 00:18:04,140 What are the edges coming out of it. 432 00:18:04,140 --> 00:18:06,565 433 00:18:06,565 --> 00:18:07,535 AUDIENCE: 2, 0. 434 00:18:07,535 --> 00:18:09,475 435 00:18:09,475 --> 00:18:10,445 AUDIENCE: 3, 4. 436 00:18:10,445 --> 00:18:13,276 437 00:18:13,276 --> 00:18:15,650 PROFESSOR: So if I decide I'm not going to take item two, 438 00:18:15,650 --> 00:18:18,390 but I already have four pounds in my backpack, 439 00:18:18,390 --> 00:18:22,330 I'm still going to end up with four pounds in my backpack, 440 00:18:22,330 --> 00:18:24,520 and I don't get anything out of it. 441 00:18:24,520 --> 00:18:25,020 And? 442 00:18:25,020 --> 00:18:26,340 443 00:18:26,340 --> 00:18:27,660 AUDIENCE: That's it. 444 00:18:27,660 --> 00:18:29,243 PROFESSOR: And that's it, because if I 445 00:18:29,243 --> 00:18:33,230 try to take the second item, that would put me overweight, 446 00:18:33,230 --> 00:18:34,850 so the edge would go out of the graph. 447 00:18:34,850 --> 00:18:36,216 Therefore, it doesn't exist. 448 00:18:36,216 --> 00:18:40,042 AUDIENCE: You can remove it, and then you go back to 3, 0, 449 00:18:40,042 --> 00:18:41,428 right? 450 00:18:41,428 --> 00:18:42,360 Is that not allowed? 451 00:18:42,360 --> 00:18:43,990 PROFESSOR: No, because when I'm here, 452 00:18:43,990 --> 00:18:45,160 I don't know how I got here. 453 00:18:45,160 --> 00:18:46,870 I don't know if I had item one or not. 454 00:18:46,870 --> 00:18:49,140 455 00:18:49,140 --> 00:18:50,990 The benefits of doing it this way is here, 456 00:18:50,990 --> 00:18:52,250 I'm just looking at item two. 457 00:18:52,250 --> 00:18:53,790 I do not know how I got there. 458 00:18:53,790 --> 00:18:55,786 I do not care what I'm going to do later. 459 00:18:55,786 --> 00:18:57,410 I'm just looking at one item and making 460 00:18:57,410 --> 00:18:58,640 one decision based on that. 461 00:18:58,640 --> 00:19:01,730 462 00:19:01,730 --> 00:19:02,680 Does this make sense? 463 00:19:02,680 --> 00:19:04,610 464 00:19:04,610 --> 00:19:06,510 Where do I get my answer from? 465 00:19:06,510 --> 00:19:11,430 466 00:19:11,430 --> 00:19:14,174 AUDIENCE: Can you put a final node on the right side? 467 00:19:14,174 --> 00:19:15,590 PROFESSOR: OK, so one way of doing 468 00:19:15,590 --> 00:19:17,480 it is that I'm going to have a final note on the right side 469 00:19:17,480 --> 00:19:19,019 and connecting everything to it. 470 00:19:19,019 --> 00:19:21,060 AUDIENCE: Do you need the done nodes right there, 471 00:19:21,060 --> 00:19:23,560 or could you have just skipped done and connected 3 to that? 472 00:19:23,560 --> 00:19:25,520 473 00:19:25,520 --> 00:19:27,470 PROFESSOR: So I can do that, but then it's 474 00:19:27,470 --> 00:19:29,660 going to be hard to reason about edges. 475 00:19:29,660 --> 00:19:31,540 This makes it easier to reason about edges 476 00:19:31,540 --> 00:19:33,900 because when I'm looking at this layer, 477 00:19:33,900 --> 00:19:35,830 I'm still going to have edges deciding 478 00:19:35,830 --> 00:19:37,350 whether I take item three or not. 479 00:19:37,350 --> 00:19:39,049 480 00:19:39,049 --> 00:19:41,340 So it would be confusing to have all the edges pointing 481 00:19:41,340 --> 00:19:43,080 to the same place. 482 00:19:43,080 --> 00:19:45,720 I can, it's just that the graph would look more confusing. 483 00:19:45,720 --> 00:19:48,640 484 00:19:48,640 --> 00:19:51,200 By the way, if I'm at 3, 2, what are the outgoing edges 485 00:19:51,200 --> 00:19:51,870 from 3, 2? 486 00:19:51,870 --> 00:19:53,710 487 00:19:53,710 --> 00:19:55,480 AUDIENCE: It's just all horizontal. 488 00:19:55,480 --> 00:19:57,460 You can't take anymore. 489 00:19:57,460 --> 00:20:01,810 PROFESSOR: So I can be done with two pounds, 490 00:20:01,810 --> 00:20:04,070 and that means I get 0 or I can take 491 00:20:04,070 --> 00:20:05,690 item three, and then where do I land? 492 00:20:05,690 --> 00:20:08,155 493 00:20:08,155 --> 00:20:09,141 AUDIENCE: Negative 7. 494 00:20:09,141 --> 00:20:18,270 495 00:20:18,270 --> 00:20:20,390 PROFESSOR: Does this make sense now somewhat? 496 00:20:20,390 --> 00:20:26,564 497 00:20:26,564 --> 00:20:29,380 AUDIENCE: So what about this dynamic programming style? 498 00:20:29,380 --> 00:20:30,880 PROFESSOR: We'll get there in a bit. 499 00:20:30,880 --> 00:20:33,840 Before, let's see what's the running time for this. 500 00:20:33,840 --> 00:20:35,780 So one way of finishing this up is 501 00:20:35,780 --> 00:20:39,110 we connect everything to one destination node. 502 00:20:39,110 --> 00:20:41,970 Another way of doing it is that we connect the source nodes 503 00:20:41,970 --> 00:20:50,810 to everything here with edges of cost 0 and say, 504 00:20:50,810 --> 00:20:53,150 well, this is how much weight we're going to waste. 505 00:20:53,150 --> 00:20:54,570 506 00:20:54,570 --> 00:20:57,339 So if my solution path goes here and then goes 507 00:20:57,339 --> 00:20:58,880 somewhere through the graph, it means 508 00:20:58,880 --> 00:21:01,690 that I'm going to waste one pound of capacity, 509 00:21:01,690 --> 00:21:05,039 so my backpack is going to have four pounds when I'm done. 510 00:21:05,039 --> 00:21:07,354 AUDIENCE: Would it be [INAUDIBLE] or infinity? 511 00:21:07,354 --> 00:21:08,369 512 00:21:08,369 --> 00:21:09,910 PROFESSOR: What should the weight be? 513 00:21:09,910 --> 00:21:10,640 Good question. 514 00:21:10,640 --> 00:21:12,597 515 00:21:12,597 --> 00:21:14,180 AUDIENCE: This is not possible, right? 516 00:21:14,180 --> 00:21:15,420 To get from s to 1, 1. 517 00:21:15,420 --> 00:21:17,520 518 00:21:17,520 --> 00:21:20,150 PROFESSOR: So I'm saying that if I get from s to 1, 1, 519 00:21:20,150 --> 00:21:22,730 this means that I'm wasting a pound. 520 00:21:22,730 --> 00:21:24,900 My backpack will have four pounds of stuff 521 00:21:24,900 --> 00:21:27,240 and then one pound of capacity will go to waste. 522 00:21:27,240 --> 00:21:28,615 AUDIENCE: Isn't there another way 523 00:21:28,615 --> 00:21:31,023 to waste it on the right side if you end at the top? 524 00:21:31,023 --> 00:21:32,915 525 00:21:32,915 --> 00:21:36,033 Or not at the bottom, basically. 526 00:21:36,033 --> 00:21:36,699 PROFESSOR: Yeah. 527 00:21:36,699 --> 00:21:37,465 528 00:21:37,465 --> 00:21:39,090 AUDIENCE: So you're not double counting 529 00:21:39,090 --> 00:21:41,082 in terms of losing stuff? 530 00:21:41,082 --> 00:21:43,486 531 00:21:43,486 --> 00:21:44,861 You're representing losing weight 532 00:21:44,861 --> 00:21:47,325 on the left side and the right side. 533 00:21:47,325 --> 00:21:49,950 PROFESSOR: Well, if I represent losing weight on the left side, 534 00:21:49,950 --> 00:21:52,610 then the advantage is that I have a single destination node. 535 00:21:52,610 --> 00:21:53,210 What is it? 536 00:21:53,210 --> 00:21:55,359 537 00:21:55,359 --> 00:21:56,150 AUDIENCE: That dot. 538 00:21:56,150 --> 00:21:57,525 PROFESSOR: So this is the source. 539 00:21:57,525 --> 00:21:58,370 540 00:21:58,370 --> 00:22:00,460 The destination is this guy. 541 00:22:00,460 --> 00:22:03,280 I can waste capacity here, so that 542 00:22:03,280 --> 00:22:04,710 means I can say that on this side, 543 00:22:04,710 --> 00:22:06,790 I don't need to waste stuff. 544 00:22:06,790 --> 00:22:08,610 On this side, I need to arrive at done 5. 545 00:22:08,610 --> 00:22:11,637 546 00:22:11,637 --> 00:22:14,220 That's the advantage of doing it this way, aside from the fact 547 00:22:14,220 --> 00:22:16,136 that it's going to map to dynamic programming. 548 00:22:16,136 --> 00:22:17,220 549 00:22:17,220 --> 00:22:18,620 There are many ways of doing it. 550 00:22:18,620 --> 00:22:21,090 551 00:22:21,090 --> 00:22:23,270 I can choose to connect the source to 1, 0, 552 00:22:23,270 --> 00:22:27,420 and then look at all the paths here and choose the best one. 553 00:22:27,420 --> 00:22:29,210 I can connect the source to everything 554 00:22:29,210 --> 00:22:31,530 here with paths of some weight, which you guys still 555 00:22:31,530 --> 00:22:34,300 need to tell me what it is, and then I can look at the answer 556 00:22:34,300 --> 00:22:35,150 here. 557 00:22:35,150 --> 00:22:36,105 AUDIENCE: Cost 0. 558 00:22:36,105 --> 00:22:36,980 PROFESSOR: Thank you. 559 00:22:36,980 --> 00:22:42,850 560 00:22:42,850 --> 00:22:44,730 So this is another way. 561 00:22:44,730 --> 00:22:47,710 And yet the third way would be to only connect 562 00:22:47,710 --> 00:22:50,460 the source to the first node, and then 563 00:22:50,460 --> 00:22:53,380 connect all these done nodes to another node with cost 0, 564 00:22:53,380 --> 00:22:55,399 and this is equivalent to this. 565 00:22:55,399 --> 00:22:56,815 The reason we're doing it this way 566 00:22:56,815 --> 00:22:58,648 is because this maps to dynamic programming. 567 00:22:58,648 --> 00:23:00,424 568 00:23:00,424 --> 00:23:01,132 AUDIENCE: Easier. 569 00:23:01,132 --> 00:23:03,444 570 00:23:03,444 --> 00:23:04,110 PROFESSOR: Yeah. 571 00:23:04,110 --> 00:23:07,457 It maps closely to how the DP runs. 572 00:23:07,457 --> 00:23:10,440 AUDIENCE: I mean is it possible to do the DP such 573 00:23:10,440 --> 00:23:12,180 that you do it the other way as well? 574 00:23:12,180 --> 00:23:13,420 PROFESSOR: Yeah. 575 00:23:13,420 --> 00:23:15,552 You can flip the DP around, too. 576 00:23:15,552 --> 00:23:17,520 577 00:23:17,520 --> 00:23:18,720 How are we doing with this? 578 00:23:18,720 --> 00:23:20,940 579 00:23:20,940 --> 00:23:23,570 So then I hope the running time analysis will go really fast. 580 00:23:23,570 --> 00:23:24,320 How many vertices? 581 00:23:24,320 --> 00:23:25,742 582 00:23:25,742 --> 00:23:26,880 AUDIENCE: v or three. 583 00:23:26,880 --> 00:23:28,310 PROFESSOR: OK, so v is? 584 00:23:28,310 --> 00:23:29,999 585 00:23:29,999 --> 00:23:30,540 AUDIENCE: ns. 586 00:23:30,540 --> 00:23:32,850 587 00:23:32,850 --> 00:23:34,260 PROFESSOR: n layers, right? 588 00:23:34,260 --> 00:23:35,330 589 00:23:35,330 --> 00:23:36,600 n plus 1 layers, actually. 590 00:23:36,600 --> 00:23:37,640 591 00:23:37,640 --> 00:23:41,322 AUDIENCE: n times weight mass. 592 00:23:41,322 --> 00:23:42,780 PROFESSOR: n times capacity, right? 593 00:23:42,780 --> 00:23:44,740 594 00:23:44,740 --> 00:23:48,602 So it's actually n plus 1 times capacity plus 1, 595 00:23:48,602 --> 00:23:50,060 but I don't want to deal with that, 596 00:23:50,060 --> 00:23:52,370 so I'm going to use order of so that I 597 00:23:52,370 --> 00:23:54,050 don't have to deal with that. 598 00:23:54,050 --> 00:23:56,615 How many edges going out of a vertex? 599 00:23:56,615 --> 00:24:00,315 600 00:24:00,315 --> 00:24:01,290 AUDIENCE: Two. 601 00:24:01,290 --> 00:24:02,620 PROFESSOR: Yep. 602 00:24:02,620 --> 00:24:05,526 So at most, two edges per vertex. 603 00:24:05,526 --> 00:24:09,870 604 00:24:09,870 --> 00:24:11,100 So how many edges total? 605 00:24:11,100 --> 00:24:13,319 606 00:24:13,319 --> 00:24:13,860 AUDIENCE: ns. 607 00:24:13,860 --> 00:24:16,744 608 00:24:16,744 --> 00:24:19,160 PROFESSOR: What shortest path algorithm am I going to use? 609 00:24:19,160 --> 00:24:20,082 610 00:24:20,082 --> 00:24:21,040 AUDIENCE: Bellman-Ford. 611 00:24:21,040 --> 00:24:22,833 612 00:24:22,833 --> 00:24:24,124 AUDIENCE: Topological sort BFS. 613 00:24:24,124 --> 00:24:24,826 614 00:24:24,826 --> 00:24:26,700 PROFESSOR: I'm going to choose the second one 615 00:24:26,700 --> 00:24:28,120 because it runs faster. 616 00:24:28,120 --> 00:24:32,510 So Bellman-Ford's running time is V times E. 617 00:24:32,510 --> 00:24:36,090 If I use the DAG algorithm, that means topological sort and then 618 00:24:36,090 --> 00:24:36,780 a DFS. 619 00:24:36,780 --> 00:24:41,230 That's V plus E. So please, whenever 620 00:24:41,230 --> 00:24:44,730 you have a dynamic programming graph, this is the answer. 621 00:24:44,730 --> 00:24:45,772 It's never anything else. 622 00:24:45,772 --> 00:24:46,605 It's never Dijkstra. 623 00:24:46,605 --> 00:24:47,710 It's never Bellman-Ford. 624 00:24:47,710 --> 00:24:48,680 It's always this. 625 00:24:48,680 --> 00:24:55,670 626 00:24:55,670 --> 00:24:56,460 And this means? 627 00:24:56,460 --> 00:25:00,329 628 00:25:00,329 --> 00:25:00,870 AUDIENCE: ns. 629 00:25:00,870 --> 00:25:03,217 630 00:25:03,217 --> 00:25:04,800 PROFESSOR: So this is the running time 631 00:25:04,800 --> 00:25:05,716 of the graph solution. 632 00:25:05,716 --> 00:25:07,750 633 00:25:07,750 --> 00:25:11,270 AUDIENCE: If you use BFS, do you need 634 00:25:11,270 --> 00:25:14,150 to put in the dummy nodes for the edge weights? 635 00:25:14,150 --> 00:25:16,070 636 00:25:16,070 --> 00:25:17,265 PROFESSOR: If you use BFS. 637 00:25:17,265 --> 00:25:21,360 638 00:25:21,360 --> 00:25:21,900 Yes. 639 00:25:21,900 --> 00:25:24,344 So then the running time would be bigger than V plus E. 640 00:25:24,344 --> 00:25:25,010 AUDIENCE: Right. 641 00:25:25,010 --> 00:25:27,830 So then the running time depends on [INAUDIBLE] 642 00:25:27,830 --> 00:25:29,460 multiply by s again? 643 00:25:29,460 --> 00:25:31,800 PROFESSOR: This isn't doing BFS. 644 00:25:31,800 --> 00:25:34,050 This is doing the shortest path algorithm 645 00:25:34,050 --> 00:25:36,570 for direct acyclic graphs. 646 00:25:36,570 --> 00:25:38,000 It's the DAG shortest path. 647 00:25:38,000 --> 00:25:38,950 AUDIENCE: Right. 648 00:25:38,950 --> 00:25:40,440 PROFESSOR: Were you here before Thanksgiving? 649 00:25:40,440 --> 00:25:40,940 AUDIENCE: No 650 00:25:40,940 --> 00:25:42,034 PROFESSOR: Right before? 651 00:25:42,034 --> 00:25:43,075 You missed the algorithm. 652 00:25:43,075 --> 00:25:44,290 653 00:25:44,290 --> 00:25:46,660 It's in the Dijkstra lecture notes. 654 00:25:46,660 --> 00:25:48,540 AUDIENCE: But basically, you don't 655 00:25:48,540 --> 00:25:50,527 have to put in all the dummy nodes? 656 00:25:50,527 --> 00:25:51,110 PROFESSOR: No. 657 00:25:51,110 --> 00:25:54,440 So you do a topological sort, and then 658 00:25:54,440 --> 00:25:56,060 you only consider a node once, and you 659 00:25:56,060 --> 00:25:57,620 look at all the edges coming through it 660 00:25:57,620 --> 00:25:59,036 and make a decision based on that. 661 00:25:59,036 --> 00:26:03,166 662 00:26:03,166 --> 00:26:05,290 So this is the running time, this is the algorithm, 663 00:26:05,290 --> 00:26:06,165 this is the solution. 664 00:26:06,165 --> 00:26:08,275 What if we do dynamic programming instead? 665 00:26:08,275 --> 00:26:09,670 666 00:26:09,670 --> 00:26:12,560 Instead of nodes, we have sub-problems. 667 00:26:12,560 --> 00:26:15,190 A sub-problem maps to a node. 668 00:26:15,190 --> 00:26:17,660 The same things that we decided about this data 669 00:26:17,660 --> 00:26:20,880 that we store in a node, the same things 670 00:26:20,880 --> 00:26:23,860 are going to apply to the state that we have in a sub-problem. 671 00:26:23,860 --> 00:26:33,302 672 00:26:33,302 --> 00:26:34,510 So what are the sub-problems? 673 00:26:34,510 --> 00:26:47,785 674 00:26:47,785 --> 00:26:49,910 First up, how many sub-problems am I going to have? 675 00:26:49,910 --> 00:26:52,784 676 00:26:52,784 --> 00:26:53,284 AUDIENCE: n. 677 00:26:53,284 --> 00:26:55,635 678 00:26:55,635 --> 00:26:56,176 AUDIENCE: ns. 679 00:26:56,176 --> 00:26:57,870 680 00:26:57,870 --> 00:27:00,140 PROFESSOR: I just said that one sub-problem 681 00:27:00,140 --> 00:27:02,470 will map to a vertex in the graph. 682 00:27:02,470 --> 00:27:04,670 ns vertices, ns sub-problems, right? 683 00:27:04,670 --> 00:27:07,250 684 00:27:07,250 --> 00:27:07,970 Come on, guys. 685 00:27:07,970 --> 00:27:08,860 Bear with me. 686 00:27:08,860 --> 00:27:10,294 Get more cookies. 687 00:27:10,294 --> 00:27:11,460 Are the cookies still there? 688 00:27:11,460 --> 00:27:12,419 689 00:27:12,419 --> 00:27:13,960 Please pass them around and eat them. 690 00:27:13,960 --> 00:27:15,410 691 00:27:15,410 --> 00:27:15,910 Yes? 692 00:27:15,910 --> 00:27:18,052 693 00:27:18,052 --> 00:27:24,816 AUDIENCE: One sub-problem would be getting the most amount 694 00:27:24,816 --> 00:27:28,047 of money for that little weight. 695 00:27:28,047 --> 00:27:29,940 696 00:27:29,940 --> 00:27:32,932 At one pound [INAUDIBLE], how much [INAUDIBLE]. 697 00:27:32,932 --> 00:27:34,890 PROFESSOR: I like that, so let's start writing. 698 00:27:34,890 --> 00:27:35,900 699 00:27:35,900 --> 00:27:46,180 What is the maximum value that I can get using a certain weight? 700 00:27:46,180 --> 00:27:53,410 701 00:27:53,410 --> 00:27:56,270 If I label the nodes indices i, j, I'm 702 00:27:56,270 --> 00:27:58,880 also going to label the sub-problems using i, j. 703 00:27:58,880 --> 00:28:03,150 So I'm going to say that sub-problem i, j 704 00:28:03,150 --> 00:28:05,520 is, what's the maximum amount of money 705 00:28:05,520 --> 00:28:08,960 I can get by using a weight of at most j, 706 00:28:08,960 --> 00:28:12,909 and you said something about items, 707 00:28:12,909 --> 00:28:14,450 so we have to figure out which items. 708 00:28:14,450 --> 00:28:18,520 709 00:28:18,520 --> 00:28:19,020 Which items? 710 00:28:19,020 --> 00:28:25,280 711 00:28:25,280 --> 00:28:26,390 Anyone else can help her. 712 00:28:26,390 --> 00:28:28,130 You already did the hard work, so you 713 00:28:28,130 --> 00:28:30,570 have most of the stuff filled in. 714 00:28:30,570 --> 00:28:32,502 Feel free to jump in. 715 00:28:32,502 --> 00:28:34,127 AUDIENCE: Greater than or equal to i. 716 00:28:34,127 --> 00:28:34,710 PROFESSOR: OK. 717 00:28:34,710 --> 00:28:38,200 718 00:28:38,200 --> 00:28:38,760 Sounds good. 719 00:28:38,760 --> 00:28:40,086 720 00:28:40,086 --> 00:28:42,460 We're going to number the items starting from 0 this time 721 00:28:42,460 --> 00:28:44,793 because we're going to have a dynamic programming table, 722 00:28:44,793 --> 00:28:47,660 and that means we like zero base indexing. 723 00:28:47,660 --> 00:28:55,360 So the items are going to be 0, 1, and 2. 724 00:28:55,360 --> 00:29:00,970 0 is the statue, 1 is the ball, and 2 is the pen. 725 00:29:00,970 --> 00:29:02,920 726 00:29:02,920 --> 00:29:05,460 This means we're going to look at suffixes of items. 727 00:29:05,460 --> 00:29:09,620 First, the empty set, no item, then only 728 00:29:09,620 --> 00:29:12,184 the pen, then the ball and the pen, and then 729 00:29:12,184 --> 00:29:13,600 the statue, the ball, and the pen. 730 00:29:13,600 --> 00:29:16,260 731 00:29:16,260 --> 00:29:20,146 And we're also going to consider how much weight we 732 00:29:20,146 --> 00:29:21,020 have in our backpack. 733 00:29:21,020 --> 00:29:24,266 734 00:29:24,266 --> 00:29:25,390 So let me write this again. 735 00:29:25,390 --> 00:29:31,080 0, 1, 2 here, and weights 0, 1, 2, 3, 4, 5, and this 736 00:29:31,080 --> 00:29:32,715 is going to be our DP table. 737 00:29:32,715 --> 00:29:40,747 738 00:29:40,747 --> 00:29:42,330 Now, how are we going to compute this? 739 00:29:42,330 --> 00:29:46,340 740 00:29:46,340 --> 00:29:47,780 DP of i, j is? 741 00:29:47,780 --> 00:29:56,127 742 00:29:56,127 --> 00:29:57,025 AUDIENCE: Maximum. 743 00:29:57,025 --> 00:29:58,900 PROFESSOR: All right, a maximum of something. 744 00:29:58,900 --> 00:30:00,110 Good. 745 00:30:00,110 --> 00:30:01,590 Perfect way to start. 746 00:30:01,590 --> 00:30:03,383 How many decisions do we have? 747 00:30:03,383 --> 00:30:03,966 AUDIENCE: Two. 748 00:30:03,966 --> 00:30:04,885 749 00:30:04,885 --> 00:30:05,510 PROFESSOR: Two. 750 00:30:05,510 --> 00:30:07,780 It's the same as in the graph problem, right? 751 00:30:07,780 --> 00:30:10,400 Once we solve that, this should be pretty easy 752 00:30:10,400 --> 00:30:12,080 because it's really very similar. 753 00:30:12,080 --> 00:30:14,090 So the two decisions are, do I take item i, 754 00:30:14,090 --> 00:30:15,710 do I not take item i? 755 00:30:15,710 --> 00:30:21,528 If I don't take item i, what situation do I land in? 756 00:30:21,528 --> 00:30:23,770 757 00:30:23,770 --> 00:30:25,960 So suppose I don't take item i. 758 00:30:25,960 --> 00:30:27,633 759 00:30:27,633 --> 00:30:28,777 AUDIENCE: i plus 1. 760 00:30:28,777 --> 00:30:29,360 PROFESSOR: OK. 761 00:30:29,360 --> 00:30:31,130 762 00:30:31,130 --> 00:30:32,170 i plus 1. 763 00:30:32,170 --> 00:30:37,100 So I have to make up my answer using items i plus 1 764 00:30:37,100 --> 00:30:39,280 all the way through n minus 1, and how much weight 765 00:30:39,280 --> 00:30:40,200 do they have to have? 766 00:30:40,200 --> 00:30:41,501 767 00:30:41,501 --> 00:30:42,000 AUDIENCE: j. 768 00:30:42,000 --> 00:30:43,040 769 00:30:43,040 --> 00:30:43,665 PROFESSOR: Yep. 770 00:30:43,665 --> 00:30:45,930 771 00:30:45,930 --> 00:30:48,729 Now suppose I do take item i. 772 00:30:48,729 --> 00:30:49,270 What happens? 773 00:30:49,270 --> 00:30:53,230 774 00:30:53,230 --> 00:30:54,730 AUDIENCE: i plus-- no, no, no. 775 00:30:54,730 --> 00:30:56,304 776 00:30:56,304 --> 00:30:58,220 PROFESSOR: You're thinking of the right thing. 777 00:30:58,220 --> 00:30:59,511 We're making some money, right? 778 00:30:59,511 --> 00:31:00,530 779 00:31:00,530 --> 00:31:01,330 AUDIENCE: Value i. 780 00:31:01,330 --> 00:31:02,880 PROFESSOR: Value i. 781 00:31:02,880 --> 00:31:04,680 So this is how much money we're making. 782 00:31:04,680 --> 00:31:05,495 Good. 783 00:31:05,495 --> 00:31:10,445 AUDIENCE: Plus dp i plus 1 j minus weight i. 784 00:31:10,445 --> 00:31:15,394 785 00:31:15,394 --> 00:31:16,310 PROFESSOR: Make sense? 786 00:31:16,310 --> 00:31:17,680 787 00:31:17,680 --> 00:31:20,460 OK Now I only have to do one more thing to make sure 788 00:31:20,460 --> 00:31:22,510 this code doesn't crash. 789 00:31:22,510 --> 00:31:23,440 AUDIENCE: I'm sorry. 790 00:31:23,440 --> 00:31:25,300 What's the third term for? 791 00:31:25,300 --> 00:31:26,095 792 00:31:26,095 --> 00:31:28,095 PROFESSOR: This is I'm making some money, right? 793 00:31:28,095 --> 00:31:29,180 794 00:31:29,180 --> 00:31:31,450 This means I'm going to have to look at the items 795 00:31:31,450 --> 00:31:33,930 starting from i plus 1 and i minus 1. 796 00:31:33,930 --> 00:31:36,160 And now I took item i, so that means 797 00:31:36,160 --> 00:31:38,135 I have si pounds in my backpack. 798 00:31:38,135 --> 00:31:39,240 799 00:31:39,240 --> 00:31:44,210 So the remaining items must weigh j minus si pounds 800 00:31:44,210 --> 00:31:47,850 because I'm going to add the si pounds for this item, 801 00:31:47,850 --> 00:31:50,060 and in total, I'm going to have at most j pounds. 802 00:31:50,060 --> 00:31:52,060 803 00:31:52,060 --> 00:31:53,675 Make some money, lose some capacity. 804 00:31:53,675 --> 00:31:56,132 805 00:31:56,132 --> 00:31:57,340 AUDIENCE: Did we [INAUDIBLE]? 806 00:31:57,340 --> 00:31:58,860 807 00:31:58,860 --> 00:31:59,485 PROFESSOR: Yep. 808 00:31:59,485 --> 00:32:00,629 809 00:32:00,629 --> 00:32:02,670 This is what happens when you move from the graph 810 00:32:02,670 --> 00:32:04,811 to dynamic programming, or you can 811 00:32:04,811 --> 00:32:06,310 draw the graph the other way around. 812 00:32:06,310 --> 00:32:08,260 813 00:32:08,260 --> 00:32:10,624 AUDIENCE: So could you have also done plus si, 814 00:32:10,624 --> 00:32:13,492 and then done something else as well? 815 00:32:13,492 --> 00:32:14,200 PROFESSOR: Sorry. 816 00:32:14,200 --> 00:32:14,890 Plus si-- 817 00:32:14,890 --> 00:32:16,598 AUDIENCE: If you did plus si and then you 818 00:32:16,598 --> 00:32:19,960 did some other check case that was different. 819 00:32:19,960 --> 00:32:22,030 PROFESSOR: Well, I do need to make a check. 820 00:32:22,030 --> 00:32:22,890 AUDIENCE: Yes. 821 00:32:22,890 --> 00:32:24,445 So that's greater than or equal to 0. 822 00:32:24,445 --> 00:32:25,352 823 00:32:25,352 --> 00:32:26,560 PROFESSOR: This thing, right? 824 00:32:26,560 --> 00:32:28,476 Because otherwise, the code is going to crash. 825 00:32:28,476 --> 00:32:30,570 826 00:32:30,570 --> 00:32:32,750 So j minus si is greater or equal to 0. 827 00:32:32,750 --> 00:32:39,290 I think this means j is greater than or equal to si, right? 828 00:32:39,290 --> 00:32:40,272 AUDIENCE: Yes. 829 00:32:40,272 --> 00:32:40,855 PROFESSOR: OK. 830 00:32:40,855 --> 00:32:50,170 831 00:32:50,170 --> 00:32:52,750 At least for me, the natural order when I have the graph 832 00:32:52,750 --> 00:32:55,576 is to consider the moves that by making in the game. 833 00:32:55,576 --> 00:32:57,200 I'm answering the questions one by one. 834 00:32:57,200 --> 00:32:58,033 Do I take this item? 835 00:32:58,033 --> 00:32:59,220 Do I not take this item? 836 00:32:59,220 --> 00:33:01,220 837 00:33:01,220 --> 00:33:05,740 When I'm in the DP, when I make a decision, 838 00:33:05,740 --> 00:33:08,850 I want to have the full information on that decision. 839 00:33:08,850 --> 00:33:11,190 Whether I take the item or not depends 840 00:33:11,190 --> 00:33:13,760 on what would happen with the items following it. 841 00:33:13,760 --> 00:33:15,060 842 00:33:15,060 --> 00:33:16,610 Representing it this way allows me 843 00:33:16,610 --> 00:33:17,960 to make the decision right here. 844 00:33:17,960 --> 00:33:19,685 845 00:33:19,685 --> 00:33:21,893 AUDIENCE: If we'd done prefixes rather than suffixes, 846 00:33:21,893 --> 00:33:23,040 we could have done it the same. 847 00:33:23,040 --> 00:33:25,373 PROFESSOR: It would have been exactly the same as there. 848 00:33:25,373 --> 00:33:28,790 849 00:33:28,790 --> 00:33:31,180 So we taught dynamic programming over many years, 850 00:33:31,180 --> 00:33:33,380 and it turns out that people understand suffixes 851 00:33:33,380 --> 00:33:37,330 better than prefixes, and the graph format 852 00:33:37,330 --> 00:33:38,830 makes more sense that way, so that's 853 00:33:38,830 --> 00:33:40,020 why we're doing it this way. 854 00:33:40,020 --> 00:33:40,978 It's for your own sake. 855 00:33:40,978 --> 00:33:42,200 Trust me. 856 00:33:42,200 --> 00:33:43,200 Or at least we think so. 857 00:33:43,200 --> 00:33:44,631 858 00:33:44,631 --> 00:33:46,150 AUDIENCE: Where does suffix come in? 859 00:33:46,150 --> 00:33:47,603 I know what it means. 860 00:33:47,603 --> 00:33:49,455 PROFESSOR: These guys. 861 00:33:49,455 --> 00:33:51,307 These are the sub-problems. 862 00:33:51,307 --> 00:33:54,170 Nothing, item two, items one, two, zero, one, two, 863 00:33:54,170 --> 00:33:56,030 so it's a suffix of the set of items. 864 00:33:56,030 --> 00:33:57,381 865 00:33:57,381 --> 00:34:00,006 AUDIENCE: How come you're going backwards rather than forwards? 866 00:34:00,006 --> 00:34:02,988 867 00:34:02,988 --> 00:34:05,680 It doesn't actually matter if you go backwards or forwards? 868 00:34:05,680 --> 00:34:05,860 PROFESSOR: Yep. 869 00:34:05,860 --> 00:34:07,776 In the end, we're going to look at everything. 870 00:34:07,776 --> 00:34:09,310 871 00:34:09,310 --> 00:34:10,690 So we need two things. 872 00:34:10,690 --> 00:34:16,239 We need to know where is the answer going to be, 873 00:34:16,239 --> 00:34:18,690 and we need to know what are the initial conditions. 874 00:34:18,690 --> 00:34:24,449 875 00:34:24,449 --> 00:34:25,159 Actually, I lied. 876 00:34:25,159 --> 00:34:26,600 We also need a topological sort. 877 00:34:26,600 --> 00:34:31,900 878 00:34:31,900 --> 00:34:33,127 So where do we want to start? 879 00:34:33,127 --> 00:34:34,531 880 00:34:34,531 --> 00:34:35,467 AUDIENCE: First one. 881 00:34:35,467 --> 00:34:36,309 882 00:34:36,309 --> 00:34:37,600 PROFESSOR: Where is the answer? 883 00:34:37,600 --> 00:34:40,570 884 00:34:40,570 --> 00:34:41,861 Yes? 885 00:34:41,861 --> 00:34:43,805 AUDIENCE: The lower right hand corner. 886 00:34:43,805 --> 00:34:46,235 I mean, if you have all the [INAUDIBLE] nodes. 887 00:34:46,235 --> 00:34:49,516 Oh, we don't have a Done column, do we? 888 00:34:49,516 --> 00:34:50,099 PROFESSOR: No. 889 00:34:50,099 --> 00:34:51,940 890 00:34:51,940 --> 00:34:54,480 Well, so the answer will have considered all the items, 891 00:34:54,480 --> 00:34:55,086 right? 892 00:34:55,086 --> 00:34:55,760 AUDIENCE: Top left. 893 00:34:55,760 --> 00:34:56,676 PROFESSOR: So which i? 894 00:34:56,676 --> 00:34:59,305 895 00:34:59,305 --> 00:34:59,805 Almost. 896 00:34:59,805 --> 00:35:02,350 897 00:35:02,350 --> 00:35:04,960 So the top left corner means I looked at all the items 898 00:35:04,960 --> 00:35:06,920 and I have an empty knapsack. 899 00:35:06,920 --> 00:35:09,700 AUDIENCE: Oh, so the max of all of the first column. 900 00:35:09,700 --> 00:35:12,241 901 00:35:12,241 --> 00:35:13,740 PROFESSOR: So the max of all columns 902 00:35:13,740 --> 00:35:16,170 would be the answer if the weight here would be equal, 903 00:35:16,170 --> 00:35:20,380 but I said the weight has to be smaller or equal, 904 00:35:20,380 --> 00:35:21,719 so the answer is easier. 905 00:35:21,719 --> 00:35:22,760 I don't have to do a max. 906 00:35:22,760 --> 00:35:23,640 AUDIENCE: Bottom left corner. 907 00:35:23,640 --> 00:35:24,973 PROFESSOR: I can only look here. 908 00:35:24,973 --> 00:35:27,090 909 00:35:27,090 --> 00:35:33,290 So this means that I will use a weight of at most s, 910 00:35:33,290 --> 00:35:38,000 because this is s, and I will have considered items 0 911 00:35:38,000 --> 00:35:39,320 and larger, so all the items. 912 00:35:39,320 --> 00:35:41,080 913 00:35:41,080 --> 00:35:42,255 This is where the answer is. 914 00:35:42,255 --> 00:35:44,650 915 00:35:44,650 --> 00:35:47,970 And in general terms, that means DP of what and what? 916 00:35:47,970 --> 00:35:53,650 917 00:35:53,650 --> 00:35:55,338 So what's the bottom left corner? 918 00:35:55,338 --> 00:35:56,294 AUDIENCE: 0, s. 919 00:35:56,294 --> 00:35:58,059 920 00:35:58,059 --> 00:35:58,684 PROFESSOR: Yep. 921 00:35:58,684 --> 00:36:02,030 922 00:36:02,030 --> 00:36:06,550 AUDIENCE: Can you explain again why it needs to be DP 0, s. 923 00:36:06,550 --> 00:36:09,240 PROFESSOR: I think it's easier to look at 0, 924 00:36:09,240 --> 00:36:11,476 s and see how it maps to the sub-problem, 925 00:36:11,476 --> 00:36:13,600 and then convince yourself that this is the answer, 926 00:36:13,600 --> 00:36:14,330 so let's do that. 927 00:36:14,330 --> 00:36:15,440 928 00:36:15,440 --> 00:36:18,300 DP of 0, s means i is 0, j is s. 929 00:36:18,300 --> 00:36:19,502 930 00:36:19,502 --> 00:36:20,960 So this is going to tell me what is 931 00:36:20,960 --> 00:36:23,290 the maximum amount of dollars I can 932 00:36:23,290 --> 00:36:28,000 get by using a weight of at most s-- agrees 933 00:36:28,000 --> 00:36:33,350 with the initial problem-- and using items i or greater 934 00:36:33,350 --> 00:36:37,960 than i, or 0 or more, so items 0 through n minus 1. 935 00:36:37,960 --> 00:36:39,120 936 00:36:39,120 --> 00:36:40,940 These are all the items. 937 00:36:40,940 --> 00:36:42,882 This is the maximum capacity, so this maps 938 00:36:42,882 --> 00:36:43,840 to the initial problem. 939 00:36:43,840 --> 00:36:46,190 940 00:36:46,190 --> 00:36:48,320 And that's why I did this. 941 00:36:48,320 --> 00:36:50,230 That's why I don't have an equal sign here. 942 00:36:50,230 --> 00:36:51,797 943 00:36:51,797 --> 00:36:53,630 AUDIENCE: And if you did have an equal sign, 944 00:36:53,630 --> 00:36:55,550 then you would be changing your sub-problems? 945 00:36:55,550 --> 00:36:57,320 946 00:36:57,320 --> 00:36:59,480 PROFESSOR: The recursion stays the same, 947 00:36:59,480 --> 00:37:02,950 but I have to look at all these to get the maximum. 948 00:37:02,950 --> 00:37:03,910 Someone suggested that. 949 00:37:03,910 --> 00:37:05,520 950 00:37:05,520 --> 00:37:08,190 AUDIENCE: If you put an equals there, 951 00:37:08,190 --> 00:37:11,080 you're going to have to do something to the DP such 952 00:37:11,080 --> 00:37:14,170 that the equals actually is captivated, 953 00:37:14,170 --> 00:37:16,130 because you can't just arbitrarily-- 954 00:37:16,130 --> 00:37:17,671 PROFESSOR: What do you think of this? 955 00:37:17,671 --> 00:37:18,499 956 00:37:18,499 --> 00:37:20,790 AUDIENCE: Something there is going to change, isn't it? 957 00:37:20,790 --> 00:37:21,210 PROFESSOR: No. 958 00:37:21,210 --> 00:37:22,001 I think this works. 959 00:37:22,001 --> 00:37:24,150 960 00:37:24,150 --> 00:37:27,008 This stays the same no matter what the sign is. 961 00:37:27,008 --> 00:37:28,880 962 00:37:28,880 --> 00:37:31,370 The only thing that changes is where is the answer 963 00:37:31,370 --> 00:37:33,309 and what are the initial conditions. 964 00:37:33,309 --> 00:37:33,850 AUDIENCE: Oh. 965 00:37:33,850 --> 00:37:35,515 So there's something else that changes. 966 00:37:35,515 --> 00:37:36,000 PROFESSOR: Yep. 967 00:37:36,000 --> 00:37:36,791 Initial conditions. 968 00:37:36,791 --> 00:37:38,510 969 00:37:38,510 --> 00:37:39,010 Good. 970 00:37:39,010 --> 00:37:40,593 I like that you're thinking about that 971 00:37:40,593 --> 00:37:42,790 because the next problem changes pretty much that. 972 00:37:42,790 --> 00:37:44,610 973 00:37:44,610 --> 00:37:46,320 The sign changes and then these change. 974 00:37:46,320 --> 00:37:51,420 975 00:37:51,420 --> 00:37:53,390 What's a good topological sort? 976 00:37:53,390 --> 00:37:55,080 This should be pretty easy. 977 00:37:55,080 --> 00:37:57,550 If I want to generate a topological sort, 978 00:37:57,550 --> 00:38:00,650 what variables do I iterate over, and in what order? 979 00:38:00,650 --> 00:38:02,580 980 00:38:02,580 --> 00:38:03,347 AUDIENCE: i. 981 00:38:03,347 --> 00:38:03,930 PROFESSOR: OK. 982 00:38:03,930 --> 00:38:06,500 983 00:38:06,500 --> 00:38:11,330 And you're pointing at n, right? 984 00:38:11,330 --> 00:38:13,570 AUDIENCE: n down to 0. 985 00:38:13,570 --> 00:38:14,195 PROFESSOR: Yep. 986 00:38:14,195 --> 00:38:15,942 987 00:38:15,942 --> 00:38:19,870 And then the only one left is j, so i in, and then j 988 00:38:19,870 --> 00:38:21,762 goes from where to where? 989 00:38:21,762 --> 00:38:24,117 AUDIENCE: j goes to s. 990 00:38:24,117 --> 00:38:25,770 AUDIENCE: It can go either direction. 991 00:38:25,770 --> 00:38:26,936 992 00:38:26,936 --> 00:38:27,685 PROFESSOR: Can it? 993 00:38:27,685 --> 00:38:31,050 994 00:38:31,050 --> 00:38:32,620 What do the dependencies look like? 995 00:38:32,620 --> 00:38:33,700 996 00:38:33,700 --> 00:38:39,700 When I'm computing i, j, I want i plus 1 and j minus-- 997 00:38:39,700 --> 00:38:43,680 so I'm looking at lower j's, higher i's and lower j's. 998 00:38:43,680 --> 00:38:44,925 999 00:38:44,925 --> 00:38:46,744 AUDIENCE: But it's always higher i's. 1000 00:38:46,744 --> 00:38:48,160 Doesn't that mean in this for loop 1001 00:38:48,160 --> 00:38:50,618 that you're already going to have calculated the next right 1002 00:38:50,618 --> 00:38:52,820 column, so it doesn't matter where 1003 00:38:52,820 --> 00:38:56,265 the column-- I may be wrong. 1004 00:38:56,265 --> 00:38:57,265 PROFESSOR: You're right. 1005 00:38:57,265 --> 00:38:58,421 1006 00:38:58,421 --> 00:38:58,920 Fine. 1007 00:38:58,920 --> 00:39:00,870 OK, both orders work. 1008 00:39:00,870 --> 00:39:03,180 I just looked at this because I wanted 1009 00:39:03,180 --> 00:39:05,360 to have a nice, simple-- but fine, both work. 1010 00:39:05,360 --> 00:39:07,190 1011 00:39:07,190 --> 00:39:07,815 AUDIENCE: Wait. 1012 00:39:07,815 --> 00:39:10,270 You mean reversing j works? 1013 00:39:10,270 --> 00:39:15,820 PROFESSOR: Yes, because we're iterating over i 1014 00:39:15,820 --> 00:39:17,050 before iterating over j. 1015 00:39:17,050 --> 00:39:18,670 1016 00:39:18,670 --> 00:39:20,070 Of course, this makes more sense. 1017 00:39:20,070 --> 00:39:21,749 Just because they're both good answers 1018 00:39:21,749 --> 00:39:23,540 doesn't mean you should choose the one that 1019 00:39:23,540 --> 00:39:24,670 requires more thinking. 1020 00:39:24,670 --> 00:39:26,670 I always like the answer that requires the least 1021 00:39:26,670 --> 00:39:29,377 amount of thinking to prove that it's correct. 1022 00:39:29,377 --> 00:39:33,070 AUDIENCE: Does that mean you're starting with a full-- 1023 00:39:33,070 --> 00:39:34,760 PROFESSOR: I start here. 1024 00:39:34,760 --> 00:39:40,220 AUDIENCE: But if you're going from s down to 0, 1025 00:39:40,220 --> 00:39:43,220 then you're starting down at the corner, which 1026 00:39:43,220 --> 00:39:46,140 means you have a full knapsack, so that doesn't make sense. 1027 00:39:46,140 --> 00:39:48,800 PROFESSOR: So the argument was when I compute this, 1028 00:39:48,800 --> 00:39:52,910 I'm looking one right, i plus 1j, 1029 00:39:52,910 --> 00:39:55,275 and then I'm looking somewhere here. 1030 00:39:55,275 --> 00:39:56,620 1031 00:39:56,620 --> 00:39:59,660 And I've already computed this column, 1032 00:39:59,660 --> 00:40:01,760 so it doesn't matter if I go up or down. 1033 00:40:01,760 --> 00:40:04,500 1034 00:40:04,500 --> 00:40:07,014 And that argument is correct because first I'm 1035 00:40:07,014 --> 00:40:09,180 going to compute this column, then this column, then 1036 00:40:09,180 --> 00:40:10,430 this column, then this column. 1037 00:40:10,430 --> 00:40:13,469 1038 00:40:13,469 --> 00:40:14,760 By the way, what's this column? 1039 00:40:14,760 --> 00:40:16,301 This column is the initial condition. 1040 00:40:16,301 --> 00:40:27,760 1041 00:40:27,760 --> 00:40:29,650 Now that we figured out the topological sort, 1042 00:40:29,650 --> 00:40:32,389 let's try to compute values here and see 1043 00:40:32,389 --> 00:40:33,930 what the initial condition should be. 1044 00:40:33,930 --> 00:40:36,860 1045 00:40:36,860 --> 00:40:40,460 So if I want to compute DP of 2, 0, 1046 00:40:40,460 --> 00:40:46,370 that is the maximum of either DP 3, 0 or something else. 1047 00:40:46,370 --> 00:40:48,070 This is going to evaluate to false, 1048 00:40:48,070 --> 00:40:50,750 so it's going to be this. 1049 00:40:50,750 --> 00:40:52,772 What should the answer be here? 1050 00:40:52,772 --> 00:40:53,949 AUDIENCE: 0. 1051 00:40:53,949 --> 00:40:54,490 PROFESSOR: 0. 1052 00:40:54,490 --> 00:40:56,080 1053 00:40:56,080 --> 00:41:00,190 So we want DP of 3, 0 to be 0 for this to work. 1054 00:41:00,190 --> 00:41:01,182 1055 00:41:01,182 --> 00:41:02,890 So what's a reasonable initial condition? 1056 00:41:02,890 --> 00:41:06,292 1057 00:41:06,292 --> 00:41:09,220 AUDIENCE: Column 3 is of 0 height. 1058 00:41:09,220 --> 00:41:14,890 PROFESSOR: DP of nj is 0 for all j, 1059 00:41:14,890 --> 00:41:16,661 pretty much what you said in math mode. 1060 00:41:16,661 --> 00:41:18,970 1061 00:41:18,970 --> 00:41:20,640 So I'm going to have an extra column. 1062 00:41:20,640 --> 00:41:23,440 This is like the Done problem over there, 1063 00:41:23,440 --> 00:41:25,200 and here I'm going to say that whenever 1064 00:41:25,200 --> 00:41:28,870 I'm looking at the empty subset-- 1065 00:41:28,870 --> 00:41:31,240 these are all suffixes. 1066 00:41:31,240 --> 00:41:34,635 All three items, two items, one item, empty suffix. 1067 00:41:34,635 --> 00:41:35,930 1068 00:41:35,930 --> 00:41:38,530 Whenever I look at the empty suffix, 1069 00:41:38,530 --> 00:41:43,270 I can fill up a backpack with any weight by using no items, 1070 00:41:43,270 --> 00:41:44,575 and I'm going to make 0 money. 1071 00:41:44,575 --> 00:41:54,430 1072 00:41:54,430 --> 00:41:56,240 So what are the values here? 1073 00:41:56,240 --> 00:42:00,002 1074 00:42:00,002 --> 00:42:01,460 You guys nodded, so you understood, 1075 00:42:01,460 --> 00:42:03,030 so then you should be able to dictate 1076 00:42:03,030 --> 00:42:04,030 the values in the table. 1077 00:42:04,030 --> 00:42:08,842 1078 00:42:08,842 --> 00:42:12,280 AUDIENCE: So is that one also 0 because you can't go up 1079 00:42:12,280 --> 00:42:18,442 to anything, and then the next one is 4 because you can go-- 1080 00:42:18,442 --> 00:42:19,150 PROFESSOR: Sorry. 1081 00:42:19,150 --> 00:42:23,680 Next one is-- so it's for the fountain pen, right? 1082 00:42:23,680 --> 00:42:24,200 Last item. 1083 00:42:24,200 --> 00:42:26,130 1084 00:42:26,130 --> 00:42:27,122 AUDIENCE: Crystal ball. 1085 00:42:27,122 --> 00:42:30,750 1086 00:42:30,750 --> 00:42:33,480 PROFESSOR: So we're going statute, ball, pen. 1087 00:42:33,480 --> 00:42:34,959 1088 00:42:34,959 --> 00:42:37,431 AUDIENCE: And this is weight on the left side, right? 1089 00:42:37,431 --> 00:42:39,180 PROFESSOR: So we're filling them like this 1090 00:42:39,180 --> 00:42:42,554 in the topological sort order that we chose here. 1091 00:42:42,554 --> 00:42:43,970 We said this is the order, so this 1092 00:42:43,970 --> 00:42:46,054 is what we're going to use to calculate the table. 1093 00:42:46,054 --> 00:42:46,595 AUDIENCE: Oh. 1094 00:42:46,595 --> 00:42:47,580 So it's still 0, then. 1095 00:42:47,580 --> 00:42:48,163 PROFESSOR: OK. 1096 00:42:48,163 --> 00:42:50,398 1097 00:42:50,398 --> 00:42:50,898 AUDIENCE: 7. 1098 00:42:50,898 --> 00:42:52,850 1099 00:42:52,850 --> 00:42:55,169 PROFESSOR: So here, this condition 1100 00:42:55,169 --> 00:42:56,710 is going to evaluate to True finally, 1101 00:42:56,710 --> 00:43:01,120 so this is going to be the maximum of either DP i plus 1j, 1102 00:43:01,120 --> 00:43:08,930 so DP of 3, 3, which is 0, or 7 plus DP of 3, 0. 1103 00:43:08,930 --> 00:43:11,860 So 7 plus 0, which is 7. 1104 00:43:11,860 --> 00:43:12,610 That's why it's 7. 1105 00:43:12,610 --> 00:43:15,404 1106 00:43:15,404 --> 00:43:17,119 AUDIENCE: 7, 7. 1107 00:43:17,119 --> 00:43:17,785 PROFESSOR: 7, 7. 1108 00:43:17,785 --> 00:43:19,500 1109 00:43:19,500 --> 00:43:20,350 How about this? 1110 00:43:20,350 --> 00:43:23,266 1111 00:43:23,266 --> 00:43:23,766 AUDIENCE: 0. 1112 00:43:23,766 --> 00:43:25,706 1113 00:43:25,706 --> 00:43:26,206 0. 1114 00:43:26,206 --> 00:43:28,634 1115 00:43:28,634 --> 00:43:29,134 4. 1116 00:43:29,134 --> 00:43:32,070 1117 00:43:32,070 --> 00:43:34,650 PROFESSOR: The maximum of 0 and 4 plus 0, right? 1118 00:43:34,650 --> 00:43:38,564 1119 00:43:38,564 --> 00:43:39,400 AUDIENCE: 4. 1120 00:43:39,400 --> 00:43:39,941 AUDIENCE: No. 1121 00:43:39,941 --> 00:43:40,440 7. 1122 00:43:40,440 --> 00:43:47,170 PROFESSOR: So it's the maximum of 7 or 4 plus 0, so this is 7. 1123 00:43:47,170 --> 00:43:52,005 1124 00:43:52,005 --> 00:43:52,505 AUDIENCE: 7. 1125 00:43:52,505 --> 00:43:56,855 1126 00:43:56,855 --> 00:43:57,355 11. 1127 00:43:57,355 --> 00:43:59,300 1128 00:43:59,300 --> 00:44:02,260 PROFESSOR: 7 or 4 plus 7. 1129 00:44:02,260 --> 00:44:08,504 1130 00:44:08,504 --> 00:44:09,920 Does this make sense for everyone? 1131 00:44:09,920 --> 00:44:12,160 1132 00:44:12,160 --> 00:44:13,035 Last column. 1133 00:44:13,035 --> 00:44:14,173 Let's do it. 1134 00:44:14,173 --> 00:44:14,672 AUDIENCE: 0. 1135 00:44:14,672 --> 00:44:15,594 Feels like 0. 1136 00:44:15,594 --> 00:44:19,131 1137 00:44:19,131 --> 00:44:19,630 0 again. 1138 00:44:19,630 --> 00:44:20,451 Why not? 1139 00:44:20,451 --> 00:44:21,864 1140 00:44:21,864 --> 00:44:23,277 4. 1141 00:44:23,277 --> 00:44:24,690 How much does this thing weigh? 1142 00:44:24,690 --> 00:44:25,394 AUDIENCE: 4. 1143 00:44:25,394 --> 00:44:25,894 AUDIENCE: 7. 1144 00:44:25,894 --> 00:44:31,196 1145 00:44:31,196 --> 00:44:32,170 10. 1146 00:44:32,170 --> 00:44:33,670 PROFESSOR: Sorry for my handwriting. 1147 00:44:33,670 --> 00:44:34,850 1148 00:44:34,850 --> 00:44:37,197 AUDIENCE: And it needs to be 11 because you 1149 00:44:37,197 --> 00:44:38,280 said that'd be the answer. 1150 00:44:38,280 --> 00:44:39,630 PROFESSOR: All right. 1151 00:44:39,630 --> 00:44:47,650 So it's 11 because it's either this guy or 10 plus DP of 1, 1. 1152 00:44:47,650 --> 00:44:52,380 1153 00:44:52,380 --> 00:44:53,970 The first item weighs 4, so I need 1154 00:44:53,970 --> 00:44:56,000 to look one right and four up when adding. 1155 00:44:56,000 --> 00:45:01,865 1156 00:45:01,865 --> 00:45:02,740 Does this make sense? 1157 00:45:02,740 --> 00:45:04,780 1158 00:45:04,780 --> 00:45:05,510 Please say yes. 1159 00:45:05,510 --> 00:45:08,510 1160 00:45:08,510 --> 00:45:10,510 AUDIENCE: What's the [INAUDIBLE] again? 1161 00:45:10,510 --> 00:45:12,250 1162 00:45:12,250 --> 00:45:14,840 I get how if you're looking horizontally, 1163 00:45:14,840 --> 00:45:16,590 the top thing is the max. 1164 00:45:16,590 --> 00:45:18,479 It's saying DP of i plus 1 j. 1165 00:45:18,479 --> 00:45:20,270 PROFESSOR: So this is looking horizontally, 1166 00:45:20,270 --> 00:45:22,050 and this means I did not take item i. 1167 00:45:22,050 --> 00:45:23,425 AUDIENCE: You didn't take item i, 1168 00:45:23,425 --> 00:45:26,250 but if you are going to take item i, you add the value of i, 1169 00:45:26,250 --> 00:45:29,841 and then you look back for DP of i plus 1, 1170 00:45:29,841 --> 00:45:37,765 which is the previous column, and the row number is whatever 1171 00:45:37,765 --> 00:45:41,405 capacity you have left if you did take it? 1172 00:45:41,405 --> 00:45:42,030 PROFESSOR: Yep. 1173 00:45:42,030 --> 00:45:47,907 AUDIENCE: And so in the case of cell 1, 1174 00:45:47,907 --> 00:45:56,977 3, if you took item one, then capacity you'd have left is 3. 1175 00:45:56,977 --> 00:45:58,260 1176 00:45:58,260 --> 00:45:59,103 PROFESSOR: Right. 1177 00:45:59,103 --> 00:46:01,050 So you said total capacity three, right? 1178 00:46:01,050 --> 00:46:03,680 1179 00:46:03,680 --> 00:46:06,410 So if I take item one, how many pounds does it have? 1180 00:46:06,410 --> 00:46:07,494 1181 00:46:07,494 --> 00:46:08,410 AUDIENCE: It has four. 1182 00:46:08,410 --> 00:46:10,460 1183 00:46:10,460 --> 00:46:12,831 PROFESSOR: Statue is 0, ball is 1, pen is 2. 1184 00:46:12,831 --> 00:46:13,372 AUDIENCE: Oh. 1185 00:46:13,372 --> 00:46:14,274 You're not using-- 1186 00:46:14,274 --> 00:46:15,201 1187 00:46:15,201 --> 00:46:16,700 PROFESSOR: So I'm using those items, 1188 00:46:16,700 --> 00:46:18,735 but I'm starting using zero based indexing. 1189 00:46:18,735 --> 00:46:21,350 AUDIENCE: Yeah, but we're going from here to here. 1190 00:46:21,350 --> 00:46:25,010 So I'm saying if you pick the middle cell that's 1191 00:46:25,010 --> 00:46:26,810 1, 3, that one-- 1192 00:46:26,810 --> 00:46:30,440 PROFESSOR: So this has item one, so the ball, weight three. 1193 00:46:30,440 --> 00:46:33,590 If I take the ball, how much weight do I have left? 1194 00:46:33,590 --> 00:46:34,690 1195 00:46:34,690 --> 00:46:38,070 AUDIENCE: The ball weighs two pounds, 1196 00:46:38,070 --> 00:46:40,399 so you'd have three pounds left, and that's 1197 00:46:40,399 --> 00:46:41,690 why you're in the three column. 1198 00:46:41,690 --> 00:46:43,760 PROFESSOR: I have a backpack of three pounds, 1199 00:46:43,760 --> 00:46:46,630 and then I put a ball of two pounds in it, 1200 00:46:46,630 --> 00:46:48,314 and I have three pounds left? 1201 00:46:48,314 --> 00:46:49,242 AUDIENCE: No, no, no. 1202 00:46:49,242 --> 00:46:52,490 You have three pounds left if you put a ball and two pounds 1203 00:46:52,490 --> 00:46:53,030 in, right? 1204 00:46:53,030 --> 00:46:54,076 1205 00:46:54,076 --> 00:46:55,950 PROFESSOR: I have a backpack of three pounds. 1206 00:46:55,950 --> 00:46:57,400 I put a ball of two pounds. 1207 00:46:57,400 --> 00:46:58,800 1208 00:46:58,800 --> 00:47:01,285 How many pounds do I have left of capacity? 1209 00:47:01,285 --> 00:47:06,210 1210 00:47:06,210 --> 00:47:11,395 So backpack, three pounds total. 1211 00:47:11,395 --> 00:47:13,110 I put a ball in that has two pounds. 1212 00:47:13,110 --> 00:47:14,740 How many pounds? 1213 00:47:14,740 --> 00:47:16,902 AUDIENCE: We have none left. 1214 00:47:16,902 --> 00:47:18,360 Oh, it can hold three total pounds? 1215 00:47:18,360 --> 00:47:18,790 PROFESSOR: Yeah. 1216 00:47:18,790 --> 00:47:20,638 AUDIENCE: Then you have one pound left. 1217 00:47:20,638 --> 00:47:22,630 But we have a five pound backpack. 1218 00:47:22,630 --> 00:47:25,364 PROFESSOR: Well, you said we were looking at 3, 1. 1219 00:47:25,364 --> 00:47:26,910 You said we were looking here. 1220 00:47:26,910 --> 00:47:28,410 AUDIENCE: Yeah, we're looking there. 1221 00:47:28,410 --> 00:47:31,930 PROFESSOR: So this means three pound backpack, 1222 00:47:31,930 --> 00:47:35,513 because the sub-problem says your weight is at most j. 1223 00:47:35,513 --> 00:47:36,479 AUDIENCE: Got it, OK. 1224 00:47:36,479 --> 00:47:37,445 Oh, I see. 1225 00:47:37,445 --> 00:47:38,894 1226 00:47:38,894 --> 00:47:41,480 So j minus si is saying-- 1227 00:47:41,480 --> 00:47:45,459 PROFESSOR: It means you used up, so you put up something there, 1228 00:47:45,459 --> 00:47:46,500 so you ate some capacity. 1229 00:47:46,500 --> 00:47:48,275 1230 00:47:48,275 --> 00:47:50,441 AUDIENCE: Well, you ate only two pounds, though, 1231 00:47:50,441 --> 00:47:53,780 so why is it in row three? 1232 00:47:53,780 --> 00:47:55,695 PROFESSOR: You told me to start here. 1233 00:47:55,695 --> 00:47:56,665 AUDIENCE: I know. 1234 00:47:56,665 --> 00:47:58,610 I'm trying to remember how we got there. 1235 00:47:58,610 --> 00:48:00,193 PROFESSOR: You said, let's start here. 1236 00:48:00,193 --> 00:48:01,430 1237 00:48:01,430 --> 00:48:04,110 That's why this arrow points here to one. 1238 00:48:04,110 --> 00:48:07,144 You have two arrows, 2, 3, and 2, 1. 1239 00:48:07,144 --> 00:48:08,560 AUDIENCE: Because it's j minus si. 1240 00:48:08,560 --> 00:48:10,000 AUDIENCE: Oh, I see. 1241 00:48:10,000 --> 00:48:10,980 Minus 3. 1242 00:48:10,980 --> 00:48:14,695 AUDIENCE: So j is the amount of weight you have left, right? 1243 00:48:14,695 --> 00:48:16,320 PROFESSOR: So j is the amount of weight 1244 00:48:16,320 --> 00:48:18,340 I can have for this sub-problem. 1245 00:48:18,340 --> 00:48:20,809 AUDIENCE: Yeah, the amount of capacity I 1246 00:48:20,809 --> 00:48:22,014 have still in my backpack. 1247 00:48:22,014 --> 00:48:27,537 1248 00:48:27,537 --> 00:48:29,620 PROFESSOR: Let's talk about pseudo polynomial time 1249 00:48:29,620 --> 00:48:31,410 very quickly and what does it mean, OK? 1250 00:48:31,410 --> 00:48:33,930 1251 00:48:33,930 --> 00:48:36,410 And you guys will promise to look at the recitation notes 1252 00:48:36,410 --> 00:48:38,460 and look at the other problems, right? 1253 00:48:38,460 --> 00:48:40,000 So incentive for that. 1254 00:48:40,000 --> 00:48:43,190 Problem two is easier than knapsack, 1255 00:48:43,190 --> 00:48:46,540 so if you get that, that should be a good confirmation that you 1256 00:48:46,540 --> 00:48:47,160 got knapsack. 1257 00:48:47,160 --> 00:48:49,340 Problem three is a bit harder than problem two, 1258 00:48:49,340 --> 00:48:51,710 but it shows up on interviews, so you 1259 00:48:51,710 --> 00:48:53,890 want to understand problem three. 1260 00:48:53,890 --> 00:48:56,700 I got problem two twice in four years, 1261 00:48:56,700 --> 00:48:59,351 so there's a decent chance that you'll get it. 1262 00:48:59,351 --> 00:49:00,850 So you want to get to problem three, 1263 00:49:00,850 --> 00:49:03,010 so you should go through problem two. 1264 00:49:03,010 --> 00:49:06,270 AUDIENCE: How many times have you got problem three? 1265 00:49:06,270 --> 00:49:08,010 PROFESSOR: Twice in four years, so that's 1266 00:49:08,010 --> 00:49:09,190 the problem that you want to get to. 1267 00:49:09,190 --> 00:49:10,790 Problem two is a stepping stone. 1268 00:49:10,790 --> 00:49:19,730 1269 00:49:19,730 --> 00:49:22,254 So running time for dynamic programming. 1270 00:49:22,254 --> 00:49:23,170 How many sub-problems? 1271 00:49:23,170 --> 00:49:25,984 1272 00:49:25,984 --> 00:49:26,922 AUDIENCE: Same, ns. 1273 00:49:26,922 --> 00:49:27,885 1274 00:49:27,885 --> 00:49:28,510 PROFESSOR: Yep. 1275 00:49:28,510 --> 00:49:29,789 1276 00:49:29,789 --> 00:49:30,330 Sub-problems. 1277 00:49:30,330 --> 00:49:35,320 1278 00:49:35,320 --> 00:49:38,207 How many sub-problems do I look at when 1279 00:49:38,207 --> 00:49:39,790 I compute the answer of a sub-problem? 1280 00:49:39,790 --> 00:49:40,906 1281 00:49:40,906 --> 00:49:42,020 Two, right? 1282 00:49:42,020 --> 00:49:43,080 So order one. 1283 00:49:43,080 --> 00:49:44,366 1284 00:49:44,366 --> 00:49:45,740 So this is how much time it takes 1285 00:49:45,740 --> 00:49:50,420 to compute the answer to a sub-problem, 1286 00:49:50,420 --> 00:49:52,170 because I have the max of two elements, 1287 00:49:52,170 --> 00:49:53,670 so it's constant time. 1288 00:49:53,670 --> 00:49:56,210 1289 00:49:56,210 --> 00:49:57,940 So the total running time is? 1290 00:49:57,940 --> 00:49:59,559 1291 00:49:59,559 --> 00:50:00,350 AUDIENCE: Order ns. 1292 00:50:00,350 --> 00:50:01,225 PROFESSOR: All right. 1293 00:50:01,225 --> 00:50:01,724 1294 00:50:01,724 --> 00:50:02,920 Order of ns. 1295 00:50:02,920 --> 00:50:07,280 1296 00:50:07,280 --> 00:50:09,039 This polynomial, is this the same kind 1297 00:50:09,039 --> 00:50:10,080 of algorithm as Dijkstra? 1298 00:50:10,080 --> 00:50:11,394 1299 00:50:11,394 --> 00:50:12,560 AUDIENCE: Pseudo polynomial. 1300 00:50:12,560 --> 00:50:13,370 PROFESSOR: Pseudo polynomial. 1301 00:50:13,370 --> 00:50:14,765 AUDIENCE: Don't know why. 1302 00:50:14,765 --> 00:50:23,707 1303 00:50:23,707 --> 00:50:25,290 PROFESSOR: So intuitively, the problem 1304 00:50:25,290 --> 00:50:29,570 is s shows up in your running here, 1305 00:50:29,570 --> 00:50:32,555 and s is the property of your input numbers. 1306 00:50:32,555 --> 00:50:33,730 1307 00:50:33,730 --> 00:50:36,160 It's not how many elements you have in the input. 1308 00:50:36,160 --> 00:50:38,065 It's what's inside one of those elements. 1309 00:50:38,065 --> 00:50:39,170 1310 00:50:39,170 --> 00:50:40,770 So let's see why that matters. 1311 00:50:40,770 --> 00:50:42,270 Let's look at the practical example. 1312 00:50:42,270 --> 00:50:45,406 1313 00:50:45,406 --> 00:50:47,322 AUDIENCE: What about measuring in cubic inches 1314 00:50:47,322 --> 00:50:48,562 or cubic centimeters? 1315 00:50:48,562 --> 00:50:50,546 1316 00:50:50,546 --> 00:50:53,026 Is that a problem? 1317 00:50:53,026 --> 00:50:56,282 It would take a lot longer if we do it in cubic centimeters. 1318 00:50:56,282 --> 00:50:57,740 PROFESSOR: Yeah, but then you could 1319 00:50:57,740 --> 00:51:00,569 argue that if it's an integer amount of cubic inches, 1320 00:51:00,569 --> 00:51:02,110 you should divide everything by that. 1321 00:51:02,110 --> 00:51:05,510 1322 00:51:05,510 --> 00:51:07,250 Where this really matters is suppose 1323 00:51:07,250 --> 00:51:14,780 you have a 100 item input, so 100 items. 1324 00:51:14,780 --> 00:51:16,830 1325 00:51:16,830 --> 00:51:19,880 What's the worst case input on a 32-bit machine? 1326 00:51:19,880 --> 00:51:25,780 1327 00:51:25,780 --> 00:51:27,880 An input looks like this, by the way. 1328 00:51:27,880 --> 00:51:34,860 How many elements you have, so 3, and then for each item, 1329 00:51:34,860 --> 00:51:36,750 what's the weight and what's the value? 1330 00:51:36,750 --> 00:51:38,160 1331 00:51:38,160 --> 00:51:41,200 So then we're going to have three weights, which I believe 1332 00:51:41,200 --> 00:51:46,210 are 4, 2, 3. 1333 00:51:46,210 --> 00:51:50,399 1334 00:51:50,399 --> 00:51:51,940 You guys have to take my word for it. 1335 00:51:51,940 --> 00:51:58,280 And then I have three values, which are 10, 4, 7. 1336 00:51:58,280 --> 00:52:02,830 1337 00:52:02,830 --> 00:52:04,207 Let's not worry about the values. 1338 00:52:04,207 --> 00:52:05,540 I claim that they're irrelevant. 1339 00:52:05,540 --> 00:52:07,130 You can convince yourselves afterwards 1340 00:52:07,130 --> 00:52:08,130 that that's the case. 1341 00:52:08,130 --> 00:52:09,810 1342 00:52:09,810 --> 00:52:11,860 Let's only look at this. 1343 00:52:11,860 --> 00:52:15,960 The weights have to be between 0 and what for the problem 1344 00:52:15,960 --> 00:52:17,051 to make sense? 1345 00:52:17,051 --> 00:52:17,550 AUDIENCE: 5. 1346 00:52:17,550 --> 00:52:19,082 1347 00:52:19,082 --> 00:52:21,040 PROFESSOR: If I have a weight bigger than this, 1348 00:52:21,040 --> 00:52:22,665 I know I'm not going to take that item. 1349 00:52:22,665 --> 00:52:23,490 1350 00:52:23,490 --> 00:52:26,736 How many bits do I need to represent these weights? 1351 00:52:26,736 --> 00:52:27,672 AUDIENCE: Log s. 1352 00:52:27,672 --> 00:52:28,932 1353 00:52:28,932 --> 00:52:30,640 PROFESSOR: It's log s plus 1 technically, 1354 00:52:30,640 --> 00:52:33,250 but if I write order of log s, I'm good. 1355 00:52:33,250 --> 00:52:36,321 1356 00:52:36,321 --> 00:52:37,820 AUDIENCE: Times the number of items. 1357 00:52:37,820 --> 00:52:38,750 PROFESSOR: Yes. 1358 00:52:38,750 --> 00:52:40,690 So if I want to represent all of them, 1359 00:52:40,690 --> 00:52:46,350 I have order of n times log s, plus the number 1360 00:52:46,350 --> 00:52:48,450 of bits required to represent this. 1361 00:52:48,450 --> 00:52:49,590 This is log n. 1362 00:52:49,590 --> 00:52:51,070 So log n is smaller than n. 1363 00:52:51,070 --> 00:52:53,020 I'm not going to add it here. 1364 00:52:53,020 --> 00:52:54,230 So this is my input size. 1365 00:52:54,230 --> 00:52:58,050 This is how many bits I need for the input. 1366 00:52:58,050 --> 00:52:59,730 1367 00:52:59,730 --> 00:53:02,260 So the worst case input on a 32-bit machine 1368 00:53:02,260 --> 00:53:10,340 is going to have roughly 3,200 bits. 1369 00:53:10,340 --> 00:53:13,310 What's the worst case s that I can 1370 00:53:13,310 --> 00:53:15,010 represent on a 32-bit machine? 1371 00:53:15,010 --> 00:53:16,520 1372 00:53:16,520 --> 00:53:19,584 These are all 32-bit numbers. 1373 00:53:19,584 --> 00:53:22,000 AUDIENCE: You mean each of the weights are 32-bit numbers? 1374 00:53:22,000 --> 00:53:22,666 PROFESSOR: Yeah. 1375 00:53:22,666 --> 00:53:28,040 1376 00:53:28,040 --> 00:53:31,015 So what's the worst case s I can represent? 1377 00:53:31,015 --> 00:53:32,470 AUDIENCE: 2 to 31 minus 1. 1378 00:53:32,470 --> 00:53:34,410 1379 00:53:34,410 --> 00:53:37,630 PROFESSOR: Which is roughly 4 times 10 to the ninth. 1380 00:53:37,630 --> 00:53:39,453 So the worst case running time is? 1381 00:53:39,453 --> 00:53:45,010 1382 00:53:45,010 --> 00:53:46,460 Roughly ns, right? 1383 00:53:46,460 --> 00:53:47,780 1384 00:53:47,780 --> 00:53:56,030 So n times s, which means roughly 100 times 10 1385 00:53:56,030 --> 00:53:59,996 to the ninth, which means 4 times 10 to the 11 operations. 1386 00:53:59,996 --> 00:54:10,330 1387 00:54:10,330 --> 00:54:12,370 Now, suppose we're looking at the worst case 1388 00:54:12,370 --> 00:54:13,880 input on a 64-bit machine. 1389 00:54:13,880 --> 00:54:20,690 1390 00:54:20,690 --> 00:54:22,240 Still 100 items. 1391 00:54:22,240 --> 00:54:23,717 What's the input size? 1392 00:54:23,717 --> 00:54:25,545 AUDIENCE: To the 21 total at the end. 1393 00:54:25,545 --> 00:54:26,162 1394 00:54:26,162 --> 00:54:27,745 PROFESSOR: That's how many operations. 1395 00:54:27,745 --> 00:54:30,366 1396 00:54:30,366 --> 00:54:31,740 Let's go through it step by step. 1397 00:54:31,740 --> 00:54:34,210 How many bits of input? 1398 00:54:34,210 --> 00:54:35,614 1399 00:54:35,614 --> 00:54:36,774 AUDIENCE: 6,400. 1400 00:54:36,774 --> 00:54:38,274 AUDIENCE: Where does that come from? 1401 00:54:38,274 --> 00:54:40,250 AUDIENCE: 100 items times 32 bits. 1402 00:54:40,250 --> 00:54:41,435 1403 00:54:41,435 --> 00:54:42,310 PROFESSOR: 100 items. 1404 00:54:42,310 --> 00:54:44,580 Each item weight has 64 bits. 1405 00:54:44,580 --> 00:54:46,110 What's the worst case s? 1406 00:54:46,110 --> 00:54:47,433 1407 00:54:47,433 --> 00:54:48,756 AUDIENCE: 2 to the 64. 1408 00:54:48,756 --> 00:54:51,160 PROFESSOR: 2 to the 64 minus 1. 1409 00:54:51,160 --> 00:54:52,240 Doesn't matter too much. 1410 00:54:52,240 --> 00:55:00,270 It's 1 times 10 to the 19th, 1.6 times 10 to the 19th. 1411 00:55:00,270 --> 00:55:02,041 So the worst case running time is? 1412 00:55:02,041 --> 00:55:05,478 1413 00:55:05,478 --> 00:55:06,933 AUDIENCE: 10 to the 21. 1414 00:55:06,933 --> 00:55:07,933 PROFESSOR: 10 to the 21. 1415 00:55:07,933 --> 00:55:15,192 1416 00:55:15,192 --> 00:55:15,900 So what happened? 1417 00:55:15,900 --> 00:55:17,240 I increased my word size. 1418 00:55:17,240 --> 00:55:18,350 1419 00:55:18,350 --> 00:55:20,655 The running time increased quadratically. 1420 00:55:20,655 --> 00:55:23,030 1421 00:55:23,030 --> 00:55:24,545 This is not a polynomial increase. 1422 00:55:24,545 --> 00:55:26,871 1423 00:55:26,871 --> 00:55:27,870 What's the problem here? 1424 00:55:27,870 --> 00:55:29,570 Why is this the case? 1425 00:55:29,570 --> 00:55:35,080 If I write log s as b, so log s becomes 1426 00:55:35,080 --> 00:55:38,180 b, what's the input size? 1427 00:55:38,180 --> 00:55:44,774 1428 00:55:44,774 --> 00:55:45,720 AUDIENCE: nb. 1429 00:55:45,720 --> 00:55:48,610 PROFESSOR: Yep. n times log s equals n times b, 1430 00:55:48,610 --> 00:55:49,790 so this is the input size. 1431 00:55:49,790 --> 00:55:51,091 1432 00:55:51,091 --> 00:55:52,340 Now, what is the running time? 1433 00:55:52,340 --> 00:55:57,322 1434 00:55:57,322 --> 00:55:58,780 AUDIENCE: The number of operations? 1435 00:55:58,780 --> 00:55:59,405 PROFESSOR: Yep. 1436 00:55:59,405 --> 00:56:04,148 1437 00:56:04,148 --> 00:56:05,460 AUDIENCE: n times 2 to the b. 1438 00:56:05,460 --> 00:56:06,230 PROFESSOR: Yep. 1439 00:56:06,230 --> 00:56:08,450 n times s, and s is 2 to the b. 1440 00:56:08,450 --> 00:56:12,590 1441 00:56:12,590 --> 00:56:13,710 So this is the problem. 1442 00:56:13,710 --> 00:56:15,200 1443 00:56:15,200 --> 00:56:18,250 This is a polynomial in n and b, but here, 1444 00:56:18,250 --> 00:56:21,460 if I write the input this way, I have b as an exponent. 1445 00:56:21,460 --> 00:56:22,510 1446 00:56:22,510 --> 00:56:24,520 So if I double the number of bits 1447 00:56:24,520 --> 00:56:28,120 by doubling the field size, my running time 1448 00:56:28,120 --> 00:56:30,870 increases quadratically, so this is not polynomial. 1449 00:56:30,870 --> 00:56:33,810 1450 00:56:33,810 --> 00:56:36,680 However, if I write it as order of n times s, 1451 00:56:36,680 --> 00:56:38,819 this looks like a polynomial. 1452 00:56:38,819 --> 00:56:40,860 So it looks like a polynomial, but it's not truly 1453 00:56:40,860 --> 00:56:44,920 a polynomial, so that's why it's pseudo, as in fake. 1454 00:56:44,920 --> 00:56:47,705 1455 00:56:47,705 --> 00:56:49,330 AUDIENCE: So it's actually exponential. 1456 00:56:49,330 --> 00:56:50,800 1457 00:56:50,800 --> 00:56:52,300 PROFESSOR: It's not exponential. 1458 00:56:52,300 --> 00:56:55,250 So an exponential algorithm for this means 1459 00:56:55,250 --> 00:56:58,060 try all the possible subsets, and that's 1460 00:56:58,060 --> 00:57:02,220 order of 2 to the n times n to compute the sum. 1461 00:57:02,220 --> 00:57:03,354 This is exponential, right? 1462 00:57:03,354 --> 00:57:04,020 You have n here. 1463 00:57:04,020 --> 00:57:05,120 It's clear. 1464 00:57:05,120 --> 00:57:07,140 AUDIENCE: I know, but if you have 2 to the b, 1465 00:57:07,140 --> 00:57:09,372 that seems pretty clear as well. 1466 00:57:09,372 --> 00:57:11,330 PROFESSOR: Well, you have to look inside this s 1467 00:57:11,330 --> 00:57:11,990 and see what it means. 1468 00:57:11,990 --> 00:57:12,906 That's the difference. 1469 00:57:12,906 --> 00:57:13,830 1470 00:57:13,830 --> 00:57:16,070 So by increasing the number of items, 1471 00:57:16,070 --> 00:57:18,030 if you double the number of items 1472 00:57:18,030 --> 00:57:20,410 but you don't do anything to the word size, 1473 00:57:20,410 --> 00:57:23,640 then your running time is going to increase polynomially, 1474 00:57:23,640 --> 00:57:25,210 but if you change the field size, 1475 00:57:25,210 --> 00:57:26,751 it's going to increase exponentially. 1476 00:57:26,751 --> 00:57:27,780 1477 00:57:27,780 --> 00:57:30,900 So pseudo polynomial means watch out, there's a trap. 1478 00:57:30,900 --> 00:57:32,110 It's not really polynomial. 1479 00:57:32,110 --> 00:57:36,862 If you increase the input size by increasing the number width, 1480 00:57:36,862 --> 00:57:38,070 bad stuff is going to happen. 1481 00:57:38,070 --> 00:57:39,290 1482 00:57:39,290 --> 00:57:40,165 So think of Dijkstra. 1483 00:57:40,165 --> 00:57:41,664 What's the running time of Dijkstra? 1484 00:57:41,664 --> 00:57:44,010 You count the number of vertices, the number of edges, 1485 00:57:44,010 --> 00:57:45,960 and you have a polynomial in that, right? 1486 00:57:45,960 --> 00:57:46,850 1487 00:57:46,850 --> 00:57:48,600 You don't have to look at the number size. 1488 00:57:48,600 --> 00:57:50,850 You don't have to look at any weird stuff like that. 1489 00:57:50,850 --> 00:57:52,154 Here, you do. 1490 00:57:52,154 --> 00:57:53,636 That's the difference. 1491 00:57:53,636 --> 00:57:57,120 1492 00:57:57,120 --> 00:57:58,240 Does it make more sense? 1493 00:57:58,240 --> 00:58:00,120 1494 00:58:00,120 --> 00:58:03,060 So whenever you have an input number that shows up 1495 00:58:03,060 --> 00:58:07,340 in your running time, instead of how many numbers you have, 1496 00:58:07,340 --> 00:58:08,627 that means there's a trap. 1497 00:58:08,627 --> 00:58:09,668 That's pseudo polynomial. 1498 00:58:09,668 --> 00:58:12,060 1499 00:58:12,060 --> 00:58:14,060 AUDIENCE: So it's just like having some constant 1500 00:58:14,060 --> 00:58:15,524 that depends on something? 1501 00:58:15,524 --> 00:58:17,150 1502 00:58:17,150 --> 00:58:18,625 PROFESSOR: It's not a constant. 1503 00:58:18,625 --> 00:58:20,020 AUDIENCE: I mean coefficient. 1504 00:58:20,020 --> 00:58:22,174 AUDIENCE: Once you set it, it's a constant, right? 1505 00:58:22,174 --> 00:58:23,062 1506 00:58:23,062 --> 00:58:25,270 PROFESSOR: I mean, that's true for everything, right? 1507 00:58:25,270 --> 00:58:28,170 You can say that you have 10 to the 80 atoms in the universe, 1508 00:58:28,170 --> 00:58:32,170 so all the numbers that you work with are at most 10 to the 80. 1509 00:58:32,170 --> 00:58:34,010 Therefore, your running time is order one 1510 00:58:34,010 --> 00:58:36,210 no matter what you do, and then running times 1511 00:58:36,210 --> 00:58:37,100 are no longer useful. 1512 00:58:37,100 --> 00:58:38,980 1513 00:58:38,980 --> 00:58:41,248 You have to draw a line somewhere. 1514 00:58:41,248 --> 00:58:43,948 AUDIENCE: I think it's just like s, if it depends on your field 1515 00:58:43,948 --> 00:58:46,837 size and you can scale it, it's kind of like-- 1516 00:58:46,837 --> 00:58:48,420 PROFESSOR: So asymptotic running time. 1517 00:58:48,420 --> 00:58:49,461 What's the point of that? 1518 00:58:49,461 --> 00:58:50,800 How do our algorithms scale? 1519 00:58:50,800 --> 00:58:53,230 As our data becomes bigger and bigger, 1520 00:58:53,230 --> 00:58:55,120 what happens to the running time? 1521 00:58:55,120 --> 00:58:56,870 This pseudo polynomial thing tells you 1522 00:58:56,870 --> 00:59:01,526 that if you're shifting to a larger number size, 1523 00:59:01,526 --> 00:59:03,400 to a larger word size, then your running time 1524 00:59:03,400 --> 00:59:04,330 is going to explode. 1525 00:59:04,330 --> 00:59:05,950 It's not going to scale linearly. 1526 00:59:05,950 --> 00:59:13,879 1527 00:59:13,879 --> 00:59:14,670 Still don't buy it? 1528 00:59:14,670 --> 00:59:19,089 1529 00:59:19,089 --> 00:59:20,562 AUDIENCE: I trust you, I just-- 1530 00:59:20,562 --> 00:59:25,963 1531 00:59:25,963 --> 00:59:28,665 AUDIENCE: So it's only dependent on the field in this case. 1532 00:59:28,665 --> 00:59:31,319 1533 00:59:31,319 --> 00:59:33,360 PROFESSOR: Do you guys want to look over Dijkstra 1534 00:59:33,360 --> 00:59:34,750 and see what the input to Dijkstra looks like 1535 00:59:34,750 --> 00:59:35,791 and why that's different? 1536 00:59:35,791 --> 00:59:38,904 Do you think that's worth your time, 1537 00:59:38,904 --> 00:59:40,320 given that this is what's standing 1538 00:59:40,320 --> 00:59:41,486 between you and the weekend? 1539 00:59:41,486 --> 00:59:42,400 1540 00:59:42,400 --> 00:59:44,470 AUDIENCE: What time is it? 1541 00:59:44,470 --> 00:59:47,405 PROFESSOR: If you guys want to, I'm willing to do it. 1542 00:59:47,405 --> 00:59:49,281 AUDIENCE: It's 4:07. 1543 00:59:49,281 --> 00:59:50,219 I'll stay. 1544 00:59:50,219 --> 00:59:51,300 1545 00:59:51,300 --> 00:59:53,680 PROFESSOR: Well, if you guys want to go, you can go. 1546 00:59:53,680 --> 00:59:55,577 I will draw this for the people who 1547 00:59:55,577 --> 00:59:57,160 still want to know what it looks like. 1548 00:59:57,160 --> 01:00:00,380 1549 01:00:00,380 --> 01:00:01,120 Dijkstra. 1550 01:00:01,120 --> 01:00:02,328 What's the input to Dijkstra? 1551 01:00:02,328 --> 01:00:03,420 1552 01:00:03,420 --> 01:00:04,590 It's a graph, right? 1553 01:00:04,590 --> 01:00:06,562 AUDIENCE: Yeah, nodes and edges. 1554 01:00:06,562 --> 01:00:10,582 1555 01:00:10,582 --> 01:00:12,290 PROFESSOR: What does the graph look like? 1556 01:00:12,290 --> 01:00:14,170 It's some number of nodes, so it's 1557 01:00:14,170 --> 01:00:18,120 a single number-- that's the number of nodes-- 1558 01:00:18,120 --> 01:00:20,190 that has log v bits in it. 1559 01:00:20,190 --> 01:00:21,270 1560 01:00:21,270 --> 01:00:27,670 And then for each edge, we have three numbers-- first vertex, 1561 01:00:27,670 --> 01:00:30,115 second vertex, and the weight. 1562 01:00:30,115 --> 01:00:31,710 1563 01:00:31,710 --> 01:00:33,940 What are the sizes of these numbers? 1564 01:00:33,940 --> 01:00:37,530 Log v, log v, and the last one? 1565 01:00:37,530 --> 01:00:38,844 1566 01:00:38,844 --> 01:00:39,720 AUDIENCE: Log w? 1567 01:00:39,720 --> 01:00:40,827 1568 01:00:40,827 --> 01:00:41,410 PROFESSOR: OK. 1569 01:00:41,410 --> 01:00:42,160 And what's w? 1570 01:00:42,160 --> 01:00:43,825 1571 01:00:43,825 --> 01:00:45,100 AUDIENCE: Maximum weight. 1572 01:00:45,100 --> 01:00:45,766 PROFESSOR: Yeah. 1573 01:00:45,766 --> 01:00:52,670 1574 01:00:52,670 --> 01:00:55,160 So this is a property of the field size, right? 1575 01:00:55,160 --> 01:00:59,797 1576 01:00:59,797 --> 01:01:00,880 Let's look at v, actually. 1577 01:01:00,880 --> 01:01:03,160 So we have E edges here, right? 1578 01:01:03,160 --> 01:01:04,730 1579 01:01:04,730 --> 01:01:13,720 So the input size is going to be log v bits plus E times log v 1580 01:01:13,720 --> 01:01:16,070 plus log w. 1581 01:01:16,070 --> 01:01:20,426 1582 01:01:20,426 --> 01:01:22,850 AUDIENCE: How did you get that? 1583 01:01:22,850 --> 01:01:25,860 PROFESSOR: Because I have the edges, so I have E of these. 1584 01:01:25,860 --> 01:01:29,510 I only have one vertex count, but then I have E edges, 1585 01:01:29,510 --> 01:01:31,880 and each edge has three numbers, and these 1586 01:01:31,880 --> 01:01:33,456 are the widths of the numbers. 1587 01:01:33,456 --> 01:01:35,905 AUDIENCE: Is the adjacent edges to v? 1588 01:01:35,905 --> 01:01:37,690 Is that right? 1589 01:01:37,690 --> 01:01:39,020 You say you have E edges. 1590 01:01:39,020 --> 01:01:40,520 PROFESSOR: I'm assuming it's a list, 1591 01:01:40,520 --> 01:01:42,040 so the most compact representation 1592 01:01:42,040 --> 01:01:47,110 of edges, I think-- or it might be a reasonably 1593 01:01:47,110 --> 01:01:50,400 compact representation is that you have the list of edges. 1594 01:01:50,400 --> 01:01:52,530 So you have a graph that has five nodes, 1595 01:01:52,530 --> 01:01:56,340 and then you have an edge that goes from 1 to 2, 1596 01:01:56,340 --> 01:02:01,809 and then weight 3, an edge that goes from 1 to 5, weight 4. 1597 01:02:01,809 --> 01:02:03,600 AUDIENCE: If you use a number, it's not a-- 1598 01:02:03,600 --> 01:02:05,849 PROFESSOR: Well, do I need anything else for vertices? 1599 01:02:05,849 --> 01:02:07,560 Not really, right? 1600 01:02:07,560 --> 01:02:11,990 AUDIENCE: So v1 and v2 are neighbors of capital V? 1601 01:02:11,990 --> 01:02:15,230 PROFESSOR: So v1, v2, w, these are the first edge. 1602 01:02:15,230 --> 01:02:16,975 1603 01:02:16,975 --> 01:02:20,300 Each edge has these fields. 1604 01:02:20,300 --> 01:02:22,110 1605 01:02:22,110 --> 01:02:25,280 AUDIENCE: This is the entire graph in one thing. 1606 01:02:25,280 --> 01:02:28,380 PROFESSOR: This is the entire graph as a list of numbers, 1607 01:02:28,380 --> 01:02:30,110 and this is how many bits it takes 1608 01:02:30,110 --> 01:02:32,427 to represent the graph in a reasonably 1609 01:02:32,427 --> 01:02:33,385 compact representation. 1610 01:02:33,385 --> 01:02:38,380 1611 01:02:38,380 --> 01:02:46,550 Now let's say little v is log v, little w is log w. 1612 01:02:46,550 --> 01:02:51,755 So then this is order of how many bits do I have here? 1613 01:02:51,755 --> 01:02:55,010 1614 01:02:55,010 --> 01:03:04,800 E times v plus w plus v. I just replaced the logs 1615 01:03:04,800 --> 01:03:06,092 with these variables. 1616 01:03:06,092 --> 01:03:15,520 1617 01:03:15,520 --> 01:03:17,180 This is how many bits. 1618 01:03:17,180 --> 01:03:19,160 Now, how many operations does Dijkstra take? 1619 01:03:19,160 --> 01:03:20,159 What's the running time? 1620 01:03:20,159 --> 01:03:22,295 1621 01:03:22,295 --> 01:03:24,630 AUDIENCE: Well, it depends on-- 1622 01:03:24,630 --> 01:03:25,690 AUDIENCE: E log v. 1623 01:03:25,690 --> 01:03:27,864 AUDIENCE: Wouldn't it be E plus v? 1624 01:03:27,864 --> 01:03:29,690 That's the fastest one, right? 1625 01:03:29,690 --> 01:03:33,270 But I think practically, it's only going to be-- 1626 01:03:33,270 --> 01:03:34,855 PROFESSOR: So this is E plus v log 1627 01:03:34,855 --> 01:03:36,230 v, the fastest theoretical limit. 1628 01:03:36,230 --> 01:03:37,280 1629 01:03:37,280 --> 01:03:43,720 This is still smaller than E log v. This 1630 01:03:43,720 --> 01:03:45,630 is going to make my life easier. 1631 01:03:45,630 --> 01:03:47,060 So this is smaller than this. 1632 01:03:47,060 --> 01:03:49,410 1633 01:03:49,410 --> 01:03:53,238 If this thing is polynomial, this is polynomial for sure. 1634 01:03:53,238 --> 01:03:55,720 1635 01:03:55,720 --> 01:04:06,760 E log v is E times little v. So how many bits in the input? 1636 01:04:06,760 --> 01:04:08,730 E times v plus w. 1637 01:04:08,730 --> 01:04:09,980 How many operations? 1638 01:04:09,980 --> 01:04:13,220 E times v. Any exponential anywhere here? 1639 01:04:13,220 --> 01:04:17,870 1640 01:04:17,870 --> 01:04:20,060 AUDIENCE: Wouldn't you change the size of v? 1641 01:04:20,060 --> 01:04:26,900 1642 01:04:26,900 --> 01:04:27,870 That looks fine. 1643 01:04:27,870 --> 01:04:31,270 1644 01:04:31,270 --> 01:04:35,270 PROFESSOR: Well, so there is a trick that v is 2 to the v, 1645 01:04:35,270 --> 01:04:36,230 right? 1646 01:04:36,230 --> 01:04:37,700 So you can say that this is order 1647 01:04:37,700 --> 01:04:45,380 of-- so this is definitely bigger than 2 1648 01:04:45,380 --> 01:04:48,230 to the little v times v, but then you 1649 01:04:48,230 --> 01:04:49,610 have the same thing in the input. 1650 01:04:49,610 --> 01:04:53,830 So the input also has at least 2 to the little v times v bits. 1651 01:04:53,830 --> 01:04:56,320 1652 01:04:56,320 --> 01:04:57,690 But don't worry about that. 1653 01:04:57,690 --> 01:04:58,477 That's too much. 1654 01:04:58,477 --> 01:05:00,810 The point is if you're worrying about this, don't worry. 1655 01:05:00,810 --> 01:05:02,000 The math still works out. 1656 01:05:02,000 --> 01:05:03,680 1657 01:05:03,680 --> 01:05:06,300 So whatever you have here as an input, 1658 01:05:06,300 --> 01:05:08,250 the running time is going to be a polynomial 1659 01:05:08,250 --> 01:05:09,350 in the size of the input. 1660 01:05:09,350 --> 01:05:12,190 1661 01:05:12,190 --> 01:05:14,680 What happens if you double the word size? 1662 01:05:14,680 --> 01:05:17,354 What happens if you have bigger weights? 1663 01:05:17,354 --> 01:05:19,674 AUDIENCE: Everything like v is multiplied by 2, 1664 01:05:19,674 --> 01:05:22,755 and w is multiplied by 2 and everything in this problem, 1665 01:05:22,755 --> 01:05:23,255 right? 1666 01:05:23,255 --> 01:05:26,410 1667 01:05:26,410 --> 01:05:28,470 PROFESSOR: So if you're doubling the word size, 1668 01:05:28,470 --> 01:05:32,141 then this is going to double, this is going to double. 1669 01:05:32,141 --> 01:05:32,890 Everything's fine. 1670 01:05:32,890 --> 01:05:35,740 1671 01:05:35,740 --> 01:05:38,680 What if you double the size of the weights? 1672 01:05:38,680 --> 01:05:41,070 1673 01:05:41,070 --> 01:05:43,550 AUDIENCE: That only adds an extra bit. 1674 01:05:43,550 --> 01:05:44,300 PROFESSOR: Sorry. 1675 01:05:44,300 --> 01:05:46,300 So if you double the size of the weight numbers? 1676 01:05:46,300 --> 01:05:47,730 1677 01:05:47,730 --> 01:05:50,810 So if you move from 32-bit weights to 64-bit weights? 1678 01:05:50,810 --> 01:05:52,746 1679 01:05:52,746 --> 01:05:54,807 AUDIENCE: That's still a constant factor, right? 1680 01:05:54,807 --> 01:05:56,640 PROFESSOR: What happens to the running time? 1681 01:05:56,640 --> 01:05:57,400 AUDIENCE: Nothing. 1682 01:05:57,400 --> 01:05:58,191 PROFESSOR: Nothing. 1683 01:05:58,191 --> 01:05:59,600 1684 01:05:59,600 --> 01:06:01,500 w does not show up in Dijkstra. 1685 01:06:01,500 --> 01:06:03,250 1686 01:06:03,250 --> 01:06:05,730 If it would, then we'd be trouble. 1687 01:06:05,730 --> 01:06:07,704 It wouldn't be polynomial anymore. 1688 01:06:07,704 --> 01:06:09,162 AUDIENCE: But practically, you will 1689 01:06:09,162 --> 01:06:10,744 be accessing that number, right? 1690 01:06:10,744 --> 01:06:12,160 PROFESSOR: Yeah, but that shows up 1691 01:06:12,160 --> 01:06:13,860 in the cost of one operation. 1692 01:06:13,860 --> 01:06:14,344 1693 01:06:14,344 --> 01:06:16,385 That's why I'm saying this is how many operations 1694 01:06:16,385 --> 01:06:18,625 you do, how many arithmetic operations. 1695 01:06:18,625 --> 01:06:19,780 1696 01:06:19,780 --> 01:06:21,957 Then the model of computation that we use is RAM, 1697 01:06:21,957 --> 01:06:23,540 and that says that you can do any math 1698 01:06:23,540 --> 01:06:24,770 operation in order one. 1699 01:06:24,770 --> 01:06:27,838 1700 01:06:27,838 --> 01:06:28,754 AUDIENCE: [INAUDIBLE]. 1701 01:06:28,754 --> 01:06:30,250 1702 01:06:30,250 --> 01:06:33,140 PROFESSOR: So here, my number in the input, 1703 01:06:33,140 --> 01:06:35,621 s, which is the size of a weight, 1704 01:06:35,621 --> 01:06:36,870 showed up in the running time. 1705 01:06:36,870 --> 01:06:38,366 1706 01:06:38,366 --> 01:06:39,824 AUDIENCE: Oh, the size of the input 1707 01:06:39,824 --> 01:06:40,700 showed up in the running time. 1708 01:06:40,700 --> 01:06:42,449 PROFESSOR: So the size of the input is OK, 1709 01:06:42,449 --> 01:06:45,404 but one number in the input showed up, 1710 01:06:45,404 --> 01:06:46,820 whereas here, that's not the case. 1711 01:06:46,820 --> 01:06:51,636 The weights do not show up in the running time. 1712 01:06:51,636 --> 01:06:53,094 1713 01:06:53,094 --> 01:06:55,524 AUDIENCE: So why don't we just always run Dijkstra, then? 1714 01:06:55,524 --> 01:06:56,581 1715 01:06:56,581 --> 01:06:58,830 PROFESSOR: Actually for this problem, for the knapsack 1716 01:06:58,830 --> 01:07:02,140 problem, you can't find an algorithm that is polynomial. 1717 01:07:02,140 --> 01:07:04,120 If you do, there's a $1 million prize for it 1718 01:07:04,120 --> 01:07:06,040 because you just proved that p equals mp. 1719 01:07:06,040 --> 01:07:10,040 1720 01:07:10,040 --> 01:07:12,260 This is the best we can do for knapsack. 1721 01:07:12,260 --> 01:07:14,748 AUDIENCE: Is counting sort pseudo linear, 1722 01:07:14,748 --> 01:07:20,840 because you need to have a maximum, a range? 1723 01:07:20,840 --> 01:07:21,920 Does that make sense? 1724 01:07:21,920 --> 01:07:23,074 1725 01:07:23,074 --> 01:07:24,115 PROFESSOR: Counting sort. 1726 01:07:24,115 --> 01:07:25,790 1727 01:07:25,790 --> 01:07:27,810 AUDIENCE: Depends on your range. 1728 01:07:27,810 --> 01:07:31,430 PROFESSOR: Yeah, but the range shows up under a log. 1729 01:07:31,430 --> 01:07:33,020 You're allowed to have logs. 1730 01:07:33,020 --> 01:07:34,340 You're allowed to have log w. 1731 01:07:34,340 --> 01:07:35,548 You're not allowed to have w. 1732 01:07:35,548 --> 01:07:40,164 1733 01:07:40,164 --> 01:07:41,830 It's dependent on the size of the input. 1734 01:07:41,830 --> 01:07:44,730 If you double the number size, then you're 1735 01:07:44,730 --> 01:07:48,930 going to have twice as many rounds, 1736 01:07:48,930 --> 01:07:51,104 but you don't have an exponential number of rounds. 1737 01:07:51,104 --> 01:07:53,560 1738 01:07:53,560 --> 01:07:54,060 Sorry. 1739 01:07:54,060 --> 01:07:55,500 You're thinking of counting sort. 1740 01:07:55,500 --> 01:07:56,490 I thought radix sort. 1741 01:07:56,490 --> 01:07:58,031 Radix sort doesn't matter because you 1742 01:07:58,031 --> 01:08:00,699 assume we can do everything in-- never mind. 1743 01:08:00,699 --> 01:08:01,990 You're right for counting sort. 1744 01:08:01,990 --> 01:08:04,900 1745 01:08:04,900 --> 01:08:05,400 Sorry. 1746 01:08:05,400 --> 01:08:06,750 You're right for counting sort. 1747 01:08:06,750 --> 01:08:07,250 Sorry. 1748 01:08:07,250 --> 01:08:09,330 I was confusing counting sort with radix sort. 1749 01:08:09,330 --> 01:08:13,520 So for counting sort, yeah, it's not linear. 1750 01:08:13,520 --> 01:08:15,500 It's linear in your range size, which 1751 01:08:15,500 --> 01:08:19,350 is not linear in the input size, which 1752 01:08:19,350 --> 01:08:21,217 is why we don't do counting sort. 1753 01:08:21,217 --> 01:08:22,681 We do radix sort. 1754 01:08:22,681 --> 01:08:25,609 1755 01:08:25,609 --> 01:08:27,863 AUDIENCE: We do counting sort in radix sort? 1756 01:08:27,863 --> 01:08:28,529 PROFESSOR: Yeah. 1757 01:08:28,529 --> 01:08:31,738 But radix sort limits the size of the range, right? 1758 01:08:31,738 --> 01:08:33,029 That's the point of radix sort. 1759 01:08:33,029 --> 01:08:33,570 AUDIENCE: Oh. 1760 01:08:33,570 --> 01:08:35,290 I see what you're thinking. 1761 01:08:35,290 --> 01:08:37,640 So doing counting sort with each number? 1762 01:08:37,640 --> 01:08:39,520 AUDIENCE: Right, with really big numbers, 1763 01:08:39,520 --> 01:08:40,930 taking a really long time. 1764 01:08:40,930 --> 01:08:43,290 AUDIENCE: Yeah, that would take a long time. 1765 01:08:43,290 --> 01:08:44,090 PROFESSOR: Yep. 1766 01:08:44,090 --> 01:08:45,010 That is very true. 1767 01:08:45,010 --> 01:08:48,818 If you try to do pure counting sort on 64-bit numbers, 1768 01:08:48,818 --> 01:08:50,109 you're going to run out of RAM. 1769 01:08:50,109 --> 01:08:55,352 1770 01:08:55,352 --> 01:08:57,490 Does this make some sense? 1771 01:08:57,490 --> 01:08:59,200 1772 01:08:59,200 --> 01:08:59,700 OK. 1773 01:08:59,700 --> 01:09:00,729 1774 01:09:00,729 --> 01:09:04,608 Promise to look over the other problems, and in return, 1775 01:09:04,608 --> 01:09:06,649 given that I didn't have time to cover them here, 1776 01:09:06,649 --> 01:09:08,170 I promise to answer any emails you 1777 01:09:08,170 --> 01:09:09,849 guys might ask me over the weekend. 1778 01:09:09,849 --> 01:09:10,390 AUDIENCE: Oh. 1779 01:09:10,390 --> 01:09:11,940 Awesome.