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

488 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.