Welcome to this lecture on Greedy Algorithms. Last week we've been looking at Dynamic Programming. We looked at some problems, for example, the rod cutting problem. In the rod cutting problem, we were given a rod of length L and we were given some lengths, l_1 and prices p_1, l_2 prices, p_2, l_k prices p_k. We saw that the solution was to carefully consider all possibilities using the optimal substructure property and we could solve it. Often, you might have noticed if you played around with the code that we provided you, that it was counter-intuitive how to solve the rod cutting problem, so the best cut was often counter-intuitive. In many cases, it also takes a lot of time. That amount of time we took was something like theta of L, where L is the actual length of the rod. For example, if L equals 1,000 and that is four digits, the amount of time is 1,000. If L equals 10^4, that's five digits, the amount of time is 10,000. As you see, the representation length of L, the number of digits or number of bits to represent L grows by every bit that you grow, your running time doubles. This looks like polynomial, like we briefly mentioned last time, it's a pseudo-polynomial algorithm. It's actually expensive. The dynamic programming solution, once L becomes large, it's again going to be expensive. It's less expensive than the recursion because we are memorizing, but it's still expensive because you have to create a table whose size is as large as the length of the array that you are interested in. This is where greedy algorithms come in. In greedy algorithms, these are generally very, very fast algorithms to solve the same kind of problems that we typically solve using dynamic programming, which is to maximize or minimize value function. Some kind of value function subject to some constraints. Typically we make the decisions or stage, so you make a decision as to what is the first cut that I make, once I have made this first cut, I make the second cut, once I've made the second cut, I made the third cut. The problem satisfies the optimal substructure property. All of this you should know from dynamic programming. What is a greedy algorithm then? A greedy algorithm simply uses what is called a local criterion or a greedy criterion to make a choice right now, and then once it makes a choice, it uses the same greedy criterion to make the next choice and so on. In the rod problem, for example, suppose I looked at each of these lengths and each of these prices, and let's say I used a metric price per unit length, p_1 divided by l_1, p_2 divided by l_2, p_k divided by l_k. Let me, for example, sort all the options using price per unit length. What is price per unit length? It means that, if for example, let me give a concrete instance, let us say I'm interested in cutting 80 centimeters. That's the size of the rod that I have to cut, and my length l_1 is 45 centimeters, and it fetches a price of $4.50. Let's say my length l_2 is 40 centimeters and it fetches a price of $3.90. Let's say my length l_3 is 30 centimeters and it fetches a price of $2.50. These are the three options that I have. These are the three options that I have for cutting this rod of 80 centimeters, what would dynamic programming do? Well, dynamic programming would carefully build up a memo table of size 80, and it would decide, in this case, I believe the best answer is to make two cuts of 40 centimeters each. Cut L into two sub rods of 40 centimeters. Hopefully, this is clear and how much do I get for it? This would pay off $7.80 and that I think is going to be the optimum. But let us look at the greedy solution, what is the greedy solution going to do? In greedy solution, what we're going to do is we are going to come up with a metric, some kind of a metric on which we are going to be greedy. We've decided that we are going to be greedy on the price per unit length. What's the price per unit length? Here, the price per unit length is $0.10 for the first option, $4.50 divided by 45 centimeters, so it's $0.10 per centimeter. $0.10 per centimeter, I'm not writing the units, you know what the units are. Let me actually make it bigger so you can see it, and bring it here. For the first option, the price is $0.10 per centimeter, what about for the second option? Well, it's going to be about 390 divided by 40, something like 9.75 cents per centimeter. Take my word for it, I might be wrong, but we can fix it later, it's going to be less than $0.10, that much I know. What's the price per unit length of the third option? Well, for the third option, it's 30 centimeters $2.50, it's going to be 8.33 cents per centimeter. This is okay, I don't need to be precise. If I made a numerical mistake, please point it out on Piazza, and that's okay. These are the three options. In the greedy algorithm, what am I going to do? I'm going to choose l_j that provides greatest value per centimeter or price per centimeter, such that also l_j is less than equal to l. If it were more than l, I cannot cut l_j, so it has to be less than L. In this case, I have 80 centimeters worth of rod. Eighty centimeters worth of rod, my first decision according to my greedy algorithm is choose the one that gives me the best bang for the buck. Literally, best price per unit length that I cut, and this is literally l_1 and that says $4.50. Then I'm going to cut off 45 centimeters, and what remains? What remains is the new L is going to be 35 centimeters after I cut off and the price that I have gotten for it is $4.50 so far. Now for 35 centimeters, I again apply the same algorithm. Choose the best option that gives me the greatest bang for the buck, but once I only have 35 centimeters, the first two options are out of question because I can no longer cut a rod of 45 out of 35 or 40 out of 35, I'm only left with a rod of size 30 that I could cut out, and that's the best option, in fact, it's the only option. The second cut is going to give me 30 centimeters, then I'm left with five centimeters, I have no option for it, so I wasted. How much do I earn using this option? I earn $7. Now you've seen your first greedy algorithm. A greedy algorithm is going to be an algorithm that makes choices in a greedy manner, another word for it is a Myopic algorithm. These algorithms apply when you have to make a sequence of choices. I have to make a choice now, based on that choice, I have to make a new choice, based on that choice, I had to make a new choice based on that choice. In greedy algorithms, I do not do any future lookahead. I look at the set of choices I have, I make up some criterion to choose between them, here the criterion is my bang for the buck criterion, which is how much cost price do I get per unit centimeter, which is a great criterion if you will, and I just take the best option that gives me for now the largest buck per unit centimeter, which is the first option. Never mind that if I had chosen a slightly less optimal option for now, what that allows me to do is that it allows me to waste less rod eventually. Because I am wasting less rod, I come out ahead eventually. But in a greedy algorithm, I always go with the best option. I cut out that size of the rod, whatever is left with, I apply the greedy criterion again. I cut out that second best and then finally I'm left with five centimeter waste. Whereas dynamic programming does a look ahead, which means that it's not myopic. It looks forward and says, let me consider the current choice, but based on the current choice, let me look at the remaining sub-problem and consider the best way of solving the subproblem and for all possible current choices, let me find out what's the best way. That's how dynamic programming works, but it's expensive. Greedy on the other hand here is really cheap. It's very easy to solve this greedy algorithm. It's linear time in the size of L let's say. It's basically an iterative algorithm. It just works a few times, you're done which is great. But the problem with greedy is that it doesn't always give you the best answer. If you put in more work, you could have gotten a better answer. Now you've gotten a flavor of greedy algorithm. Let's go through some other greedy algorithms and let's start looking at first examples where greedy algorithms are not going to be the best options. But then strangely, there are some very happy examples, and some very important examples where the greedy algorithm provides you an answer that's as good as a more expensive dynamic programming algorithm. Those are the most important cases. What are those? It turns out, greedy algorithms are widely used for couple of reasons. One reason is they are fast. In many cases, getting a fast answer that's slightly or maybe probably worse than the best answer, it's fine, is better than getting the best answer, which may take a long time to compute. That's one reason to do it. In some cases, the best option is actually a greedy algorithm. These are very important cases. We will look at a few of them today, but then there's more coming up in the rest of this class. More importantly, there is a couple of very important algorithms. An algorithm for finding minimum spanning trees in graphs. The shortest path algorithm called Dijkstra's algorithm. Among other things, these are going to be well-known examples and widely used examples of greedy algorithm. We're going to look at a few more examples of greedy algorithms, cases where they are fast but not necessarily provide you the right answer, and then cases where they are actually going to be fast and the happy coincidence of being fast and optimal at the same time, which is everything we want in life, fast and optimal. Now we're going to look at the greedy coin changing problem. We've already looked at the coin changing problem. We have an amount x, and we are allowed coins of denominations c_1, c_2, through c_n. For example, you have 78 cents, and you have 1 cent, 5 cents, 10 cents, 25, and 50 cents, and these are the standard US denominations. It's also standard in many countries and as you will see it's standard for a reason. Why? What's the greedy algorithm for making change? This is the algorithm that people across the world use for making change. If I have 78 cents to make for, let me look at the largest coin that still goes under 78 cents, that's 50 cents. Let me first start by giving you 50 cents. The remaining is 28 cents. Now, how do I make change for 28? I'll give you one 50 cent coin. Now for 28, I'll give you a 25 cent coin, then I get three cents back, and then I'll give you three times one cent. The greedy algorithm is the algorithm that millions of people in the US around the world used to provide change. What is it? Find largest amount C_i less than equal to C, the amount I have to make change for. Give one coin C_i, and then recursively solve for C minus C_i, that's it. That's what we did here so if we had to make change for 78 cents, we found the largest amount that goes under 78, 50, give one 50 cent coin, now we're left with 28 cents. How do I make change for 28? Give one 25 cent coin, now we're left with three, and so give three. The number of coins we used in this process is five coins, one 25 cent, one 50 cent, and three one cent coins. This is how you would do it in a supermarket or anywhere else. It turns out that this is actually optimal for these sets of denominations. On the other hand, if I wanted to mess you up, let me introduce, let's say 1, 5, 10, 25. Let's also for fun, have a 39 cent coin, and 50 cent. Why a 39 cent coin? I don't know. Let's say because we wanted to honor some event that happened in 1939, I don't know, or the 39th president of the United States, whoever that was. Let's say they issue that 39 cent coin for some reason. Well, now it's going to mess things up because this is no longer optimal if I had a 39 cent coin. Then the optimal way to give change which is what our dynamic programming algorithm looked at, was to give two 39 cent coins, and then you have 78 cents and you're done. Instead of five coins, I can do it with two coins, that's so much better. We have an interesting idea here, if we have the standard US denominations, then greedy algorithm is actually optimal. If I had the standard US denomination, then the greedy algorithm is actually optimal. How do we prove this? This is actually a very interesting question. I will not really look into how to prove this for now, but let's say this is a well-studied problem on why this happens. One hint that I will provide you is suppose you sum up 1 plus 5, that comes in less than 10. If you sum up 1 plus 5 plus 10, that's 16, which is less than 25. 1 plus 5 plus 10 plus 25 is less than 50. So if you sum up all the preceding denominations, that comes in less than 50. That's one good reason why this happens, though that's not the right reason. I'm just alluding to a result about what's known for a form of knapsack problem, which is what the coin changing problem really is. Let's not worry too much about that. Take my word for it that greedy algorithm is optimal if you had these coins in the standard US denominations and it's so much faster than the dynamic programming algorithm. On the other hand, if you mess up the standard denomination, then greedy algorithm is no longer optimal as we saw in this example here. You can make change with smaller number of coins. What we have learned from this is greedy algorithms are really great under some situations. They are always fast. Because they are myopic, I'm making one choice right now without consideration of future choices. I'm just making a greedy choice and then whatever is left over, I solve it using a greedy choice, and a greedy choice, and so on. They are not always guaranteed to solve the problem. They are not always guaranteed to solve it optimally, but in some instances they are. In those instances, they are extremely fast. As an example, greedy algorithms provide the optimal answer when the coins are the standard US denomination as opposed to some arbitrary numbers we came up with. With this introduction, we are going to look at more greedy algorithms coming right up where we're going to look at cases where greedy algorithms actually do a great job, and actually solve the problem perfectly. Coming right up.
