Chapter 4

Section 4.1 covers the introduction to greedy algorithms using the basic “staying ahead” mentality. There are two specific algorithms that are introduced in this section. The first is the interval scheduling algorithm which returns the optimal schedule of intervals from some given set of intervals. The algorithm works by finding the interval that has the earliest finishing time, removing all intervals that conflict with the chosen intervals, and then recursing through the remaining intervals until there are not left. The run-time of this algorithm is O(nlogn).

The second algorithm schedules all intervals in an optimal fashion such that the number of resources used is no more than the depth of the intervals. The algorithm works by going through each interval and removing any other intervals that conflict with it. Then, after excluding all of the conflicts, the algorithm stitches together the remaining intervals together so that the fewest resources have to be used.

I give this chapter a 6 for readability since the proofs were sometimes hard to understand a 7 on the interesting scale.

Section 4.2 covers the design and creation of an algorithm that minimizes lateness in job scheduling. The algorithm itself is surprisingly simple, it arranges jobs in the order of their finish time. Even though this algorithm completely ignores the other half of data, the length of each job, it is shown in the rest of the chapter through various proofs that the algorithm always produces an optimal solution.

This section was a much tough read than many of the other sections since so much of it was taken up by the proofs which I personally find much harder to read. As such, I give this section a 4 on readability and a 6 on the interesting scale.