Greedy Algorithms 🤑
In your coding journey, you will come across the term — Greedy Algorithms. Sounds strange right? In this blog, we will be diving into what they are and where you will find yourself using them.
What makes an algorithm greedy? 🤔
Firstly, we will define this term and break it down further to get a better understanding.
Simply put, a greedy algorithm is an uncomplicated, intuitive algorithm that is used when dealing with optimisation problems. The algorithm makes the optimal choice at every step step as it attempts to find the overall ideal way to solve the entire problem.
Now, the reason the term greedy is given, is because of the fact it aims to take a very short-sighted approach in making decisions. Sometimes, this is what we exactly need however, there is also a negative to this strategy.
Our Binary Tree Isn’t Happy 😢
We will take a look at an example that shows us why a greedy algorithm isn’t always the best approach. Take a look at the binary tree below:
From this, we want to return the largest number that exists and as you can see from the two different approaches, the greedy and the optimal, we seem to be receiving two different results.
So, what is happening over here? Well, the greedy tree is always looking for the biggest number and so chooses that. Unfortunately, we are failing to get the biggest value or biggest total!
Now we want our solution to be that of the optimal tree, which uses a different strategy to give us what we want. When we take a step back to thoroughly see the problem at hand, we avoid ourselves from producing sub-optimal solutions.
The Good Place 😇
Let’s take a look at situations where greedy algorithms are worth using and thus creating efficiency on our end.
One question we can ask is, “Do you need to take optimal decisions every time?”. If the answer is no then we can achieve our aim through substructures derived from an original structure, like our unhappy binary tree. It is always good to remember these few points so we know we are heading in the right direction.
Let us take a look at two greedy algorithm’s that come in handy:
- Dijkstra’s Algorithm — used to find the shortest path between nodes. You can apply this logic to connecting flights, comparing estimated times for road networks, etc. Sounds like a great use case!
- Huffman Coding Algorithm — analyses a message and depending on the frequencies of the characters used in the message, it assigns a variable-length encoding for each character. This is extremely useful for compressing data without losing information, which again is a great use case!
I hope this blog has helped you in understanding greedy algorithms, why they are given that name and the use cases for such algorithms! Good luck on your coding journey and in efficiently using our good ole’ greedy friend!
