(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.
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.
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.