Hello ladies and gents,
I hope you had a great week, if you did not, I hope this one is better than the previous one. Today we will be discussing about greedy algorithms. I have always believed that all advancements in computing and computer science are efforts to replicate the human brain and/or behavior, greedy algorithms support this hypothesis. By the end of this newsletter you should know why.
Greedy Algorithms
Greedy algorithms are a set of algorithms that make the most optimal choice at any given point. This means that in each iteration, the algorithm makes the “best” possible choice, however, this does not always result in an overall “best” outcome. In order words, the algorithm is well, greedy.
Greedy algorithms try to get the best possible outcome by making the most optimal choice at each step. However, it is possible that it does not produce the best possible outcome.
Before we talk about this using a more in-depth example, let’s quickly run through a scenario that portrays how greedy algorithms work.
Given the options below, which would you pick? Which do you think a greedy algorithm would pick?
Hint: you are a five year old :)
While greedy algorithms would also desire to end up with iPhone 13, they will end up with iPhone 12. Why? Because they make the best choice at every step. Given the options iPhone X or iPhone 11, greedy algorithms would pick an iPhone 11. Consequently, the end result will be an iPhone 12. As we can see, this is the right choice to make at step, but it isn’t the right choice when you consider the final outcome. This is the risk of greedy algorithms.
Why Greedy Algorithms?
Greedy algorithms are great for problems that require finding the maximum or minimum outcomes - i.e optimisation problems. By making the best choice each time, greedy algorithms end up making the best overall choice.
Let’s take a good example.
Growing up, I always tricked my younger siblings that the quantity of cash in hand is more important than the value of cash in hand. This example illustrates that trick.
Let’s assume I have $5, $50, $10, $100, $1, and $20 notes (I said assume because I do not have in reality). If the assignment is to take as many notes as possible, greedy algorithms would pick the smaller notes first. Say we could only pick 3 notes, greedy algorithms would pick $1, $5, and $10. If however, the assignment was to take as few notes as possible, the notes collected would be $100, $50, and $20.
When and When Not To?
As I previously alluded to, greedy algorithms are great for maximising or minimising output, however, they are not great at predicting future events.
Let’s assume you just got out of work and had to take public transportation, which path would you take home? In an attempt to minimise the cost of going home, greedy algorithms would pick path A, thus you’d spend $55 to get home. That is a lot of money! Especially when you could have paid $20 less if you went with path C.
Because greedy algorithms always make the best local optimal choice in an attempt to get the global optimal result, we limit the use of greedy algorithms to problems we are sure that they will give us good outcomes.
Greedy algorithms are good for problems like “first come first serve”, “shortest job first”, “priority scheduling”, “knapsack problem”, “Dijkstra Shortest path” etc.
Conclusion
Who would have thought that being greedy would help you understand understand an algorithm? Not me! As we can see, being greedy isn’t the right answer all the time either. Choose when and how to be greedy.
Thank you so much for reading! See you again next week.
Technical resources
Find more technical resources to learn about greedy algorithms.
https://medium.com/brandons-computer-science-notes/greedy-algorithms-c015b0da1d14
https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/