Class 37: Greedy Algorithms, Proving Optimality


Reading
The book's section on greedy algorithms.
Homework
Not to be turned in: Memoize the following function:
(define (F x y z)
  (cond ((= x 0) y)
        ((= y 0) z)
        ((= z 0) x)
        (#t (- (F (- x 1) y z) (F x (- y 1) z) (F x y (- z 1))))))
Don't just do it on paper, implement it! The unmemoized version takes 25 seconds just to figure out that (F 6 6 6) is -1424436. Your memoized version should do that in a flash. Make sure you really know how to do this. Such things will be on the exam.

Lecture
Proving optimality of greedy algorithms
First thing we did in class was to go over the proof (found in last class's lecture notes) of the optimality of the greedy algorithm for activity selection based on the greedy choice of "earliest ending time". Recall, that two things must be proved:
  1. Our greedy choice always appears in some optimum solution to an input problem.
  2. An optimum solution in which our greedy choice appears always includes an optimum solution to the subproblem we get when we update the problem after making our greedy choice.
For this problem (and for many) the second point is pretty obvious, so it is the first point that really needs proof. So that's what we went over in detail.

The homework: Scheduling activities in the fewest rooms possible
We went over the homework that was due today. First we formulated the problem as "choices to make":

  1. choose an activity and a room
  2. schedule the activity in the room
  3. update the problem by removing the activity from the list & recording that the room is unavailable for some period of time
  4. go back to step 1

Next we formulated several greedy choices, and debunked all but "earliest starting activity in first available room". That we couldn't find a counter example for, which led us to think that it might really yield optimum solutions.

Proving optimality of "earliest starting activity in first available room"
To prove the optimality of the "earliest starting activity in first available room" greedy choice, we must prove the two things listed above.
Our greedy choice always appears in some optimum solution to an input problem.
To really understand our algorithm we must realize a few things. By always scheduling the activity with the earliest start time, we will be guaranteed to never have the situation in which there is a "gap" between two scheduled activities in which we can place an unscheduled activity. Why? Because the unscheduled activity must have an earlier start time than the activity on the right side of the "gap", in which case it would have to have been scheduled first. So the situation is impossible. Thus, we can view a problem as consisting of a list of activities, and a list of rooms with different "opening times", where the "opening time" of a room is set equal to the ending time of the latest activity scheduled in that room ... or zero if nothing is yet scheduled in that room.

So, let Ai be the earliest starting activity and let Rj be the first available room in our list of rooms. Suppose there is an optimum schedule in which Ai is not scheduled in Rj. Since all activities are scheduled, Ai must be scheduled in some room Rk. If we swap the activies scheduled in Rj with those in Rk, we have another optimal solution, but one in which Ai is scheduled in Rj. How do we know this schedule is still valid? Because Ai is the earliest starting activity, it must be the first activity in the schedule for Rk, and we know that Rj is available for Ai, that's how Rj was chosen. So it's OK to put Ai the rest of Rk's schedule in Rk. Also, we chose Ai so that no activity started before it, so Rk must be available for any activity, including those currently in Rj. Thus, the new schedule is valid and, since the number of rooms is the same as before, it is an optimum schedule.


Christopher W Brown
Last modified: Thu Mar 31 17:26:45 EST 2005