So in this video, we're going to revisit our greedy algorithm for minimizing the wait and somewhat completion times. And we're going to give a more robust more general correctness proof that also accommodates ties amongst the ratios of the different jobs. The main reason I'm doing this is not because you know, I think the result is, is so earth-shattering in its own right, but rather to give you further examples of exchange arguments in action, in particular outside of a proof by contradiction. So let's be formal about our new more general correctness proof. So we're again talking about the greedy algorithm which orders jobs by the ratio of weight to the length. We're no longer assuming these are distinct. So we can't really say decreasing order. We'll say non-increasing order. And ties can be broken any way you want. We'll prove the algorithms commit, correct, no matter how the ties are resolved. So fortunately,, we'll be able to reuse much of the work that we did for the previous correctness proof. But actually, our overall proof plan is going to change a little bit. we're no longer going to proceed by contradiction. So here's the high level, here's the high level plan of that. So as before, we're going to argue correctness on every separate instance, so fix an arbitrary one. So, the notation will be similar to last time, so on this input, we'll let sigma denote the output of our greedy algorithm and then we'll let sigma star denote an arbitrary other competitor, any other schedule of the jobs. So now, we're going to do is were going to show that sigma, the output of our greedy algorithm, is at least as good as sigma star, since sigma star was arbitrary, that means the greedy algorithms output is at least as good as every other schedule, and therefore, sigma has to be optimal. So, let's now fill in the details. We're going to make a similar notational assumption as last time and that we're going to assume that the greedy schedule is just 1, 2, 3, all the way up to n. And again, that's a content free assumption, we can get away with it just by changing the names of the jobs, changing notation. So, recall the proof plan, we have to take any other competing schedule sigma star and show that it's no better than sigma, show that sigma is at least as good as it. So fix any such schedule sigma star, obviously, if sigma star is sigma, then they're they same or just as good as each other so there's nothing to do. Now, if sigma star is not the same thing as sigma, if it's not just the sequence 1, 2, 3, all the way up to n, we're going to reuse a key observation from our previous proof, namely any schedule other than just 1 through n has to contain in it a consecutive pair of jobs, i and j, where j is executed immediately after i where i has the higher index. So now we argue similarly to last time. What does it matter that's, one job has a higher index than another. Well, that means it's further along in the ordering, which means its ratio can only be smaller. Remember, the ratios are non-increasing, they can only go down in the order. So higher index, means lower ratio. But there may be ties, so we can't claim a strict inequality, just a weak inequality. And so again, by clearing denominators, this boils down to the weight of job i times the length of job j is at most the weight of job j times the length of job i. Now, the next thing I want you to recall from our previous proof is that there are nice semantics with wilj and wjli namely as the cost in the benefit of exchanging jobs i and j in the schedule sigma star. So arguing as in the previous videos, we can argue, we can claim that exchanging i and j [SOUND] from a schedule sigma star has a net benefit, that is a benefit minus cost of wjli, that's because job j's completion time drops by li minus wilj. That's because job i's completion time increases by lj with this exchange and so this is non-negative. [SOUND] So in comparison with our previous proof, in our previous proof, with the assumption of bought us, it bought us the stronger fact than we exchange i and j, in fact sigma star gets strictly better. It's we get a better schedule than what we started with. Here with ties, that need not be true. If i and j have exactly the same ratio and we exchange them, then the cost equals the benefit so the net change in the objective function is 0. So we can only claim that by inverting i and j, we don't make sigma star worse. It can only get better and might stay the same. So let's see why that's good enough to nonetheless complete the proof. So what the previous slide gives us, it gives us a method of changing a schedule, massaging a schedule, so that, it doesn't get any worse, it can only get better. Specifically, if we take any schedule sigma star, we take any adjacent inversion, by which I just mean two consecutive jobs with the higher one having a higher index. We exchange the jobs in any adjacent inversion, we get a new schedule which can only be better. Some of weighted completion times might be the same, but if it's different, it has to be smaller. So in our previous proof, we knew it was strictly better because we had no ties and then our proof by contradiction said we were done. So what are we going to do now? What we're going to do is take this operation, which massages the schedule without making it worse, and we're just going to repeat it over and over and over again, because actually, this operation has a second property. Not only can it not make a schedule worse, but, it also decreases the number of inverted job pairs. And here by an inversion, I mean the same thing as when we counted inversions with the divide and conquer algorithm back in part 1. I just need a job pair somewhere in the schedule, where the higher next to one occurs earlier in the ordering. When we exchange adjacent inversion, we uninvert that aversion and because they are adjacent, we don't create any new inversions. So the number of inverted job pairs drops by exactly one, each time we do one of these exchanges. So what does that mean? So here is the proof in a nutshell. We take an arbitrary competitor, some schedule sigma star and we find, either it's the same as the greedy schedule. If it's not, there is an adjacent inversion, in which case we exchange it. We get a schedule that's at least as good and fewer inversions. Either this new schedule is sigma, in which case we're done, or it's not, and then we find an adjacent inversion, and we exchange it, it only gets better and we keep going. Why can this not continue forever? Well, the number of inversions can only be n choose 2 initially, that's if you start with the schedule n, n - 1, n - 2, all the way 1 if the jobs are initially backward. So, we can only do this exchange n choose 2 times before we necessarily terminates witht the greedy schedule, 1 through n. At that point what have we done? We've taken an arbitrary schedule sigma star, we've massaged it, making it only better, and better, and better, and better, terminating with our greedy schedule sigma. What does that say? That says our greedy schedule sigma is at least as good as when we started with sigma star. So the greedy schedule is at least as good as this arbitrary schedule sigma star, so it's optimal. It's better than everything. So one final note before I write down the QED. for those of you familiar with the bubble sort algorithm and it's totally fine if you're not familar with bubble sort, but if you are familiar with bubble sort, you will recognize that essentially what we're doing here inside the proof, not in tour algorithm but inside our proof, we're applying bubble sort in effect to this arbitrary competing schedule sigma star. And by uninverting the inversion we transform it in to the, the greedy schedule, making it only better, thereby justifying as optimal our greedy algorithm schedule sigma.