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.