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).
A Greedy Algorithm
Loading...
From the course by Stanford University
Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
557 ratings
From the lesson
Week 1
Two motivating applications; selected review; introduction to greedy algorithms; a scheduling application; Prim's MST algorithm.
Meet the Instructors
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.
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
