Chapter 4

This section discusses the Greedy Stays Ahead algorithm. It focuses on maximizing the number of compatible intervals that can be scheduled. It refers to the maximal compatible set as optimal. In designing possible algorithms, it discusses the natural ways we could go about picking a first interval. One not optimal solution is to simply pick the earliest interval, but this does not work. The next idea is picking the shortest interval, but this can not work as well. Another idea that does not pan out is picking the interval with the fewest conflicts. The rule that does work is picking the first interval to end, or the interval with the first end time.

Initially let R be the set of all requests, and let A be empty

While R is not yet empty

→Choose a request i in R that has the smallest finishing time

→Add request i to A

→Delete all requests from R that are not compatible with request i

EndWhile

Return the set A as the set of accepted requests

This is the pseudocode for the algorithm. It can be shown to run in O(nlogn). Extensions of this problem include the problem where we do not know all intervals at the start. This is an online algorithm, which requires making decisions as time progresses. Additionally, we could modify this problem to change the weight, or reward, of certain intervals.

Another problem that is looked into with more depth is the scheduling all intervals problem, or the interval partitioning problem. This problem can be visualized as providing a class room for multiple lectures while using as few class rooms as possible.

Sort the intervals by their start times, breaking ties arbitrarily Sort intervals by starting time so that s1 ≤ s2 ≤ … ≤ sn d = 0 for j = 1 to n if (lecture j is compatible with some classroom k) schedule lecture j in classroom k else allocate a new classroom d + 1 schedule lecture j in classroom d + 1 d = d + 1

This algorithm runs in O(nlogn).

I honestly find these problems very interesting as the idea of solving these optimally with fairly straight forward, intuitive means in a good run time is cool, for lack of a better term. I enjoy learning about these types of problems. We did, however, already learn it in class, so the long reading kind of dragged on. I give this a 5/10.

This section's problem involves having a single resource and using the minimum amount to accomplish the set of tasks that consist of a time requirement and deadline.

The algorithm is as follows:

Order the jobs in order of their deadlines

Assume for simplicity of notation that dl…dn

Initially, f= s

Consider the jobs i=l ….. n in this order

→Assign job i to the time interval from s(i)=f to f(i)=f+ti

→Let f = f + ti

End

Return the set of scheduled intervals [s(i),f(i)] for f= 1 ….. n

This algorithm runs in O(nlogn). An extension of this problem would be allowing for events to have a “release” time or earliest possible start time.

This section is similar to the first, and my thoughts on it mirror that of 4.1. As such, it once again gets a 5/10.

The problem for this section is: given a directed graph with a designated start node, we want to know the shortest path to each of the other nodes. The algorithm solving this problem was presented by none other than Edsger Dijkstra

Dijkstra’s Algorithm (G, l)

Let S be the set of explored nodes

→For each u in S, we store a distance d(u)

Initially S = {s} and d(s) = 0

While S =/= V

→Select a node v not in S with at least one edge from S for which

–>d’(v) = min (e=(u,v):u in S) d(u) + le is as small as possible

→Add v to S and define d(v)=d’(v)

EndWhile

The above pseudocode describes the idea behind the greedy algorithm. In order to actually implement this algorithm, we employ the trusty priority queue using the value d'(v) as the key for v. We can use the heap based priority queue implementation to remove nodes from the queue and reorder the heap as d'(v)'s change. Abusing the logn operations of the heap, we can ultimately manage to implement this algorithm in O(mlogn) for a graph with m edges and n nodes.

Of all of the greedy algorithms we have looked at, while this algorithm is fairly conceptually straight forward, similarly to the others, I find it much harder to actually “perform it” as we did in class. There is significantly more to keep track of as is expected of a graph. Despite this, I actually found this section to be an easier read than the previous ones, so I give this section a 6/10.