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.