So now let's turn our attention to proving the correctness of this Greedy Algorithm that we devised that proportatedly minimizes the some of the waited completion times. Let me remind you of the formal correctness claim. The claim is that our second greedy algorithm. The one which looks at the ratio of each job. The ratio of the weight to the length and sorts them in decreasing order, is always correct. For every possible input, it ouputs the, the sequence of jobs, which minimizes the weighted sum of completion times. And as promised, it wasn't hard to devise the greedy algorithm. It's certainly not hard to analyze its running time, which is N Log N. The same time as sorting, but it is quite tricky to prove it correct. The way we're going to do that, is going to be our first example of what's called an exchange argument, which is one of the few recurring principles in the correctness proofs of greedy algorithms. So I'm actually going to give you proofs of two different versions of this claim. Both will make use of an exchange argument in slightly different ways. For starters that's going to be in the next video and the next one. I'm going to make a simplifying assumption that there are no ties amongst the ratios, that each job has its own distinct ratio of its weight versus its length. In this case, we will be able to get away with proof by contradiction. So, on this slide lemme give you the high level proof plan and of how this is going to go, we will start delving into the details on the next slide. So on the high level we're going to begin by fixing an arbitrary instance. By which I mean, you know just the description of the weights and lengths that. So remember, we have to prove that our algorithm is always correct. So we just fix an arbitrary instance, and prove correctness on this arbitrary instance. So, as I said, for the case with no ties, we're going to proceed by contradictions. Remember, this means we assume what we're trying to prove is false. And from that, we derive something which is obviously false inconsistent. So, what would it mean to assume that this claim is false? It means there exists an instances for which this greedy algorithm does not produce an optimal solution. For which there's some other solution not output by the greedy algorithm, which is better than that of the greedy algorithm. So let me just give you some notation to set this up. We're going to let sigma denote the greedy schedule. And if our claim is false, that means this is not an optimal schedule there's some other one which is better so call this better optimal sigma star. So, to complete a proof by contradiction, we need to derive something which is obviously false and the way we're going to do that here might strike you as initially as a little weird but it turns out to work really well in this context. From this assumptionm that the greedy algorithm is not optimal, and there is a better scheduled sigma star, we're actually going to exhibit yet another schedule which is even better than sigma star. Strictly smaller picto.function value than sigma star has. Why is that a contradiction? Well, by assumption, sigma star is optimal so if you show that there is something even better than sigma star, sigma star is not optimal and that completes the proof by contradiction. So now lets start filling the details of this proof plan and making it rigorous. So as I said in this video and the next we're going to be assuming that all of the ratios are distinct. In general, of course that need not be true and I'll give you a separate argument to handle the case of ties. I'm going to make a second assumption. But, unlike the first assumption, the second assumption has no content. It's just an assumption about notation. I'm going to assume by renaming jobs, that job one, number one, is the one with the highest ratio. Job number two is the one with the second highest ration and so on. Job ending the one with smallest ratio. As a consequence of this switch in notation the greeter schedule is very simple to describe. It just schedules job one first, then job two second, then job three third, and so on, all the way up to job N. Okay, so we have one assumption which is not without loss of generality, and we'll have a separate argument for handling ties. We have a second assumption which is without loss of generality. It's just an agreement amongst friends who want to minimize notation. And now, lets actually derive something with content. So given that the greedy schedule is just the jobs in order, one, two, three, all the way up to N. And given our assumption that the greedy solution is not optimal, and instead there's some other distinct optimal schedule sigma star. I claim that sigma star must contain consecutive jobs, that it is somewhere in the schedule, sigma star, I can isolate a pair of jobs, one executed after the other, such that the earlier of those two consecutive jobs has a larger index. I'm going to call these jobs I and J with I being earlier. So again by virtue· of the optimal solution sigma star being something other than the schedule one, two, three up to N there must be two jobs somewhere in the schedule executed in a row one after the other so that the earlier job I has a higher index then the subsequent job J. Why is this true? Well the reasoning is that, the only schedule. It has the property that indices only go up as you go from the earliest job to the latest job. The only way that indices will always go up is if you schedule the jobs one, two, three, all the way up to N. There is no other schedule with a property that indices always go up other than one, two, three, all the way up to N. So this is an observation that's going to be important in the rest of the proof, so make sure you pause, give yourself enough time to stare at it and commit yourself it is in fact true. Any, any schedule other than one, two, three, all the way through N, have to have consecutive jobs, the earlier one having a higher index than the later one. So I'm now in a position to explain the exchange in the exchange argument. So let me just distill the two key points from the discussion so far. So first of all we have changed notations so that ratios are decreasing with index and this is exactly the same as the schedule that the greedy algorithm will output. And then assuming that the optimal schedule sigma star is something else we know it has consecutive jobs with a earlier one having a higher index. Keep in mind, our high level proof plan from the first slide of this video. Where, we're doing a proof by contradiction. We need to derive a contradiction and what we're going to do is we're going to exhibit a schedule even better than sigma star thereby contradicting it's purported ophthalmology. So how do we do that? We do that with an exchange. So this exchange is going to take the place of methodic experiment. We're going to take this purportedly optimal schedule sigma star and we're going to switch the order just of the two jobs I and J leaving all of the other jobs unchanged. So sigma star consists of various jobs. It's called stuff collectively. then next is job I and after that immediately is job J. And then there's possibly some more jobs that get executed after J. And remember, we observe that, we can chose I and J so that I has a higher index than J despite being scheduled earlier. Then we execute this exchange. The stuff before INJ is the same as before. The more stuff after JNI, is the same as before. But we're going to have them occur in opposite order. And the key thing we have to understand next is, what are the ramifications of this exchange? What are the costs? What are the benefits? That's how we'll begin, the next video .