Today, we're going to embark on the 
discussion of a new algorithm design 
paradigm. 
Namely, that of designing and analyzing 
greedy algorithms. 
So to put this study of greedy algorithms 
in a little bit of context, let's just 
zoom out. 
Let's both review some of the algorithm 
design paradigms that we've already seen, 
as well as look forward to some that 
we're going to learn later on, in this 
course. 
So it's sort of a sad fact of life that 
in algorithm design, there's no one 
silver bullet. 
There's no magic potion that's the cure 
for all your computational problems. 
So instead, the best we can do, and the 
focus of these courses, is to discuss 
general techniques that apply to lots of 
different problems that arise and lots of 
different domains. 
So that's what I mean by algorithm design 
paradigms. 
High level problem solving strategies 
that cut across multiple applications. 
So let's look at some examples. 
Back in part one, we started with the 
divide and conquer algorithm design 
paradigm. 
A canonical example of that paradigm 
being the merge sort algorithm. 
So remember in divide and conquer what 
you do is you take your problem you break 
it into smaller sub problems, you solve 
the sub problems recursively and then you 
combine the results into a solution for 
the original problem. 
Like how in merge sort you recursively 
sort two sub arrays and then merge the 
results to get a sorted version of the 
original input array. 
Another paradigm that we touched on in 
part one, 
although we didn't discuss it anywhere 
near as thoroughly, is that of randomized 
algorithms. 
So the idea that you could have code flip 
coins, 
that is, make random choices, inside the 
code itself. 
Often, this leads to simpler, more 
practical, or more elegant algorithms. 
A canonical application here is the quick 
sort algorithm using a random pivot 
element. 
But we also saw applications for example, 
to the design of hash functions. 
So the next measure paradigm we're going 
to discuss is that of greedy algorithms. 
So these are algorithms that iteratively 
make myopic decisions. 
In fact, we've already seen an example of 
a greedy algorithm in part one namely 
Dijkstra's shortest path algorithm. 
And then, the final paradigm we're going 
to discuss in this class is that of 
dynamic programming, 
a very powerful paradigm which solves, in 
particular, two of the motivating 
questions we saw earlier namely, sequence 
alignment, and distributed shortest 
paths. 
So what is a greedy algorithm anyways? 
Well, to be honest, I'm not going to 
offer you a formal definition. 
In fact, much blood and ink has been 
spilled over which algorithm is precisely 
greedy algorithms. 
But, I'll give you a sort of informal 
description. 
A sort of rule of thumb for what greedy 
algorithms usually look like. 
Generally speaking, what a greedy 
algorithm does, is make a sequence of 
decisions with each decision being made 
myopically. 
That is, it seems like a good idea at the 
time and then you hope that everything 
works out at the end. 
The best way to get a feel for greedy 
algorithms is to see examples and the 
upcoming lectures will give you a number 
of them. 
But I want to point out we've actually 
already seen an example of a greedy 
algorithm in part one of this course, 
namely Dijkstra's shortest path 
algorithm. 
So in what sense is Dijkstra's algorithm 
a greedy algorithm? 
Well if you recall the psuedo code for 
Dijkstra's algorithm, you'll recall 
there's one main wild loop and the 
algorithm process's exactly one new 
destination vertex in each iteration of 
this wild loop, so there's exactly N - 1 
iterations overall, where N is the number 
of vertices. 
So the algorithm only gets one shot to 
compute the shortest path to a given 
destination. It never goes back and 
revisits the decision, in that sense the 
decisions are myoptic, irrevocable and 
that's the sense in which Dijkstra's 
algorithm is greedy. 
So let me pause for a moment to discuss 
the greedy algorithm design paradigm 
generally. 
Probably this discussion will seem a 
little abstract so I recommend you 
revisit this discussion on the slide 
after we've seen a few examples so at 
that point I think it will really hit 
home. 
So let me proceed by comparing it and 
contrasting it to the paradigm we've 
already studied in depth. 
That of divide and conquer algorithms. 
So you'll recall that in a divide and 
conquer algorithm what you do is, you 
break the problem into sub-problems. 
So, maybe you take an input array and you 
split it into two sub-arrays. 
Then you solve the smaller sub-problems 
recursively, and then you combine the 
results of the sub-problems into a 
solution to the original input. 
So the greedy paradigm is quite different 
in several respects. 
First, both a strength and a weakness of 
the greedy algorithm design paradigm is 
just how easy it is to apply. 
So it's often quite easy to come up with 
plausible greedy algorithms for a 
problem, even multiple difference 
plausible greedy algorithms. 
I think that a point of contrast with 
divide and conquer algorithms. 
Often it's tricky to come up with a 
plausible divide and conquer algorithm, 
and usually you have this eureka moment 
where you finally figure out how to 
decompose the problem in the right way. 
And once you have the eureka moment, 
you're good to go. 
So secondly, I'm happy to report that 
analyzing running time of greedy 
algorithms will generally be much easier 
than it was with divide and conquer 
algorithms. 
For divide and conquer algorithms it was 
really unclear whether they were fast or 
slow, because we had to understand the 
running time over multiple levels of 
recursion. 
On the one hand problems were size was 
getting smaller, but on the other hand, 
the number of some problems was 
proliferating. 
So we had to work hard, we developed 
these powerful tools like the master 
method, and some other techniques, for 
figuring out just how fast an algorithm 
like Merge Sort runs, or just how fast an 
algorithm like Strassen's fast matrix 
multiplication algorithm runs. 
In contrast with greedy algorithms, it 
will often be a one liner. 
Often it will be clear that the work is 
dominated by say, a sorting sub routine 
and of course we all know that sorting 
takes n log and time if you use a 
sensible algorithm for it. 
Now the catch, 
and this is the third point of 
comparison, 
is we're generally going to have to work 
much harder to understand correctness 
issues of greedy algorithms. 
For divide-and-conquer algorithms we 
didn't talk much about correctness. 
It was generally a pretty straightforward 
induction proof. 
You can review the lectures on Quicksort 
if you want an example of one of those 
canonical inductive correctness proofs. 
But the game totally changes with greedy 
algorithms. 
In fact, given a greedy algorithm we 
often won't even have very good intuition 
for whether or not they are correct. 
Let alone how to prove they're correct. 
So even with a correct algorithm, it's 
often hard to figure out, why it's 
correct. 
And in fact, if you remember only one 
thing from all of this greedy algorithm 
discussion many years from now, 
I hope one key thing you remember is 
they're often not correct. 
Often, especially if it's one you 
proposed yourself which you're very 
biased, in favor of. 
You will think the algorithm, the greedy 
algorithm must be correct because it's so 
natural. 
But many of them are not, so keep that in 
mind. 
So to give you some immediate practice 
with the ubiquitous incorrectness of 
natural algorithm. 
Let's review a point that we already 
covered in part one of this class 
concerning Dijkstra's algorithm. 
Now, in part one we made a big deal of 
what a justly famous algorithm Dijkstra's 
shortest path algorithm is, it runs 
brazenly fast and it computes all the 
shortest paths. 
What else do you want? 
Well remember there was an assumption 
when we proved that the Dijkstra's 
algorithm is correct. 
We assumed that every edge of the given 
network has a non negative length. 
We did not allow negative edge lengths. 
And as we discussed in part one, you 
know, 
for many applications, you only care 
about non negative edge lengths. 
But there are applications where you do 
want negative edge lengths. 
So let's review on this quiz why 
Dijkstra's is actually incorrect, despite 
being so natural. 
it's incorrect when edges can have 
negative lengths. 
So I've drawn in green, a very simple 
shortest path network with three edges 
and I've annotated the edges with their 
links. 
You'll notice one of those edges does 
have a negative length, the edge from V 
to W with length minus two. 
So the question is consider the source 
vertex S and the destination vertex W. 
And the question is, what is the shortest 
path distance computed by Dijkstra's 
algorithm and you may have to go and 
review just a pseudo code in part one or 
on the web. 
to answer that part of the question and 
then what is in fact the actual shortest 
path distance from S to W where as usual 
the length of a path is just the sum of 
the lengths of the edges in the path. 
All right, so the correct answer is D. 
So let's start with the second part of 
the question, what is the actual length 
of a shortest path from S to W when 
there's only two paths at all in the 
graph? 
The one straight from S to W that has 
length 2, and the one that goes by the 
intermediate point V that has length 3 + 
-21, = 1 which is shorter. 
So, SVW is the shortest path that has 
length 1. Why is Dijkstra incorrect? Well 
if you go back to the pseudo code of 
Dijkstra, you'll see that in the very 
first iteration it will greedily find the 
closest vertex to S in that case this is 
W, W is closer then V. It will greedily 
compute the shortest path distance to W 
knowing the information it has right now 
and all it knows is there's this one hot 
path from S to W, so it will irrevocably 
commute to the shortest path distance 
from S to W as 2. 
Never reconsidering that decision later. 
So Dijkstra will terminate with the 
incorrect output that the shortest path 
link from S to W is 2. 
This doesn't contradict anything we 
proved in part one, because we 
established correctness of Dijkstra only 
under the assumption that all edge links 
are non-negative, an assumption which is 
violated in this particular example. 
But again, the takeaway point here is 
that, you know, it's easy to write down a 
greedy algorithm, especially if you came 
up with it yourself. 
You probably believe deep in your heart 
that it's got to be correct all the time, 
but more often than not, probably your 
greedy heuristic is nothing more than a 
heuristic. 
And there will be instances in which it 
does the wrong thing. 
So keep that in mind in greedy algorithm 
design. 
So now that my conscience is clear, 
having warned you about the perils of 
greedy algorithm design, let's turn to 
proofs of correctness. 
That is if you have a greedy algorithm 
that is correct. 
And we will see some notable examples in 
the coming lectures. 
How would you actually establish that 
effect? 
Or if you have a greedy algorithm, and 
you don't know whether or not it is 
correct, 
how would you approach trying to 
understand which one it is, whether it's 
correct or not? 
So let me level with you. 
Proving greedy algorithm is correct. 
Frankly, is sort of, more art than 
science. 
So, unlike the divide and conquer 
paradigm, where everything was somewhat 
formulaic. 
We had these black box ways of evaluating 
recurrences. 
We had this sort of, template for proving 
algorithms correct. 
Really, proving correctness of greedy 
algorithms takes a lot of creativity. 
And it has a bit of an ad hoc flavor. 
That said, as usual, to the extent that 
they are recurring themes. 
That is what I will spend our time 
together emphasizing. 
So let me tell you just again about very 
high level. 
How you might go about this. 
You, again, might want to revisit this 
context aft-, content after you've seen 
some examples where I think it'll make a 
lot more sense. 
So method one is our old friend or 
perhaps nemesis depending on your 
disposition, namely proofs by induction. 
Now for a greedy algorithms remember what 
they do, they sequentially make a bunch 
of irrevocable decisions, so here the 
induction is going to be on decisions 
made by the algorithm. 
And if you go back to our proof of 
correctness of Dijkstra's algorithm, that 
in fact is exactly how we proved 
Dijkstra's algorithm correct. 
It was by induction of the number of 
iterations, in each iteration of the main 
wild loop. 
Computed the shortest path to one new 
destination. 
And we always proof that assuming all of 
our previous computations were correct, 
that's the inductive hypothesis. 
Then so is the computation in the current 
iteration. 
And so then by induction, everything the 
algorithm ever does is correct. 
So that's a greedy 
proof by induction that a greedy 
algorithm can be correct. 
And we might see some more examples of 
those in, for other algorithms in the 
lectures to come. 
Some of the text books call this method 
of proof greedy stays ahead, 
meaning you always proof greedy's doing 
the right thing iteration by iteration. 
So a second approach to approving the 
correctness of greedy algorithms which 
works in a lot of cases is what's called 
an exchange argument. 
So you haven't yet seen any examples of 
exchange arguments in this class so I 
can't really tell you what they are but 
that's what we're going to proceed next. 
I'm going to argue by an exchange 
argument that a couple of difference 
famous greedy algorithms are in fact 
corrected. 
It has a couple of different flavors one 
flavor is to approach it by 
contradiction. 
You assume for contradiction that a 
greedy algorithm is incorrect and then 
you show that you can take an optimal 
solution and exchange two elements of 
that optimal solution and get something 
even better which of course contradicts 
the assumption that you started with an 
optimal solution. 
a different flavor would be to gradually 
exchange an optimal solution into the one 
output by a greedy algorithm without 
making the solution any worse. 
That would show that the output of the 
greedy algorithm is in fact optimal. 
And formally that's done by an induction 
on the number of exchanges required to 
transfer an optimum solution into yours. 
And finally, I've already said it once, 
but let me say it again, there's not a 
whole lot of formula behind proving 
greedy algorithms correct, you often have 
to be quite creative, you might have to 
stitch together aspects of method one and 
method two, you might have to do 
something completely different. 
Really, any rigorous proof is fair game.