Chapter 4 - Greedy Algorithms

The section begins by bringing back a problem from earlier in the text: the Interval Scheduling Problem. In this problem, we are given a set of requests with start and finish times, and we are asked to find the largest subset of requests such that none of the times overlap. We want to devise a greedy algorithm to solve this problem.

The book walks through the different strategies we could use: ordering by start times, total time intervals, basing intervals on other intervals, and finally, finish times. It turns out that by ordering the requests by finish times, we have a greedy algorithm that matches the optimal solution.

The algorithm begins with a while loop on the set of all requests R. It says that while that set is nonempty, we choose the request with the smallest finishing time, we add that request to our set A (which will contain the solution), and then delete all requests from R that are not compatible with the request we just added to A. This algorithm is intuitive, and the book walks through the proof behind it well. Finally, the text diagnoses the runtime of the algorithm which is O(nlogn). Note that the runtime here is caused by ordering the finish times in sorted order, which we know takes O(nlogn) time.

Next, the book moves on to a similar problem. Here, we are given another set of requests, and we wish to schedule all of these requests using as few resources as possible. The book provides a good example to contextualize this using the idea that if we are given a set of class times, how many classrooms will we need to accommodate these class times. The text proves the intuitive fact that the number of resources needed is at least the depth of the set of intervals.

The algorithm follows similarly from the algorithm produced earlier in the section. First, we sort the intervals by their start times. As we progress through these sorted intervals j = 1,2,…,n, for any two intervals that are overlapping, we exclude the label from the preceding (earlier) interval I_i from consideration with the later interval I_j (in the same resource). And then if there is a label that has not been excluded during this call of the for loop, we assign a nonexcluded label to I_j. If there does not exist such a label, we leave I_j unlabeled.

The book does not diagnose the runtime of this algorithm. However, it does analyze the algorithm, ultimately concluding that the algorithm will schedule every interval on a resource, using a number of resources equal to to the depth, which was not as clear before reading the section carefully.

This section was long, and hard to follow at times. I would rate the readability at 5/10.

This section begins by slightly manipulating the interval scheduling problem such that each request is given a time t and a deadline d. Our goal is to minimize the maximum lateness of the requests. The text walks through a few different strategies for solving this problem. It spends some time attacking the strategy of ordering by the amount of time each request takes and the strategy of ordering by slack time (d - t). It then concludes that the clear choice to produce an optimal solution is ordering by increasing deadlines. The text then walks through an algorithm will it claims will accomplish this.

The algorithm first orders the jobs in order of their deadlines. It then considers each job in this sequence, creates a start and finish time for each job by using the information given, and returns the set of scheduled intervals after conducting this loop.

It then walks through the long and dwindling proof that this solution is indeed optimal. It does this by using an exchange argument. The exchange argument is used by defining something called an inversion. An inversion is a pair of jobs i and j such that j is scheduled immediately after i and has d(j)<d(i). The text takes an optimal schedule, supposes it has inversions, and then shows by eliminating these inversions, we still have an optimal schedule (minimizing maximum lateness) which is identical to the schedule which is created by the algorithm. We know this because the algorithm produces a schedule with no inversions.

I would rate the readability of this section at 8/10. It was interesting and a helpful supplement to what we learned in class.

This section begins by laying out its purpose: to apply a greedy algorithm to the problem of trying to find the shortest path in a graph. The problem is then further defined: given a start node s, what is the shortest path from s to each other node?

It turns out that Edsger Dijkstra created a greedy algorithm to solve this exact problem in 1959. The algorithm keeps track of a set S of vertices u. For each one of these nodes, the set also maintains the shortest distance from s to each one of these other vertices u as d(u). Initially, we let S={s} and d(s) = 0. And for each node v in V-S, where V is the set of vertices in the graph, we find the shortest path that can be created by traveling through the vertices in S to the new node v before adding it to S. For some node u in S, there will be a path (u,v) such that d(v) = d(u) + length(u,v) where d(v) is the shortest path to v from s.

I found this algorithm confusing in class, but the text helped to clear things up in Figure 4.7, laying out a very simple example of the next choice Dijkstra's algorithm would take.

The text goes on to prove that Dijkstra's algorithm will indeed drive the shortest path from s to any other node u in the graph. I found this proof straightforward. The text also notes two key facts about the algorithm: (1) that it does not work if paths have negative distances and (2) that is is truly a continuous version of the breadth-first search. (2) helps clear up the intuition behind the algorithm because, intuitively, I would think that the way to find the shortest path from one node to another would be to simply run a BFS on that node.

The book then walks through the implementation of the algorithm. It ultimately concludes that by using a priority to queue to hold the nodes V with the distances as the keys for each node, we can reduce the running time of Dijkstra's algorithm to O(m), rather than O(nm) with sloppy implementation.

I would rate the readability of this section at 8/10. Although I found it difficult to follow at times, I think it is just because Dijkstra's algorithm is slightly more complex than what we have covered in the past. Although, once it became clear to me the exact intuition behind it, I began to read much more fluidly with more comprehension and interest.

This section begins by illustrating the problem: we have a set of locations and we want to build a communication network between them with the least cost possible. This then leads us to the idea of the minimum spanning tree because, in reality, we are searching for the cheapest spanning tree of a given graph.

The section then walks through three different approaches to solving this problem (which are all efficient and correct): Kruskal's Algorithm, Prim's Algorithm, and the Reverse-Delete Algorithm. Before going into detail as to what each of these does, I want to lay out the properties essential for proving these algorithms work. First, the book lays out and proves the cut property: this says that if we have two subsets of nodes, and there is an edge e with the minimum-cost with one end in one set and the other end in the other set, then every minimum spanning tree on that graph must contain that edge e. I found the book's proof of the cut property very helpful and intuitive. Now, with this property, the text makes it clear that we are able to prove the optimality of Kruskal's and Prim's algorithms.

Krukal's algorithm works by taking the graph, disconnecting the edges, and then adding the edges back in ascending order until we arrive at a minimum spanning tree. This, intuitively, makes sense and I found the proof of its optimality clear, with the usage of the cut property.

Prim's algorithm works very similarly to Dijkstra's algorithm. It starts with a root node s and greedily grows a tree outward from s. However, at each step, we just add in the node to the tree which yields the least cost. The book uses the cut property to prove the optimality of this, as well.

Then, the book walks through the cycle property, which I felt I had a solid grip on from class. The cycle property says that if a graph has a cycle C, then the most expensive edge in that cycle cannot possibly belong to the minimum spanning tree of that graph.

The book uses this property to explain the optimality of the Reverse-Delete Algorithm: this algorithm starts with the fully connected graph, and progressively deletes the largest edge in the graph until reaching a minimum spanning tree (obviously not deleting an edge which would disconnect the graph).

The book ends the section with, first, discussing the implementation of Prim's algorithm, which follows fairly intuitively from Dijkstra's algorithm. It uses a priority queue to contain the nodes with attachment costs of those nodes as the keys. This was a nice reminder from what we covered in class, as implementation details can sometimes be difficult to grasp.

The book concludes the section discussing extensions of the minimum spanning tree problem. One suggestion that jumped out at me, in particular, was the idea of making resilience an explicit goal when designing a tree. What would an algorithm for designing a tree which stayed connected through any particular edge deletion look like? If we were designing a power grid for a neighborhood, this is what kind of structure we would want, as power lines are bound to come down at some point. We would want houses to maintain power even if something like this happened.

I would rate the readability of this section at 9/10. It was interesting material and the proofs were straight-forward.

This section through the background of the Union-Find data structure in order to reach an implementation of Kruskal's Algorithm, which I discussed in the previous section.

In order to implement the algorithm, the book lays out what operations we would like our data structure to be able to accomplish. The first operation is MakeUnionFind, which returns all elements in sets, which we want to run in O(n) time. The second is, for some u in S, Find(u), which returns the name of the set containing u. And we want this to run in O(log n) time. And finally, for two sets A and B, we want to be able to join them using an operation called Union(A,B) and run in O(log n) time.

The book walks through two approaches for implementation of this structure. The first approach is an array implementation. I like the strategy the text uses for proving that the union operation runs the time it does. Rather than focusing on worst-case run time for every call, it focuses on the total running time a for a sequence of operation, which turns out to be O(k log k). But I preferred the book's second implementation option, which uses pointers to nodes to maintain sets. When two sets are joined in a union, the pointer of the smaller set then points to the location of the pointer of the larger set, which implements union in O(1) time. But this increases the runtime of finding a node to O(log n) time as one must cycle through at most log(n) pointers in order to reach the node being sought.

The book walks through the implementation of Kruskal's algorithm using this data structure, but also notes that the current version we have of the union-find data structure could be improved, but is not necessary for the implementation of the algorithm. This is because the bulk of the running time of the algorithm comes from sorting the edges in ascending order (which we need to use the algorithm) which runs in O(m log m) time. The book also notes that O(m log m) is the same as O(m log n) since m ⇐ n^2.

I would rate the readability of this section at 8/10.