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

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

Okay let's continue the perfect correctness of our greedy algorithm for

minimizing the sum of the weight of completion times and let's move onto

understanding the ramifications of the exchange of jobs suggested at the

conclusion of the previous video. So recall the basic ideas to use this

observation that the optimal schedule sigma star by virtue of our assumption of

being different from the greedy one has to have this pair of consecutive jobs

where the earlier one has the higher index.

So my question for you involves thinking about how the completion times of all of

the jobs change after we make this exchange of the two jobs i and j.

Which ones go up? Which ones go down?

Which ones are unaffected? Which ones can we not actually predict

whether they go up or down? All right, so the answer to this, quite

key question is the third answer. Jobs other than I and J are unaffected, the

completion time of job I goes up, and the completion time of job J goes down.

So let's review why. Consider a job K, other than I or J, it's probably easiest

to see if in sigma-star, K completes before I and J, scheduled earlier than I

and J. Don't, remember what the completion time

of a job is, it's just the time that needs to elapse before it gets done, so

it's the sum of the job lengths up to, and including that job itself.

So if K was scheduled before I and J before, it's exactly the same after I and

J are swapped. You don't know the difference.

Exactly the same set of jobs precedes Job K is the force whose completion time is

the same. But if you think about it, this exact

same argument is true for jobs K that succeed INJ.

So before we do the swap, it has to wait for a bunches ops to complete, including

INJ and after we swap INJ, it still has to wait for INJ to complete.

Yeah, they complete in opposite order but who cares?

The amount of time of the lapse is exactly the same.

So importantly, jobs other than INJ are completely agnostic to the swap.

Their completion time is exactly the same as before.

So that's the first. Part.

so job I, it's completion time goes up. It's easier to see why it used to be

before J, now it has to wait for J. In fact we can say exactly how much

completion time goes up by. It goes up by exactly the length of J.

That is the extra time that now needs to elapse before I gets completed.

By exactly the same reasoning the completion time of job j actually drops

it has to wait for the same jobs to complete before it being accepted no

longer has to wait for job I. So, not only can we say its completion

time goes down we can say that it goes down so by precisely the length of job I.

So now we are in a great position to finish off this proof.

Let's summarize what we got so far. So, for a cost benefit analysis of

exchanging I and J, we discovered the cost is limited to an increase in the

completion time of job I and the benefit is limited to the decrease in the

completion time of job J. Specifically the cost, the new cost

incurred by the exchange is the weight of job I times the amount by which it's

completion time went up, namely the length of job J.

Similarly, the benefit of the exchange is the drop of LI and J's completion time

and that gets multiplied by it's weight's of WJ.

So now finally we are at the point where we can use the fact that this purportedly

optimal schedule sigma star schedules I and J in some sense incorrectly,

with a higher index job first despite it having a lower ratio in contrast to the

principles followed by our greedy algorithm.

So why is it relevant that the earlier job I has a higher index?

Well, a higher index corresponds to a lower ratio.

Remember we did this notation switch so that the first job has the highest ratio,

the second job has the second highest ratio and so on.

So the bigger your index, the further you are down in the ordering, the lower your

ratio. So because I is bugger than J, that means

I's ratio is worse than J. The usefulness of this becomes even more

apparent when we clear denominators. We multiply both sides by the, by LI

times LJ. And then we find that WI times LJ is

strictly less than WJ times LI. But what are these, these are just the

cost and benefit terms respectively of our thought experiment exchange,

exchanging I and j. So what does it mean that the benefit of

the swap outweighs the cost? It mean if we take sigma star, this

reportedly optimal solution, and we invert the jobs I and j, we get a

schedule with an even better weighted sum of completion times, but that is nuts.

That's absurd, sigma star was supposed to be optimal.

So here's our contradiction. That completes the proof.

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