An greedy algorithm is accurate to its name. It builds up a solution greedily, by choosing a decision at each step that optimizes the solution at that point. While greedy algorithms can be designed for many problems, the ones we want to concern ourselves with are the ones that have optimal greedy solutions. Thus, most of this chapter will be concerned with constructing a greedy algorithm and then proving it is optimal, using either the greedy stays ahead argument or the exchange argument.

The Interval Scheduling Problem was introduced in chapter 1.2 and basically consists of try to schedule the largest subset of requests(with start and end times) possible without overlap. The easiest concrete example is trying to schedule meetings in a single meeting room. The key to designing an optimal greedy algorithm to solve this problem is to determine what rule to use to choose the requests. Several options, including choosing by earliest start time or smallest interval of time, provide solutions, but they are not optimal. Instead, we want to order the requests by finish time. From there, you simply pick the first one, then go down the list choosing the first one that does not overlap, and so on. The algorithm is on page 118.

To analyze the algorithm we show that our algorithm “stays ahead” of the optimal solution at every point. We can prove that for every r, the r accepted request in our algorithm finishes no later than the r request in the optimal solution. By ordering the requests by finish time, out algorithm will run in O(nlogn) time. There are also several extensions of this project such as scheduling weighted requests or scheduling requests without knowing all of them ahead of time.

A similar problem is scheduling all intervals, with the goals of using the fewest possible resources. We prove in this section that the number of resources needed is equal to the depth of the set of intervals. The depth is the maximum number of requests that overlap. It is impossible to have a solution with less resources than the depth and you cannot have an optimal solution with more resources than the depth. The algorithm on page 124 orders requests by their start time and is optimal.

This problem, like interval scheduling, has a set of requests(this time with deadlines) and a single resource. The goal here is to schedule all the requests in the single resource with the minimum largest lateness. Several ordering approaches that don't work are ordering by increasing length or time of request. Instead, we should order by their deadline, with the earliest deadline first. This is logical so that we can be sure to schedule first, the jobs that will be late the soonest. The algorithm is on page 127-128.

There are several key point to not while analyzing this algorithm, which we can prove using an exchange argument. First of all, the optimal schedule has not idle time. If it did, we could bump the requests up and the new lateness would be less than or equal to the previous lateness. There also exists an optimal schedule with no inversions. An inversion is when a job with a later deadline is scheduled before a job with an earlier deadline. This optimal schedule with no inversions or idle time is produced by the greedy algorithm. The proof by exchange argument works by modifying an optimal schedule with exchanges until it matches the greedy one, maintaining optimality the whole time. At first I didn't think it was possible to have an optimal solution with inversions, but it makes sense now. It also clears up the exchange argument.

This problem is based on a network of directed nodes and how to find the shortest path from node s to node t, or from s to any other node. Each edge has a weight or length associated with it, so a path is the sum of the weights of the edges to get from s to t. This algorithm, known as Dijkstra's Algorithm, is on page 138. The basic premise is that it keeps track of a set of explored nodes, and the distances to each of the nodes (originally infinity). You look at each edge from the explored set to any other node and keep updating the minimum distances. This algorithm is greedy because it always forms the shortest s-v path we can make from the explored set with a single edge at each step. The path to each node can only get shorter.

There are two things to note about this algorithm. First, this algorithm is dependent on the fact that all the weights are positive. Second, this algorithm is really just an extension of BFS. If we implement this algorithm with a priority queue, it can run in O(mlogn) time. Where the algorithm itself if O(m) and the operations on the priority queue are O(logn).