Today I am continuing on with my review of a book on programming algorithms. The book, “Grokking Algorithms, Second Edition” by Aditya Bhargava, is well worth a read if you haven’t studied algorithms or if you would like a refresher. In Part 5 I covered Depth First Search. Today I am covering greedy algorithms and dynamic programming.

Greedy Algorithms

Sometimes when you are trying to solve a problem, there are easy ways to arrive at the optimal solution. That’s where greedy algorithms come in. Bhargava uses the classroom scheduling problem to illustrate, let’s go over it. Technicall, at each iteration of your solution, you pick the optimal move, and that produces the globally optimal solution. It only works for some problems, but when it does, it offers an easy solution. Imagine that you have a set of classes you want to hold, but only one classroom available, and more classes that can be held in the classroom. How do you schedule the largest number of classes? look at this schedule:

Note, this code takes what you might consider a shortcut by turning the classes hash map into an array and then sorting the array by start time to ensure the greedy algorithm picks the earliest class first. It also fails to check the earliest ending class on each iteration of the loop, so it depends on classes of the same length. It works for our sample data, but would need adjustment if there were classes starting at the same time that ended at different times.

Next time, I will talk about the backpack problem, which requires a more sophisticated approach than this.