[MUSIC] In this part of the course, we've been talking about algorithms. And last time, we looked at an approach to solving optimization problems called brute force, in which we consider all possible solutions and choose the one that's best. But sometimes this can lead to a lot of possible solutions and we may not want to spend a lot of time checking all of them. So we'll wrap us this part of the course by talking about a simple approach. It may not always give the best solution but at least it's quick and may give us something that's close to optimal in much less time. In the first part of the course, Sue talked about algorithms she could use for determining how to mulch her yard. One of the approaches was to first mulch the flower bed that would make her happiest, since it was most visible from the house, and then do the flower bed that would make her the next happiest, and so on until all the beds were mulched. This way she's maximizing her initial happiness and then doing things that will increase your happiness as much as possible. This is known as a greedy algorithim. In a greedy algorithm you do the thing that seems best at the time or locally optimal as we say and it's going to get you closest to solving the problem even if it's not actually part of the best solution. It's kind of the opposite of brute force. With brute force, you look at all the possibilities and then choose the one that's best. In a greedy algorithm, you just say, I'll do whatever seems best right now, repeat, and hope it all works out later. Let's see how we can use a greedy algorithm to solve another optimization problem. I love my laptop but my battery only lasts about three hours before I need to recharge it, which can be a bit of a pain because I'm always in meetings across the campus or teaching. So the problem I need to solve is when I should bring my laptop to my office to charge the battery so that I don't have to bring the power cord with me. I'd like to do this so that I never run out of power. And most importantly so that I have to go back to my office the fewest number of times. So let's say this is my schedule for a particular day. And you can see I have these seven half hour breaks in between the meetings and classes. I can only go three hours without charging the battery and I want to recharge it as few times as possible. And let's say that each time I charge it, I get a full charge after 30 minutes. So when should I plan on charging it? We could approach this using a brute force algorithm that would have exponential complexity. There are seven breaks in my schedule, and at each break, I either do or do not recharge the battery. Overall, that would be 2 to the 7th or 128 different possible combinations. Some of those combinations would not actually work because my battery would die if I waited more than three hours. But of those 128 combinations, I could look at the ones that do work and then find the one where I recharge my battery the fewest times. But if we approach this using a greedy algorithm, we don't have to look at all combinations, we can just ask what makes the most sense right now and plan that way by doing what seems locally optimal. That is makes some short-term decisions that makes sense and don't worry about what might happen later on. In this case, what seems locally optimal is just waiting as long as possible to recharge the battery, and not recharging it if I can wait until later to do it. So if the battery's fully charged at 8 AM, I know it'll last until 11 AM before it dies. It doesn't make sense to recharge it at 9:30, because I can just wait until 10:30. That is, I'll just try to go as far as possible into my schedule, recharge it and then start over. So I'll charge it from 10:30 to 11 and now that's part of my solution. Now I know that the battery will last until 2 PM. Again, I won't bother charging it at 12 o'clocl because I know I can wait until 2 which is when my 3 hours are up but at least I made through my meeting so I'll charge it from 2 to 2:30. Now I know the battery will last until 5:30, I won't charge it at 3, but I'll have to charge it from 4:30 to 5. And then that will get me to the end of the day. So the solution is to charge it three times, as you see here. In this case, it can be shown that the greedy algorithm gives us an optimal answer. That is one where my laptop doesn't die and involves the fewest number of return visits to my office. Furthermore, it's linear. We only go through the scehdule once and don't need to consider all 128 combinations. Unfortunately though, greedy algorithms won't always give us the best answer. And in some cases, we need to resort to brute force to get the optimal answer. But even in those cases, greedy is still a good approach if we're okay with being close to optimal. Let's revisit the example from last time in which I taught a class that had eight teaching assistants and I wanted to meet with all of them once a week. I gave them five options for meeting times, and then I wanted to choose the smallest number of meeting times so that I could meet each TA at least once. Here are the five times that I suggested, and the x marks indicate when each of the eight TAs are available. Remember, I'm trying to find the fewest meeting times such that I can meet each of the TAs. Last time we said that a brute force approach would be exponential. I could look at all combinations of the five meeting times, which I do or do not include each solution. For instance, one possible solution that I could consider is Monday, 2 PM, Wednesday, 4 PM and Thursday, 6 PM. But I'd reject this because I couldn't meet TA number six that way. Another possible solution that I could consider is Monday, 2 PM, Tuesday, 6 PM, Wednesday, 1 PM, and Thursday, 6 PM. That would allow me to meet all the TAs. But is that the fewest number of meetings? So a brute force approach is to find all the combinations that allow me to meet all the TAs, and then among those, find the solution with the fewest number of meetings. As we saw last time, since there are five possible meeting times, there are two to the fifth possible solutions. And 2 to the 5th is 32. But now let's try to use a greedy algorithm so that we don't have to explore all 32 possible solutions. When we use a greedy algorithm, we ask, what's the best thing I can do right now that gets me closest to the goal? It might make sense to start with the time when the most TAs are available. So now here are the candidate meeting times sorted by the number of available TAs. If I were being greedy, I choose the first one which is Wednesday 4 PM since 6 of the TAs are available. This is a choice that seems best at the time, or locally optimal. Do the thing that gets you closest to the solution. Great, I'm nearly done, right? I just need to find time to meet with the last two TAs. So let's get rid of the one's I've already scheduled and look at the ones I haven't. So now I just need to find a time that works for TA6 and TA7. I've highlighted their availability in red, and we'll circle it here. [SOUND] It looks like there's no time that works for both of them, so I would need to set up two more meetings for a total of three. That's not bad and we found that solution pretty quickly. But it's not actually the minimum number of meetings. Can you see why this approach didn't work? Let's go back to the original chart. Obviously, I can't meet all the TAs at once but can I do it with two meetings? It turns out you can with Tuesday 6 PM and Thursday 6 PM. These two times work for all the TAs. It turns out that we could only have find that solution by considering all 32 possibilities. But in this case, the greedy approach got us a pretty good solution quickly, even though it wasn't actually optimal. In this lesson, we've seen greedy algorithms as an alternative to brute force algorithms for solving optimization problems. In a greedy algorithm, we always do the thing that seems best at the time and that gets us closest to the solution, and then keep repeating until we're done. Unlike brute force algorithms, greedy algorithms are not guaranteed to give you the optimal solution, but in many cases can quickly give one that may be good enough. When you should use brute force algorithms and when you should use greedy algorithms is a tricky subject. If you're doing calculations by hand and not using a computer to help solve the problem, and you'd probably want to use a greedy algorithm, you wouldn't be guaranteed the absolutely best optimal solution, but it might be close enough for you and it would save you a lot of time. However, if you were writing a program to implement your algorithm, as we'll see later in the course, and your input size isn't too big, then a brute force solution may be okay as you'd likely get the optimal answer in a reasonable amount of time. But if you do have a large input size and aren't willing to wait a really long time, like hours or even days, to get the absolute optimal solution, then a greedy algorithm would be a good choice.
