The Greed of Algorithms

Ka-ching!

The sound of the register as you see the cashier pick out cash and coins to give you your change for your purchase. But how does the cashier know what types of change to give you so you don’t get flooded with coins? Well, the correct answer would be to return all $0.83 with pennies, but instead, cashiers use what’s called a “greedy algorithm”. 

Now, what exactly is a greedy algorithm? Simply put, a greedy algorithm is a heuristic, or method, which chooses the most optimal path at every point. This doesn’t necessarily mean you produce an overall optimal path, just that the path you take is optimal in each step. What does this mean? Well, let’s return to our coin problem.

In our coin problem, the cashier, let us call him Aaron, picks coins until he gets up to $0.83. Aaron lives in America, so he uses the American coin system. In the American coin system, we primarily focus on 4 types of coins: quarters, dimes, nickels, and pennies, which are $0.25, $0.10, $0.05, and $0.01 respectively. Using a greedy algorithm, Aaron would decide to pick out two quarters, one dime, one nickel, and one penny, as he is choosing the most optimal path each time. This can be described in the figure below.

slide_10

As Aaron starts out with $0.83, the largest valued coin that would go into the money would be a quarter. He would then subtract $0.25, and be left with $0.58. Once again, a quarter is the largest valued coin that can be subtracted from the change. He can do this twice, leaving him at $0.08. Here, a quarter can no longer go into the change, so Aaron chooses the next highest coin that can to in, which is a nickel, valued at $0.05, leaving him with $0.03. From here, Aaron can only pick out three pennies as no other coin is valued less than $0.03. Thus, Aaron, our cashier, has found the optimal path to the least number of coins, which is a total of 7 coins.

The above situation is a greedy algorithm. In the case of the coins, the most optimal option is the largest number which will go into the remainder. There are many situations like this, like the largest object that can fit into a bag, etc. However, this is not always the scenario. Take, for example, if Aaron was to live in a country where the coins valued $1.00, $5.00, and $6.00. A greedy algorithm would work, at least until Aaron hit $10.00. Let us take two examples, $7.00 and $10.00.

In the first example, Aaron would choose one $6.00 coin, as it fits into $7.00, and end up with $1.00 remaining. He would then select a $1.00 coin, which would add up to $7.00 in two coins, the least amount of coins Aaron can give. You can test this, and you will find that given only $1.00, $5.00, and $6.00 coins, the minimum number of coins will always be two coins. However, if Aaron wishes to return $10.00 the same way, he will not have the most optimal solution. By using one $6.00 coin, Aaron is left with $4.00, which means he has to use four $1.00 coins. This results in him using five coins, which is not an optimal number of coins. Instead, if Aaron uses two $5.00 coins, he will similarly achieve $10.00 while using three fewer coins.

What can we learn from this? Well, first off, we must thank Americans for getting one system of measurement right, even if it is only money. However, we must understand that what is initially optimal isn’t necessarily always the best option. In computer science, greedy algorithms only work in certain scenarios and therefore require further improvement. In the case of graphs, greedy algorithms will work for a majority of the time; one example would be finding the “minimum spanning tree”, an algorithm that finds the minimum edge weights within a graph.

Overall, greedy algorithms are still quite powerful; they might be a basic, brute force approach to a problem, but most times they are enough to deliver your solution. Greedy algorithms are simple and fast to write, making them an optimal first attempt. Sometimes, it’s alright to be greedy with your algorithms.

 

-Yucheng Niu

 

Image credits:

https://slideplayer.com/slide/4527824/

https://en.wikipedia.org/wiki/Travelling_salesman_problem

 

 

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.