Greedy Algorithms 💰🎩💰
Introduction
Hello, fellow reader. Thanks for taking the time to read my short blog on Greedy Algorithms. I find this topic to be particularly interesting as we often use this tool in real life. In fact, if you're new to coding, you may have even used this approach on a coding exercise or project. Let’s dive in and take a look at where will use them, and why they aren’t always a good choice.
The Concept
a Greedy Algorithm is a set of instructions you’ll implement in your code to solve a particular problem. What makes this algorithm “Greedy” is the fact that it takes a very short-sighted approach in making decisions. Sometimes it’s exactly what you’ll need but there is a downside to this strategy. Let’s look at an example to help illustrate this.
Example
Let’s use a fairly common and straightforward example to explain our approach. You’ll notice in the picture above we are looking at three data structures known as binary trees. We start at the top circle or root node and move our way down to the bottom nodes/leaf nodes. At each node, we have 2 choices to make(hence the name binary tree). Each circle has a number(positive integer value) and will make our decisions based on that.
If you look at the Greedy Tree, you’ll notice that no matter the options we are given we always go with the biggest number. This doesn’t give us the biggest value though, nor does it give us the biggest total!
We want our solution to look like the optimal tree, which used another type of strategy to give us what we want. Therefore, we need to think before we leap. Gathering all your insight first will keep us from producing sub-optimal solutions.
Good Places for Greedy Algorithms
There is a general rule of thumb with this strategy. Do you need to take optimal decisions every time? Can you do this with substructures derived from the original structure( …remember our trees from earlier)? If so you’ve got a great use case. Keep this in mind, and your one more step to becoming a pro.
Dijkstra’s Algorithm, an algorithm that used to find the shortest path between nodes, is a great example. You can apply this logic to connecting flights, comparing estimated times for uber rides, even optimizing pizza deliveries. These use cases are great pairings with Greedy Algorithms.
Huffman’s Coding Algorithm is another great example. This clever set of instructions analyzes a message and depending on the frequencies(or a number of times) of the characters(a,b,c,1,2,3) used in the message, it assigns a variable-length encoding for each character.
This helps us identify commonly used symbols from rarer ones, by the length of the encoding. Super useful for compressing data without losing information, which again uses a Greedy approach!
Conclusion
In general, it’s interesting to see the various strategies used to tactical complex problems. It helps build up your knowledge base, which leverages your powers of reasoning and deduction. Starting with the greedy approach and understanding what it’s used for is important. It’s commonly used but often misunderstood.
Happy Coding 🧑💻
More on Greedy Algorithms: https://brilliant.org/wiki/greedy-algorithm/#:~:text=A%20greedy%20algorithm%20is%20a,to%20solve%20the%20entire%20problem.Huffman’s Coding Algorithm: https://brilliant.org/wiki/huffman-encoding/Dijkstra’s Algorithm: https://brilliant.org/wiki/dijkstras-short-path-finder/
