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

437 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

For our next case study of how to use greedy algorithms, we're going to turn to

Â the application domain of scheduling. That is how do you schedule jobs on

Â shared resources in order to accomplish some objective.

Â So, the domain of scheduling there's lots of different applications of greedy

Â algorithms. We'll see two in this course.

Â we'll start for today just with the following simple scenario.

Â So, we'll assume, for today, that there's just one shared resource.

Â This resource could represent any number of things.

Â For concreteness, you can think of it as a computer processor.

Â And then, there's a lot of different things that got to get done.

Â So, for example, there's a lot of processes that have to be handled by this

Â processor. In the algprithmic question, we are going

Â to study, is, in what order should we sequence these jobs?

Â Which one should we do first, which one should we do second, and so on, all the

Â way up to which one should we do last. So, obviously to answer this question, we

Â need to pin down the mathematical model a little bit more precisely.

Â And lets start with just, you know, what is the characteristics of jobs, what

Â information do we have that might lead us to prefer one job over another.

Â But for this problem, we're going to assume that each job comes with two known

Â parameters. So, first of all, job j has what we're

Â going to call a weight w sub j. That's a non-negative real number.

Â And you should think of the weight of a job as quantifying its importance.

Â That is, jobs with a higher weight, in some sense, deserve to be processed

Â earlier than those with a lower weight. And secondly, each job j is going to come

Â with a non negative length l sub j. Depending on the application, you may or

Â may not have a good estimate of how long jobs are going to take, but for today to

Â keep things simple, let's assume we know what the length of every job is, and

Â that's l sub j, it's part of the input to are problem.

Â So. we have now defined the input to this

Â computational problem. We get n jobs each specified by a weight

Â and a length. And we know that the output is going to

Â be a sequence of these n jobs in some order.

Â So, what we have to understand now is what criterion do we want to optimize?

Â What are we trying to accomplish with this sequence?

Â To explain that, I need to tell you about completion times of jobs.

Â So, the completion time of a job is defined hopefully in exactly the way

Â you'd think. So, for the job which is scheduled first,

Â it's just the length of the job because that's how long it takes to process that

Â job. For whatever job gets scheduled second,

Â its completion time is the length of the first job and then, the length of that

Â job itself. So, in other words, it's just the total

Â time which elapses before that job gets completed,

Â okay? So, in general, the completion time of a

Â job is just the sum of the lengths of the jobs scheduled to before that job plus

Â the length of that job itself. To make sure this is clear, let's go

Â through a quick example. So, suppose there are three jobs with

Â lengths one, two, and three. I'm not going to tell you the job weights

Â because they're irrelevant for the purposes of computing the completion

Â time. And let's suppose we do the schedule

Â where we just schedule job one first, the job two, then job three.

Â So, pictorially, I'm going to represent that schedule just by stacking the jobs

Â on top of each other with the interpretation that time starts at the

Â bottom. So, time zero is where we schedule job

Â one. And then, time increases as we go from

Â the bottom to the top of the diagram. And the question then is, what are the

Â completion times of these three jobs? Okay.

Â So, the correct answer is answer C. So, for the first job, it gets scheduled

Â first so it's very happy and it just takes one unit of time to complete, so

Â its completion time is one. The second job, well, it has to wait for

Â the first job to complete so one unit of time elapses and then, it itself has to

Â complete so that's two more units so it gets to the completion time of three.

Â For the third job, it has to wait for the first two to complete, so that adds three

Â to the clock, and then plus it takes three units of time for a total of six.

Â So, that's the definition of job completion times. In some sense, we

Â obviously want completion times to be as small as possible.

Â But it's not so simple. In any given schedule, the jobs that are

Â give early on are going to have small completion times and the jobs towards the

Â end are going to have big completion times. So inevitably, we're going be have

Â to trading off the completion times between different jobs.

Â So, what is the optimal way to so that? Well, that depends on our objective

Â function, and in scheduling, there's many different objective functions you might

Â want to use. today, I'm just going to tell you about

Â one. It's not the only natural objective

Â function, but it's one of several most natural objective functions.

Â It's called minimizing the weighted sum of completion times.

Â You translate this English phrase into mathematics in the obvious way.

Â What you want to do is you want to minimize the sum over all n jobs of their

Â completion time, but then multiplied by their weight of [UNKNOWN] j.

Â Okay. So, the sum over j of w j times c j.

Â The w j is the weight and c j is the completion time as defined on the

Â previous slot. If you think about it for a second,

Â you'll realize this is equivalent to minimizing the weighted average of the

Â completion times with the weights given as in the input.

Â So, just to make sure this makes sense, let's go back to the example that we saw.

Â In that example, we had jobs with lengths one, two, and three, and we thought about

Â to schedule or we scheduled them in that order.

Â To evaluate the subjective function, I'd have to tell you their weights, so let's

Â suppose their weights are three, two, and one, respectively.

Â In this case, the weighted sum of completion times in the schedule,

Â in the previous slide, well first, we begin with a, the first

Â job, which has weight three. Its completion time, remember, was one.

Â Then, we have the second job with weight two, its completion time is three.

Â Then, we have the third job with weight one, its completion time was six.

Â So, we sum up the weighted completion times and we get a total of fifteen.

Â And I'll let you verify that, in fact, all of the three factorial or six

Â schedules in that example, this is, in fact, the schedule that minimizes the

Â weighted sum of completion times. And the algorithmic question we're going

Â to study next, is how do we do this in general?

Â Given arbitrary input in jobs, weights, and lengths, what is the sequence that

Â minimizes this sum over all n factorial sequences you might consider?

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