Keep calm and be greedy, sometimes6 min read . Updated: 11 Jun 2021, 12:50 AM IST
Greedy algorithms are valuable tools as they give us workable solutions
Greedy algorithms are valuable tools as they give us workable solutions
Two thought experiments to start this column, both of which you may have run into, or even used yourself.
First, recall your college days. In particular, imagine sitting down for a tough year-end mathematics exam. You’ve kept up in class, studied the subject well, but even so you expect the exam to push you. When you get the paper, you approach it the way your professor and parents and various other well-meaning folks have always advised: spend several minutes reading it through, then start by answering the question you recognize as the easiest. Done with that, you go on to the next-easiest, and so on.
The idea is to quickly lock in the marks you’re sure you can get. When that’s done to the extent possible, use the remaining time to solve questions that need more thought and effort and time, whose intricate calculations might induce mistakes. Why tackle the exam this way? Why not jump into the deep end right away, with the more difficult questions? Because you don’t want the difficult questions to take so much of your time that you have none left for the easy ones. That is, you don’t want to lose the easy marks that you can nail down with minimal effort. You might say, you’re greedy for them. Hold that thought.
Second, one rainy morning, you tell me I need to make a run to the nearby convenience store to stock up on food for Aziz the cat. As I grumble and then scrounge around for an umbrella, you produce a fistful of notes of several denominations. You hand them over with this stern instruction: use the minimum number of notes to pay for the cat food. On my way to the store, I marvel for a while at the eccentricity of this injunction. Why would you care how many notes I use, let alone insist on the fewest possible number? But then I start to wonder how I’m going to satisfy you.
So, let’s make this a little more real. Your fistful contains notes in these denominations: ₹500, ₹100, ₹50, ₹20 and ₹10. When I am done picking out Aziz’s food, the bill comes to ₹1,780. You’ve given me enough cash to pay, and enough notes of each denomination that there are several combinations of notes I can use. But there is that constraint you’ve handed me. How can I be sure of using the smallest number of notes?
It’s not that difficult, actually, as a little thought will tell you. We start with the note of the highest value that’s less than what we owe, and use as many of them as possible. In this case, that’s the ₹500 note. Three of them sum to ₹1,500 and, of course, we can’t use any more. We hand those over to the store-owner. What’s left of the bill is ₹280 (1,780 - 1,500 =280). Repeat: choose the note of the highest value that’s less than that amount, use as many as possible. That would be two ₹100 notes. Keep this going and we quickly have our solution: three ₹500s, two ₹100s, one ₹50, one ₹20 and one ₹10.
How do I know this is the correct solution? Well, the only way to use fewer notes is if some combination of notes can be replaced by one of a higher denomination. Not possible with the ₹500s, because I have no note worth more than that. Not possible with the ₹100s, because there are only two that I use to pay, and I need to have five to replace them with a ₹500 note. In general, not possible with any other combination of notes, because my selection of notes proceeded by switching to lower-denomination notes only when it wasn’t possible to use the higher denomination.
Intuitively at any rate, this probably makes sense. At every stage, I want to be sure to use higher-denomination notes first. You might say, at least in this task, where I must pay with as few notes as possible, that I’m greedy for the high-value notes.
“Greedy", again! As it happens, a whole class of mathematical algorithms is called “greedy". These two thought experiments capture the spirit of that greed. The point, every time you’re faced with a choice during the process, is to pick the option that you think will take you furthest right then towards the overall goal—score well in an exam, or use the fewest currency notes. That way, when the task is done, you will likely have reached that overall goal. Put it this way: while searching for an optimal solution to a problem, at each step the algorithm makes the optimal choice from those available.
Here’s a nicely mathematical example, taking off from last week’s column about series. First, an “arithmetic progression" (AP) is a sequence of three or more numbers that differ by the same amount. For example, 1, 3, 5, 7; or 101, 111, 121, 131, 141 and 151. Now you would agree that every increasing sequence of numbers doesn’t have to have an AP pop up somewhere along the way. Take the squares—1, 4, 9, 16, 25 ... - or the powers of 2 - 2, 4, 8, 16, 32 ...—clearly neither will contain an AP. You can think of other examples, too.
But consider a greedy algorithm that will produce a sequence of numbers, one that is guaranteed never to have an arithmetic progression. Put down 0 to begin with. The next entry in the sequence is selected greedily—the smallest number that will not immediately form an AP with numbers already in the series. The second entry is thus 1 (because anyway we can’t form an AP with just two numbers). The third cannot be 2, because (0, 1, 2) is an AP. So it is 3. The fourth is 4 because (0, 1, 4), (0, 3, 4) and (1, 3, 4) are all not APs. So, we have 0, 1, 3, 4. What’s the fifth in the sequence? It can’t be 5, because (1, 3, 5) is an AP. Not 6, because (0, 3, 6) is an AP. 7 gives us (1, 4, 7) and 8 (0, 4, 8), both APs; so neither of those can be next. In fact, it is 9. Staying greedy every time, we produce this sequence: 0, 1, 3, 4, 9, 10, 12, 13, 27, 28, 30, 31, 36, 37, 39, 40 ... (Aside: if you were presented this sequence—even this many entries—and not the greedy algorithm that produced it, would you be able to work out the next entry? I seriously doubt I would).
As computer science students know well, greedy algorithms are interesting programming challenges in various familiar mathematics and computer science problems—finding the shortest path through a maze, for example, or compressing data for more efficient storage, or maybe even playing a game of chess. Though as CS students also know well, interesting programming challenges don’t necessarily solve problems: greed may not actually succeed. The famous travelling salesman problem is not so easily tackled, and what looks superficially like the best move in a given chess situation may well lead to disaster several moves down the road. Still, greedy algorithms are valuable tools in many problems. Maybe even in decisions about vaccinations? If they don’t always produce a correct solution, they may get us a workable solution. Sometimes, that’s good enough. Sometimes, you see, greed is good.
Once a computer scientist, Dilip D’Souza now lives in Mumbai and writes for his dinners. His Twitter handle is @DeathEndsFun
Never miss a story! Stay connected and informed with Mint. Download our App Now!!