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

373 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 the plan for this video is to develop a greedy algorithm that always minimizes

the waited sum of completion times of a given set of in jobs.

But more than the specific problem, more than the specific algorithm I want you to

focus on the process by which we arrive. At this greedy algorithm.

because I think this process is really something which you can use yourself, in

your own applications. The process we're going to use is we're

going to first look at just a special case in the problem, where it's

reasonably intuitive what should be the optimal thing to do.

Looking at these special cases will then motivate a couple of natural greedy

algorithms. Then, we'll figure out how to narrow a

couple of greedy algorithms down to just a single candidate, and that in fact, as

we will prove in the following lectures, will always be correct.

So let's just briefly recall what is it we're trying to do.

The computational problem and instant to specify by end jobs which come along with

waits and links, and among all end factorial ways that we can sequence the

jobs, we want to somehow home in on the one that minimizes the sum of waited

completion times. Recall from the previous video that the

completion time of a job is just the amount of time that elapses before it's

done. So that's going to be the length of all

the previous jobs plus the length of job J itself.

What we're hoping is going to work out is that we can devise a greedy algorithm

that always solves this problem. So maybe I should take a step back and

ask, you know why do greedy algorithms seem like a sensible way to approach this

scheduling problem? Well, you know.

In general, greedy algorithms are not guaranteed to work.

You may have to do something more complicated.

But scheduling still seems like a good place to try them out.

Remember what a greedy algorithm does, it iteratively makes myopic decisions.

An then you hope you have a, a reasonably good result at the end.

Now, what are we doing? We're studying a sequencing problem.

The definition of the problem is to schedule a job then another job then

another job all the way up to the last job and so this iterative nature of the

solution suggests that at least if you're lucky if the problem is simple enough

maybe there's a greedy algorithm which simply schedules the jobs in the correct

order one at a time. So, we're going to see if that works for

minimizing the sum of waited completion times.

So let's start by thinking positive, being optimistic.

So let's pause it that the greedy algorithm does exist for this problem.

Given that we're in the greedy algortihm section of the course you're, probably

you'll going to find this hard to believe.

But suppose one existed, how would we discover what it is?

Well a useful technique not just for this problem but, you know more generally in

real life, first focus on some special cases of the problem, where it's

relatively clear how you should proceed. And the two special cases I want you to

think about for this problem are first of all, suppose I told you all of the jobs

had exactly the same length but they had different weights, then, what order do

you think it makes sense to schedule the jobs in?

Secondly, suppose that I told you, that all of the jobs had exactly the same

weight, but they had different lengths. Then, what order do you think you should

schedule the jobs in? So first if all the jobs have the same

length, you should prefer jobs with larger weights.

Certainely, eh, this intuitively jives with our semantics of weights, that says

more importance, which suggest that higher weight jobs should go first, if

you look at the actual formula of minimizing the sum of weight and

completion times, if the jobs all have the same length.

Then the completion times are going to be the same your going to see the same set

of them. If all the jobs have length one, then the

completion times of the jobs are going to be one, two, three, four all the way up

to N. No matter what sequence you use.

So to make this as small as possible, you want the highest waits to be associated

with the smallest completion times that is, you want them upfront as early as

possible. The second special case where jobs have

equal waits but varying lengths, I think is a little more subtle.

Here what you want to do is you always want to favor small jobs, jobs with the

smallest lengths, everything else being equal.

The reason for that is that scheduling a job at a given position forces all the

other jobs to wait for that job to complete.

So all the, so whatever job you schedule first has a negative impact on all of the

rest of the N minus one jobs. So I'll.

Things being equal, you want the smallest job there that minimizes the consequences

for the jobs that are to follow. If you find this a little unintuitive, I

suggest just looking at a very simple example.

Two jobs. Both have weight one, one has length one,

one has length two. If you schedule the small job first

you'll have completion times of one and three for a total of four but if you

schedule the bigger job first you get completion times of two and three for the

bigger sum of completion times of five. So the next step is to move beyond

special cases, which we understand well. To the general case, which perhaps we

don't understand. So suppose all of the weights are

different, and all of the lengths are different.

Well, if we have two jobs, and both of these rules of thumb give us the same

advice, we're good. If there's one job which is both higher

weight, and smaller than another job, then clearly that job should go first.

But what if our two rules of thumb to prefer high weight jobs and to prefer

small jobs, give us conflicting advice. What if we have a pair of jobs, where one

of them is on the one hand higher weight, higher priority but on the other hand,

bigger than the other one. Which one should go first?

Well let's again stay positive, and let's try to think about the simplest kind of

algorithm that could conceivably work. It won't be a guarantee that it works,

but it might work. So we have these two different

parameters, length and weights. Maybe we can aggregate these two

parameters into a single one, into a single sort of score for each of the jobs

so that if we schedule the jobs from high score to low score, we'll always be

optimal. That would be great.

If we could compile these two numbers into one for each job, and then just sort

and be done. There is of course the question of

exactly how do we choose this aggregation function.

How do we compile length and weight into a single number.

Well as guidelines we should recall our special case and make sure we respect our

two rules of thumb. So all else being equal we should prefer

jobs with higher weight. So that says higher weight should meet

the higher scores if we're going to schedule the job from high score to low

score. And then also if a length is bigger that

should decrease the score. We should prefer jobs that have a small

length. So this idea leaves open the question of

exactly how do we aggregate the length and the weight of a job into a single

number. So what I want you to do now is I want

you to think for a minute about what kind of simplest possible functions you could

use. So again, these are mathematical

functions. They take as input two numbers, a length

and a weight of a job, and they output a single number, a score.

And the function should have the properties that it's increasing in the

job's weight, and it's decreasing in the job's length.

So there's more than one answer to this question but just sort of dream some sort

of ideas of what this function might look like.

Alright so there is certainly any number of functions that have these properties,

but I'm just going to write down for concreteness two of what I think are of

the simplest functions that have these properties.

So one is going to be based on taking the difference of the two numbers and one is

going to be based on taking the ratio of the two numbers.

So if you're going to use a function based on the difference, then you're want

to be increasing in the way of decreasing the length.

Then of course, the obvious difference to use is weight minus length, this can be

negative sometimes but that doesn't bother us the algorithm is still well

defined. And if you're going to use a ratio and

you want it to be increasing in weight, decreasing in length, then the sensible

ratio to use is, the weight of a job, divided by the length of a job.

It is of course possible that you have ties for either one of these scoring

functions, so let's just allow ties to be broken arbitrarely.

Now, what we're seeing here is a concrete instantiation of something I promised you

in our high level discussion of greedy algorithms, namely, it's both a strength

and a weakness of them that they're really easy to come up with and propose.

So here we have just, you know, this one simple problem, and we now have two

different, competing greedy algorithms for the problem.

Now, because these two algorithms don't do the same thing.

Only one of them, at most, can be always correct.

At least one of them has to be wrong sometimes.

So, as the algorithm designer, what the process now is.

Maybe we can rule out at least one of these two proposed greedy algorithms, by

showing an example where it doesn't do the right thing.

So I want to emphasize this is the type of scenario that's very likely to arise

in your own algorithm designed adventures.

You might have some problem. You're not sure how to solve it yet.

You've brainstormed up a couple of proposed algorithms.

And a good thing to do, a good time saver is too quickly rule out some of those

algorithms as not the right way to go as a poor approach to the problem.

So in this context we have these two greedy algorithms.

Let's quickly break one of them. Show that's it's not always correct.

How do we do that? Well, a smart way to go would be to come

up with an input where the two algorithms do different things.

If they do different things, at most one of them is going to be correct.

At least one of them is going to be incorrect so that's the plan.

Now to execute this goal, as usual we want to keep things as simple as possible

but no simpler. So, what's the simplest possible instance

that could lead to different behavior by two algorithms?

Well, obviously one job is not enough because there's only one possible

feasible solution. But already with two jobs we might be

able to have one algorithm flip them one way and the other algorithm schedule them

in the opposite order. In fact it is not difficult to come up

with an instance with two jobs where they do different things.

let me just go ahead and write such an instance down for you now.

So suppose I give you two jobs, the first one is both longer and more important

than the other one, specifically, its length is five, its weight is three.

The second job, its length is merely two but its weight is merely one.

So what I want you to do is I want you to take our two proposed greedy algorithms,

the first one which orders by difference, the second one which orders by ratio.

I want you to execute them on this 2-job input and compute the sum of weighted

completion times. And then answer what is the sum of

weighted completion times of the corresponding two schedules.

Alright, so the correct answer, is answer B.

Let's just briefly go through why. So first let's just make sure we

understand which algorithm produces which schedule.

So the first job has the better ratio. It's ratio is five 3rds, where as the

ratio of the second job is one-half which is smaller.

Where as the second job has the larger difference, it has a difference of -1

where as the first job has the more negative difference of -2/ So, the first

algorithm which orders by difference will schedule the second job first then the

first job. The second algorithm will schedule the

first job first and then the second one. So it just remains to compute the

objective function value of those two schedules.

So for the first schedule, with the second job first, while we're, the second

job has waits of one, has a completion time of two.

The second job has a weight of three and a completion time of seven.

So that gives us a total of 23. Whereas the schedule produced by the

second algorithm we have the weight three job first.

It's completion time, now that it's first, is only five and then the second

job with weight one get the completion time of seven for a total of 22.

So ordering by difference gives us a value of 23.

Ordering by ratio gives a value of 22. So in this case the ratio does better

than the difference. So certainly the difference is not

optimal for this specific example. So what have we accomplished?

Well, what we've done is we very quickly ruled out one of our natural proposed

greedy algorithms. We know that ordering by difference is

not always correct. Again, it's going to be correct in

special cases like when all the lengths are equal, where all weights are equal

but it is not correct in general. That said, please remember the warning I

gave you in the high level discussion of greedy algorithms which is greedy

algorithms are very often wrong. Just because we know algorithm number one

is incorrect sometimes does not at all imply that algorithm number two is

guaranteed to be correct. It's really easy to come up with multiple

incorrect greedy algorithms for the same problem.

It does, however, turn out. In this case for this greedy algorithm,

algorithm number two driven by ratio it is happily always correct.

But you certainly shouldn't believe this claim until I provide you with a proof.

A rigorous argument explaining the correctness.

Always maintain healthy skepticism about the performance of a greedy algorithm

until you learn otherwise. So, this fulfills another promise I gave

you in the high-level discussion of greedy algorithms.

Namely, when they're correct it's often quite difficult to prove it.

So this would be the topic of the next couple videos the correctness proof for

this greedy heuristic. The third and final thing we discussed

about greedy algorithms typically is that their running time is not difficult to

analyze. So that's a break that we catch relative

to divide and conquer algorithms, and again that's certainly true here,

right? So, what does this algorithm do? All it does is compute these ratios and

then sort the jobs by ratio, so essentially the algorithm reduces to a

single sorting computation and of course from part one, we know very well, how to

sort in N log N time.

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