The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

Loading...

From the course by Stanford University

Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming

433 ratings

The primary topics in this part of the specialization are: greedy algorithms (scheduling, minimum spanning trees, clustering, Huffman codes) and dynamic programming (knapsack, sequence alignment, optimal search trees).

From the lesson

Week 1

Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim's MST algorithm.

- Tim RoughgardenProfessor

Computer Science

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.

Â Coursera provides universal access to the worldâ€™s best education,
partnering with top universities and organizations to offer courses online.