1 00:00:02,040 --> 00:00:06,653 So the plan for this video is to develop a greedy algorithm that always minimizes 2 00:00:06,653 --> 00:00:10,085 the waited sum of completion times of a given set of in jobs. 3 00:00:10,085 --> 00:00:14,699 But more than the specific problem, more than the specific algorithm I want you to 4 00:00:14,699 --> 00:00:18,183 focus on the process by which we arrive. At this greedy algorithm. 5 00:00:18,183 --> 00:00:21,883 because I think this process is really something which you can use yourself, in 6 00:00:21,883 --> 00:00:24,793 your own applications. The process we're going to use is we're 7 00:00:24,793 --> 00:00:28,049 going to first look at just a special case in the problem, where it's 8 00:00:28,049 --> 00:00:31,009 reasonably intuitive what should be the optimal thing to do. 9 00:00:31,009 --> 00:00:34,808 Looking at these special cases will then motivate a couple of natural greedy 10 00:00:34,808 --> 00:00:37,225 algorithms. Then, we'll figure out how to narrow a 11 00:00:37,225 --> 00:00:41,172 couple of greedy algorithms down to just a single candidate, and that in fact, as 12 00:00:41,172 --> 00:00:44,280 we will prove in the following lectures, will always be correct. 13 00:00:44,280 --> 00:00:47,250 So let's just briefly recall what is it we're trying to do. 14 00:00:47,250 --> 00:00:52,315 The computational problem and instant to specify by end jobs which come along with 15 00:00:52,315 --> 00:00:56,831 waits and links, and among all end factorial ways that we can sequence the 16 00:00:56,831 --> 00:01:01,347 jobs, we want to somehow home in on the one that minimizes the sum of waited 17 00:01:01,347 --> 00:01:04,826 completion times. Recall from the previous video that the 18 00:01:04,826 --> 00:01:09,525 completion time of a job is just the amount of time that elapses before it's 19 00:01:09,525 --> 00:01:12,088 done. So that's going to be the length of all 20 00:01:12,088 --> 00:01:15,140 the previous jobs plus the length of job J itself. 21 00:01:15,140 --> 00:01:19,840 What we're hoping is going to work out is that we can devise a greedy algorithm 22 00:01:19,840 --> 00:01:23,478 that always solves this problem. So maybe I should take a step back and 23 00:01:23,478 --> 00:01:27,180 ask, you know why do greedy algorithms seem like a sensible way to approach this 24 00:01:27,180 --> 00:01:28,708 scheduling problem? Well, you know. 25 00:01:28,708 --> 00:01:31,299 In general, greedy algorithms are not guaranteed to work. 26 00:01:31,299 --> 00:01:33,428 You may have to do something more complicated. 27 00:01:33,428 --> 00:01:36,251 But scheduling still seems like a good place to try them out. 28 00:01:36,251 --> 00:01:39,768 Remember what a greedy algorithm does, it iteratively makes myopic decisions. 29 00:01:39,768 --> 00:01:42,730 An then you hope you have a, a reasonably good result at the end. 30 00:01:42,730 --> 00:01:45,414 Now, what are we doing? We're studying a sequencing problem. 31 00:01:45,414 --> 00:01:48,774 The definition of the problem is to schedule a job then another job then 32 00:01:48,774 --> 00:01:52,409 another job all the way up to the last job and so this iterative nature of the 33 00:01:52,409 --> 00:01:55,952 solution suggests that at least if you're lucky if the problem is simple enough 34 00:01:55,952 --> 00:01:59,633 maybe there's a greedy algorithm which simply schedules the jobs in the correct 35 00:01:59,633 --> 00:02:02,892 order one at a time. So, we're going to see if that works for 36 00:02:02,892 --> 00:02:05,300 minimizing the sum of waited completion times. 37 00:02:05,300 --> 00:02:08,089 So let's start by thinking positive, being optimistic. 38 00:02:08,089 --> 00:02:12,036 So let's pause it that the greedy algorithm does exist for this problem. 39 00:02:12,036 --> 00:02:16,352 Given that we're in the greedy algortihm section of the course you're, probably 40 00:02:16,352 --> 00:02:18,405 you'll going to find this hard to believe. 41 00:02:18,405 --> 00:02:21,405 But suppose one existed, how would we discover what it is? 42 00:02:21,405 --> 00:02:25,668 Well a useful technique not just for this problem but, you know more generally in 43 00:02:25,668 --> 00:02:29,352 real life, first focus on some special cases of the problem, where it's 44 00:02:29,352 --> 00:02:33,563 relatively clear how you should proceed. And the two special cases I want you to 45 00:02:33,563 --> 00:02:37,826 think about for this problem are first of all, suppose I told you all of the jobs 46 00:02:37,826 --> 00:02:42,175 had exactly the same length but they had different weights, then, what order do 47 00:02:42,175 --> 00:02:44,992 you think it makes sense to schedule the jobs in? 48 00:02:44,992 --> 00:02:49,305 Secondly, suppose that I told you, that all of the jobs had exactly the same 49 00:02:49,305 --> 00:02:53,962 weight, but they had different lengths. Then, what order do you think you should 50 00:02:53,962 --> 00:03:06,213 schedule the jobs in? So first if all the jobs have the same 51 00:03:06,213 --> 00:03:08,795 length, you should prefer jobs with larger weights. 52 00:03:08,795 --> 00:03:12,772 Certainely, eh, this intuitively jives with our semantics of weights, that says 53 00:03:12,772 --> 00:03:16,541 more importance, which suggest that higher weight jobs should go first, if 54 00:03:16,541 --> 00:03:20,001 you look at the actual formula of minimizing the sum of weight and 55 00:03:20,001 --> 00:03:22,790 completion times, if the jobs all have the same length. 56 00:03:22,790 --> 00:03:26,592 Then the completion times are going to be the same your going to see the same set 57 00:03:26,592 --> 00:03:28,864 of them. If all the jobs have length one, then the 58 00:03:28,864 --> 00:03:32,528 completion times of the jobs are going to be one, two, three, four all the way up 59 00:03:32,528 --> 00:03:34,386 to N. No matter what sequence you use. 60 00:03:34,386 --> 00:03:38,502 So to make this as small as possible, you want the highest waits to be associated 61 00:03:38,502 --> 00:03:42,416 with the smallest completion times that is, you want them upfront as early as 62 00:03:42,416 --> 00:03:44,906 possible. The second special case where jobs have 63 00:03:44,906 --> 00:03:48,159 equal waits but varying lengths, I think is a little more subtle. 64 00:03:48,159 --> 00:03:52,123 Here what you want to do is you always want to favor small jobs, jobs with the 65 00:03:52,123 --> 00:03:54,410 smallest lengths, everything else being equal. 66 00:03:54,410 --> 00:03:58,475 The reason for that is that scheduling a job at a given position forces all the 67 00:03:58,475 --> 00:04:00,712 other jobs to wait for that job to complete. 68 00:04:00,712 --> 00:04:04,879 So all the, so whatever job you schedule first has a negative impact on all of the 69 00:04:04,879 --> 00:04:06,760 rest of the N minus one jobs. So I'll. 70 00:04:06,760 --> 00:04:11,065 Things being equal, you want the smallest job there that minimizes the consequences 71 00:04:11,065 --> 00:04:14,956 for the jobs that are to follow. If you find this a little unintuitive, I 72 00:04:14,956 --> 00:04:17,343 suggest just looking at a very simple example. 73 00:04:17,343 --> 00:04:19,943 Two jobs. Both have weight one, one has length one, 74 00:04:19,943 --> 00:04:22,876 one has length two. If you schedule the small job first 75 00:04:22,876 --> 00:04:27,143 you'll have completion times of one and three for a total of four but if you 76 00:04:27,143 --> 00:04:31,410 schedule the bigger job first you get completion times of two and three for the 77 00:04:31,410 --> 00:04:35,295 bigger sum of completion times of five. So the next step is to move beyond 78 00:04:35,295 --> 00:04:39,217 special cases, which we understand well. To the general case, which perhaps we 79 00:04:39,217 --> 00:04:41,848 don't understand. So suppose all of the weights are 80 00:04:41,848 --> 00:04:44,274 different, and all of the lengths are different. 81 00:04:44,274 --> 00:04:48,143 Well, if we have two jobs, and both of these rules of thumb give us the same 82 00:04:48,143 --> 00:04:51,136 advice, we're good. If there's one job which is both higher 83 00:04:51,136 --> 00:04:54,954 weight, and smaller than another job, then clearly that job should go first. 84 00:04:54,954 --> 00:04:58,876 But what if our two rules of thumb to prefer high weight jobs and to prefer 85 00:04:58,876 --> 00:05:02,952 small jobs, give us conflicting advice. What if we have a pair of jobs, where one 86 00:05:02,952 --> 00:05:07,028 of them is on the one hand higher weight, higher priority but on the other hand, 87 00:05:07,028 --> 00:05:09,778 bigger than the other one. Which one should go first? 88 00:05:09,778 --> 00:05:14,043 Well let's again stay positive, and let's try to think about the simplest kind of 89 00:05:14,043 --> 00:05:18,045 algorithm that could conceivably work. It won't be a guarantee that it works, 90 00:05:18,045 --> 00:05:20,625 but it might work. So we have these two different 91 00:05:20,625 --> 00:05:23,942 parameters, length and weights. Maybe we can aggregate these two 92 00:05:23,942 --> 00:05:28,049 parameters into a single one, into a single sort of score for each of the jobs 93 00:05:28,049 --> 00:05:32,103 so that if we schedule the jobs from high score to low score, we'll always be 94 00:05:32,103 --> 00:05:33,788 optimal. That would be great. 95 00:05:33,788 --> 00:05:37,948 If we could compile these two numbers into one for each job, and then just sort 96 00:05:37,948 --> 00:05:40,321 and be done. There is of course the question of 97 00:05:40,321 --> 00:05:42,858 exactly how do we choose this aggregation function. 98 00:05:42,858 --> 00:05:45,693 How do we compile length and weight into a single number. 99 00:05:45,693 --> 00:05:49,772 Well as guidelines we should recall our special case and make sure we respect our 100 00:05:49,772 --> 00:05:52,707 two rules of thumb. So all else being equal we should prefer 101 00:05:52,707 --> 00:05:55,841 jobs with higher weight. So that says higher weight should meet 102 00:05:55,841 --> 00:05:59,622 the higher scores if we're going to schedule the job from high score to low 103 00:05:59,622 --> 00:06:02,109 score. And then also if a length is bigger that 104 00:06:02,109 --> 00:06:05,328 should decrease the score. We should prefer jobs that have a small 105 00:06:05,328 --> 00:06:07,454 length. So this idea leaves open the question of 106 00:06:07,454 --> 00:06:10,864 exactly how do we aggregate the length and the weight of a job into a single 107 00:06:10,864 --> 00:06:12,901 number. So what I want you to do now is I want 108 00:06:12,901 --> 00:06:16,577 you to think for a minute about what kind of simplest possible functions you could 109 00:06:16,577 --> 00:06:18,171 use. So again, these are mathematical 110 00:06:18,171 --> 00:06:20,385 functions. They take as input two numbers, a length 111 00:06:20,385 --> 00:06:23,131 and a weight of a job, and they output a single number, a score. 112 00:06:23,131 --> 00:06:26,320 And the function should have the properties that it's increasing in the 113 00:06:26,320 --> 00:06:28,667 job's weight, and it's decreasing in the job's length. 114 00:06:28,667 --> 00:06:32,298 So there's more than one answer to this question but just sort of dream some sort 115 00:06:32,298 --> 00:06:34,380 of ideas of what this function might look like. 116 00:06:40,480 --> 00:06:44,339 Alright so there is certainly any number of functions that have these properties, 117 00:06:44,339 --> 00:06:48,008 but I'm just going to write down for concreteness two of what I think are of 118 00:06:48,008 --> 00:06:50,533 the simplest functions that have these properties. 119 00:06:50,533 --> 00:06:54,488 So one is going to be based on taking the difference of the two numbers and one is 120 00:06:54,488 --> 00:06:57,204 going to be based on taking the ratio of the two numbers. 121 00:06:57,204 --> 00:07:00,539 So if you're going to use a function based on the difference, then you're want 122 00:07:00,539 --> 00:07:03,208 to be increasing in the way of decreasing the length. 123 00:07:03,208 --> 00:07:07,019 Then of course, the obvious difference to use is weight minus length, this can be 124 00:07:07,019 --> 00:07:10,688 negative sometimes but that doesn't bother us the algorithm is still well 125 00:07:10,688 --> 00:07:13,318 defined. And if you're going to use a ratio and 126 00:07:13,318 --> 00:07:17,815 you want it to be increasing in weight, decreasing in length, then the sensible 127 00:07:17,815 --> 00:07:21,678 ratio to use is, the weight of a job, divided by the length of a job. 128 00:07:21,678 --> 00:07:26,060 It is of course possible that you have ties for either one of these scoring 129 00:07:26,060 --> 00:07:29,520 functions, so let's just allow ties to be broken arbitrarely. 130 00:07:29,520 --> 00:07:33,774 Now, what we're seeing here is a concrete instantiation of something I promised you 131 00:07:33,774 --> 00:07:37,772 in our high level discussion of greedy algorithms, namely, it's both a strength 132 00:07:37,772 --> 00:07:41,667 and a weakness of them that they're really easy to come up with and propose. 133 00:07:41,667 --> 00:07:45,460 So here we have just, you know, this one simple problem, and we now have two 134 00:07:45,460 --> 00:07:48,228 different, competing greedy algorithms for the problem. 135 00:07:48,228 --> 00:07:51,150 Now, because these two algorithms don't do the same thing. 136 00:07:51,150 --> 00:07:54,070 Only one of them, at most, can be always correct. 137 00:07:54,070 --> 00:07:56,991 At least one of them has to be wrong sometimes. 138 00:07:56,991 --> 00:08:00,285 So, as the algorithm designer, what the process now is. 139 00:08:00,285 --> 00:08:05,132 Maybe we can rule out at least one of these two proposed greedy algorithms, by 140 00:08:05,132 --> 00:08:08,550 showing an example where it doesn't do the right thing. 141 00:08:08,550 --> 00:08:12,559 So I want to emphasize this is the type of scenario that's very likely to arise 142 00:08:12,559 --> 00:08:14,664 in your own algorithm designed adventures. 143 00:08:14,664 --> 00:08:17,871 You might have some problem. You're not sure how to solve it yet. 144 00:08:17,871 --> 00:08:20,628 You've brainstormed up a couple of proposed algorithms. 145 00:08:20,628 --> 00:08:24,587 And a good thing to do, a good time saver is too quickly rule out some of those 146 00:08:24,587 --> 00:08:28,196 algorithms as not the right way to go as a poor approach to the problem. 147 00:08:28,196 --> 00:08:31,203 So in this context we have these two greedy algorithms. 148 00:08:31,203 --> 00:08:34,611 Let's quickly break one of them. Show that's it's not always correct. 149 00:08:34,611 --> 00:08:37,518 How do we do that? Well, a smart way to go would be to come 150 00:08:37,518 --> 00:08:41,200 up with an input where the two algorithms do different things. 151 00:08:41,200 --> 00:08:44,748 If they do different things, at most one of them is going to be correct. 152 00:08:44,748 --> 00:08:47,997 At least one of them is going to be incorrect so that's the plan. 153 00:08:47,997 --> 00:08:51,946 Now to execute this goal, as usual we want to keep things as simple as possible 154 00:08:51,946 --> 00:08:54,745 but no simpler. So, what's the simplest possible instance 155 00:08:54,745 --> 00:08:57,545 that could lead to different behavior by two algorithms? 156 00:08:57,545 --> 00:09:00,893 Well, obviously one job is not enough because there's only one possible 157 00:09:00,893 --> 00:09:03,693 feasible solution. But already with two jobs we might be 158 00:09:03,693 --> 00:09:07,841 able to have one algorithm flip them one way and the other algorithm schedule them 159 00:09:07,841 --> 00:09:10,890 in the opposite order. In fact it is not difficult to come up 160 00:09:10,890 --> 00:09:14,363 with an instance with two jobs where they do different things. 161 00:09:14,363 --> 00:09:17,990 let me just go ahead and write such an instance down for you now. 162 00:09:17,990 --> 00:09:21,992 So suppose I give you two jobs, the first one is both longer and more important 163 00:09:21,992 --> 00:09:25,589 than the other one, specifically, its length is five, its weight is three. 164 00:09:25,589 --> 00:09:29,085 The second job, its length is merely two but its weight is merely one. 165 00:09:29,085 --> 00:09:33,240 So what I want you to do is I want you to take our two proposed greedy algorithms, 166 00:09:33,240 --> 00:09:37,192 the first one which orders by difference, the second one which orders by ratio. 167 00:09:37,192 --> 00:09:41,194 I want you to execute them on this 2-job input and compute the sum of weighted 168 00:09:41,194 --> 00:09:43,829 completion times. And then answer what is the sum of 169 00:09:43,829 --> 00:09:46,920 weighted completion times of the corresponding two schedules. 170 00:09:56,880 --> 00:09:59,657 Alright, so the correct answer, is answer B. 171 00:09:59,657 --> 00:10:04,286 Let's just briefly go through why. So first let's just make sure we 172 00:10:04,286 --> 00:10:07,857 understand which algorithm produces which schedule. 173 00:10:07,857 --> 00:10:15,638 So the first job has the better ratio. It's ratio is five 3rds, where as the 174 00:10:15,638 --> 00:10:18,758 ratio of the second job is one-half which is smaller. 175 00:10:18,758 --> 00:10:23,291 Where as the second job has the larger difference, it has a difference of -1 176 00:10:23,291 --> 00:10:27,765 where as the first job has the more negative difference of -2/ So, the first 177 00:10:27,765 --> 00:10:32,533 algorithm which orders by difference will schedule the second job first then the 178 00:10:32,533 --> 00:10:35,418 first job. The second algorithm will schedule the 179 00:10:35,418 --> 00:10:39,774 first job first and then the second one. So it just remains to compute the 180 00:10:39,774 --> 00:10:42,600 objective function value of those two schedules. 181 00:10:42,600 --> 00:10:46,674 So for the first schedule, with the second job first, while we're, the second 182 00:10:46,674 --> 00:10:49,390 job has waits of one, has a completion time of two. 183 00:10:49,390 --> 00:10:53,545 The second job has a weight of three and a completion time of seven. 184 00:10:53,545 --> 00:10:57,700 So that gives us a total of 23. Whereas the schedule produced by the 185 00:10:57,700 --> 00:11:01,061 second algorithm we have the weight three job first. 186 00:11:01,061 --> 00:11:05,583 It's completion time, now that it's first, is only five and then the second 187 00:11:05,583 --> 00:11:09,922 job with weight one get the completion time of seven for a total of 22. 188 00:11:09,922 --> 00:11:12,917 So ordering by difference gives us a value of 23. 189 00:11:12,917 --> 00:11:17,561 Ordering by ratio gives a value of 22. So in this case the ratio does better 190 00:11:17,561 --> 00:11:20,922 than the difference. So certainly the difference is not 191 00:11:20,922 --> 00:11:24,365 optimal for this specific example. So what have we accomplished? 192 00:11:24,365 --> 00:11:28,037 Well, what we've done is we very quickly ruled out one of our natural proposed 193 00:11:28,037 --> 00:11:30,720 greedy algorithms. We know that ordering by difference is 194 00:11:30,720 --> 00:11:33,216 not always correct. Again, it's going to be correct in 195 00:11:33,216 --> 00:11:37,029 special cases like when all the lengths are equal, where all weights are equal 196 00:11:37,029 --> 00:11:40,466 but it is not correct in general. That said, please remember the warning I 197 00:11:40,466 --> 00:11:43,997 gave you in the high level discussion of greedy algorithms which is greedy 198 00:11:43,997 --> 00:11:47,481 algorithms are very often wrong. Just because we know algorithm number one 199 00:11:47,481 --> 00:11:50,964 is incorrect sometimes does not at all imply that algorithm number two is 200 00:11:50,964 --> 00:11:54,119 guaranteed to be correct. It's really easy to come up with multiple 201 00:11:54,119 --> 00:11:57,027 incorrect greedy algorithms for the same problem. 202 00:11:57,027 --> 00:12:01,194 It does, however, turn out. In this case for this greedy algorithm, 203 00:12:01,194 --> 00:12:05,429 algorithm number two driven by ratio it is happily always correct. 204 00:12:05,429 --> 00:12:09,855 But you certainly shouldn't believe this claim until I provide you with a proof. 205 00:12:09,855 --> 00:12:12,455 A rigorous argument explaining the correctness. 206 00:12:12,455 --> 00:12:16,825 Always maintain healthy skepticism about the performance of a greedy algorithm 207 00:12:16,825 --> 00:12:20,356 until you learn otherwise. So, this fulfills another promise I gave 208 00:12:20,356 --> 00:12:22,957 you in the high-level discussion of greedy algorithms. 209 00:12:22,957 --> 00:12:26,184 Namely, when they're correct it's often quite difficult to prove it. 210 00:12:26,184 --> 00:12:30,133 So this would be the topic of the next couple videos the correctness proof for 211 00:12:30,133 --> 00:12:33,215 this greedy heuristic. The third and final thing we discussed 212 00:12:33,215 --> 00:12:37,116 about greedy algorithms typically is that their running time is not difficult to 213 00:12:37,116 --> 00:12:39,573 analyze. So that's a break that we catch relative 214 00:12:39,573 --> 00:12:43,177 to divide and conquer algorithms, and again that's certainly true here, 215 00:12:43,177 --> 00:12:47,141 right? So, what does this algorithm do? All it does is compute these ratios and 216 00:12:47,141 --> 00:12:50,745 then sort the jobs by ratio, so essentially the algorithm reduces to a 217 00:12:50,745 --> 00:12:54,864 single sorting computation and of course from part one, we know very well, how to 218 00:12:54,864 --> 00:12:56,100 sort in N log N time.