Chapter 4: Greedy Algorithms

A greedy algorithm creates a solution by making the optimal choice at a local level in the hopes of creating a solution that is globally optimal. The easiest example of this is giving change in the way that uses the least amount of coins. There are several ways to prove that the greedy solution is the optimal solution. The two this chapter discusses are greedy stays ahead and exchange (swappy). The motivation by the greedy algorithm is to solve a non-trivial problem optimally and can be used to solve interesting problems.

The Interval Scheduling problem is a problem where we have n intervals that each have a specific start and finish time. We want to perform as many of these n tasks as possible but the intervals cannot overlap , i.e. they are compatible. The section traces through several ways we could order the intervals prior to running the greedy algorithm, providing counter-examples to the orderings that are not optimal.The optimal ordering has been found to be ordering the intervals by the time they finish. Then we choose the job the finishes first thus allowing us to maximize the time we have left to perform other jobs. If we order the intervals in this way the algorithm (text page 118) will return an optimal ordering of intervals. In order to prove that the greedy solution is the optimal solution, we use the “Greedy Stays Ahead” proof. If we create the “optimal” set of intervals, we know that at every point the greedy algorithm will have chosen an interval that ends either sooner or at the same time as the optimal set. From there we can see that there would not be an interval in the optimal solution that we would not have chosen in the greedy solution. The greedy algorithm runs in O(nloqn) time. The interval sorting take O(logn) time and then the while loop with run in O(n) time. In addition to the greedy algorithm solving the Interval Scheduling problem, it also solves the Interval Partitioning problem. This problem has a set of intervals or jobs that we want to fit in the smallest amount of resources possible (i.e. a bunch of lectures that we want to fit into the smallest number of classrooms). We immediately know the minimum number of classrooms we will use, by seeing how deep the set of intervals is. If there are 3 intervals that overlap at any given point, we know that we will need to have at least 3 resources to fit everything. Then we can design a greedy algorithm (text page 124) to place the intervals into the minimum number of resources. After analyzing the algorithm, we find that the optimal number of resources is exactly the depth of the set of intervals.

This was a pretty straightforward section. I would give it a 9/10 because it provided solutions for some cool problems and explained everything in a clear manner.