You are reading the third segment of our algorithm design patterns series. We have successfully covered the backtracking and divide-and-conquer techniques. In this article we will cover the so-called Greedy Strategy. Greedy algorithms often, but not always, yield the optimal solution in record time since they approach problem solving from a metaheuristic point of view. Thus, it is critical to master greediness.
Greedy Strategy as an Algorithm Technique (Page 1 of 4 )
Before we begin, I’d like to advocate reading the previous two parts of this series if you missed either of them. While each article covers only one technique that can be read and understood independently, there is a logic behind the sequence of articles. That’s why we began with backtracking and then moved further to divide-and-conquer, and now we’re talking about the greedy technique.
You can find both of those articles published here on Dev Articles. The upcoming segments of this series will also be located here. Don’t forget to tune in every so often so you can read them when they go live.
In the first article I presented the style that is going to be followed throughout this series. We start out by discussing the theory of each technique, and as soon as we understand how the algorithm design pattern in question works, we present problem(s) along with their solution(s) using the technique. We’ll present examples in pseudo-code and code samples in C/C++.
This article will respect that pattern. At the end, I will also point out a few other standard greedy problems and challenge you to research them to find optimal solutions (if possible), solve them as effectively and efficiently as possible, and eventually mathematically prove that your algorithm indeed finds the globally optimal solution. The same applies for other already famous algorithms… prove them!
I think the timing couldn’t be better for us to kick-start our greediness. Let’s begin!