Chapter 4: Greedy Algorithms

This section opens up by discussion some of the merits of being ‘greedy’. It defines a greedy algorithm to be one that can build a solution using small steps, each step making a decision that will optimize the solution. Various greedy algorithms can be created for the same problem. The success of a greedy algorithm helps to imply that there exists a certain ‘rule’ that can be applied to the decisions at each step which one can use to create an optimal solution. While it is simple to actually create a greedy algorithm, proving they are the optimal solution is much more difficult. There are various approaches to creating a greedy algorithm, which will be discussed in other sections of this chapter. I would give this section a 10/10 readability as it was very short and a good introduction to what this section is talking about.

This section goes over the Greedy Algorithm Stays Ahead approach, and demonstrates it using the Interval Scheduling problem. Overall I would give it a 8/10 for readability. This is exactly what we did in class, so this section was very much a review. The interval scheduling problem can be described as a set of n tasks where each task starts at s(i) and finishes at f(i). A subset of tasks are compatible if no two tasks in the subset overlap in time, and we are looking for the largest subset possible. Sets that are of the largest size possible are considered optimal.

To develop a greedy algorithm, we want to come up with a rule in selecting our first task. We then would reject all other tasks that are not compatible with the chosen task. Then, we’d look at the next compatible task, and also reject non- compatible tasks. This process is repeated until we have analyzed all tasks for compatibility. The difficult part in developing this greedy algorithm is not the process itself, however, it is choosing the rule that will allow us to have an optimal solution. To find this rule, we consider some of the most obvious methods of picking a task. One rule is to pick the earliest task (earliest start time). This does not yield an optimal solution as a task that starts early might have a long interval, meaning that there may be several conflicts. By starting with the task that takes the shortest interval of time we still might not get the optimal solution. We can find the optimal solution with the rule of accepting the task that finishes first. This allows us to maximize our subset of tasks.

While this method is optimal, it is not clear from looking at the problem that this is the optimal solution. Now that we have determined that it is optimal, we need to prove it. We need to consider an optimal set of intervals, that we can call O, that we need to show our algorithm “stays ahead” of. To do so, partial solutions of the greedy algorithm are compared to the corresponding segments of O to show that the greedy algorithm is “staying ahead”. We want to show that the length of our subset equals the length of the optimal solution’s subset. This can be proved by induction to show that the greedy algorithm stays ahead. To show why this implies the optimality of the subset we determine using the greedy algorithm, we can use a proof by contradiction. In this scenario, our algorithm would have a runtime of O(n log n). This is because we must initially sort the requests in order of their finish time, which takes O(n log n) time. It then takes O(n) time to construct the array and iterate through the intervals.

A similar problem is where we have several resources and want to schedule all tasks using as few resources as possible. This is also similar to what we exampled in class. To demonstrate this problem, we will use a task as a lecture that needs to be scheduled in a classroom for an interval of time. We can refer to the depth as the maximum number that occur at the same point in time. Therefore, the depth is equal to minimum number of resources needed. However, the depth isn’t always the answer to the number of resources needed. There may be other issues that cause the use of additional resources. However, we can design a greedy algorithm that can create a schedule. In this case, we use the start times of the intervals to organize them. We then assign each interval to a ‘label’ that hasn’t already been assigned to any previous interval that overlaps it.

We now look at greedy algorithms through the exchange argument. Here, we go back to the use of a single resource and a set of n tasks to use the resource for a certain interval of time. Now, these requests have deadlines, but still take a time period of t to complete. We want to schedule each task to minimize lateness. This problem seems much easier to think about a possible greedy solution for as it reminds me of in general scheduling things to be completed, like homework. Just as in the solution, when I do my homework, it is the most logical to complete items that are due first, rather than doing what takes the shortest amount of time or some other method.

A request is considered late if it misses its deadline. Here, we want to minimize the maximum lateness. As already mentioned, the optimal solution here is pretty intuitive, schedule based on earliest deadline, however, the proof isn’t so simple. First, we want to order jobs by their deadline. Then we want to assign the next job to start once we have completed the previous task. In this algorithm there are no gaps in time. This means that there is an optimal schedule with no idle time. Considering an optimal schedule, O, we want to modify O at each step, eventually transforming it into a schedule that is identical to our result from the greedy algorithm. This is an exchange argument. An inversion is if a job is scheduled before a job with an earlier deadline. By definition our greedy algorithm has no inversions. We can then say that all schedules with no inversions and no idle time have the same maximum lateness, and the same about the optimal solution. We can prove that both of these scenarios exist, and so the schedule obtained by the greedy algorithm is optimal.

This problem can also be applied to scenarios where we need to consider each task’s start time as well. Readability was 7/10.

Greedy algorithms can also be applied to graphs in finding the shortest paths and constructing minimum-cost spanning trees. Since graphs are used to model networks, we often want to find the shortest path between nodes in a graph in the most efficient manner. Given a starting node s, what is the shortest path from s to another node? Edsger Dijkstra used a simple greedy algorithm to solve this problem. He started by finding an algorithm that finds the length of the shortest path from s to each other node, which then allowed him to produce the paths as well. This algorithm maintains a set of verticies that have been determined the shortest-path distance from s, the “explored” nodes. Then, he determined the shortest path by traveling along a path from the explored region to another node. He then chose the node for which the quantity of this next path is minimized, and then added that node to the explored region as well. We can prove that this algorithm both finds the shortest path from s to each node, and that it will include all nodes when it terminates through induction.

For Dijkstra’s algorithm to work, the edges must have positive lengths. It can also be observed that it is a “continuous version” of breadth-first search. Now, we look at the runtime of this algorithm. We know that it will execute n-1 times for a graph with n nodes. To find the path to the next node we need to check each edge, which means this would take O(m) time, and for each node O(mn) time. The use of additional data structures, however, can improve this runtime. If we use a priority queue to hold the nodes and then remove them when they are explored, it can reduce this runtime to O(m) time. Implementing the heap-based priority queue takes O(log n) time, so the overall time for this algorithm would take O(m log n) time.

This section applies an exchange argument to solve the Minimum Spanning Problem. The minimum spanning problem occurs when there is a set of locations that can be represented through nodes and we want to create a network on top of those locations. The network should be connected, having a path between each location, with the goal of creating the “cheapest” network possible. Pairs can be linked together for a specified, positive cost. The links can be represented though edges on the graph. To create the “cheapest” network, we want to keep c as small as possible. Here, we can assume that the graph is fully connected.

We know that the minimum-cost solution to this problem can be turned into a tree, (V, T), where V are the locations and T is the solution to the problem. (V, T) must be connected by definition, and we need to show that it does not contain a cycle. To prove that there are no cycles, we use a proof by contradiction. Assuming there is some edge in a proposed cycle, the tree without that edge is still connected as any path with that edge can now find a longer path around the rest of the cycle instead. This also in turn solves the problem and is less expensive, which gives us a contradiction.