A greedy algorithm uses small steps to formulate its solution. In each step, a decision is made to optimize the solution at that step. A greedy algorithm tells use that there is some rule we can use to make small decisions that will ultimately lead us to an optimal solution. Sometimes, greedy algorithms produce solutions that are close to optimal, but not quite optimal. A greedy algorithm works by staying ahead of the optimal solution at each step. There is also the “exchange argument” that says a possible solution can be turned into the greedy algorithm solution without altering its optimality.

Readability: 7/10

The interval scheduling problems consists of a set of intervals (start and stop times) that must be scheduled for a single resource. The optimal solution is the largest set of intervals such that there is no overlap. While there are a few intuitive ways to think about how we might want to solve this problem, the greedy algorithm is based on end time. We always schedule the interval that finishes first in our set, unless that interval conflicts with the previous intervals already to our solution. To prove the solution is optimal, we must show that the greedy algorithm “stays ahead” of any other optimal solution. Each i^th accepted request will finish at least as soon as the i^th accepted request in an optimal solution, which means the greedy algorithm stays ahead of any other optimal solution. The efficiency of the algorithm to calculate this set of intervals is O(nlogn).

Readability: 7/10

The problem in this scenario is that of a single resource that must be scheduled with jobs that take a certain amount of time and have a deadline, but no set start time. The objective is to schedule all jobs in a way that minimized the maximum lateness incurred by any one job. Like our other scheduling problem, we first try to intuitively come up with ways to schedule the jobs. An optimal solution can be found by using a greedy algorithm that simply schedules jobs in order of earliest deadline. It may seem like this approach would not work because it ignores the length of jobs, but it still provides an optimal solution. While there may be many optimal solutions, our greedy algorithm provides one that has no idle time. An optimal solution with no idle time must exist, because we could simply take an optimal solution with idle time and just close all the gaps by sliding jobs backwards without adding any lateness. We define an inversion as a grouping of two jobs such that the later job's deadline occurs before the earlier job's deadline. We can just invert all of our inversions to come up with an optimal solution with no inversions, but the greedy algorithm does this for us already.

Readability: 7/10

Our problem is to find the shortest path between two nodes, assuming that are starting node has a path to ever other node in the graph, and that each edge has a specific length associated with it. Dijkstra's algorithm adds the next node with the shortest length to the current set of nodes. We use a priority queue to store the edge lengths and then use the extractMin operation to get the next shortest length.The algorithm has an efficiency of O(m) if we use priority queues.

Readability: 6/10 because it is a fairly confusing algorithm to follow