Homework 4 due 7/9/7.  Reading: Chapter 16 except for 16.4.

1.  Consider the activity scheduling problem of 16.1.  Let S[1..n] and
    F[1..n] denote the starting and finishing times.  Assume that the
    numbering is such that jobs are in non-decreasing order of the
    finishing time, i.e. F[i] <= F[i+1].

    Suppose i is smallest such that F[1] < S[i].  Show that {1} U Some
    optimal solution to S[i..n],F[i..n] is an optimal solution to
    S[1..n],F[1..n].  Clearly state which optimal solution to the
    smaller instance you must choose.

2.  Consider the fractional knapsack problem defined in 16.2.
    Consider the space of feasible solutions to this problem.  Define
    a suitable neighbourhood structure.  Use this to show how to make
    the greedy choice.

3.  Exercise 16.2-7.  Define a neighbourhood structure on the feasible
    solutions to derive a greedy algorithm for the problem.

4.  Exercise 16.3-7.

5.  Problem 16-2

(For practice solve all problems in the chapter except those related
to section 16.)