Hw 8, due Friday 26/10

Reading: all of chapter 34, except for the presentation based on
languages.  Well, if you you really want you may give the definitions
as in the book, but it would be preferable if you give definitions as
taught in class.

1.  Solve exercise 34.5-6.  Showing that HP is in NP should be
    straightforward.  To show that HP is NP-hard there are 3
    possibilities: (1) Reduce from Hamiltonian cycle which we have
    already proved to be NP-complete, (2) Modify the proof of HC being
    NP-hard so that it applies to HP.  (3) Use the generalized notion
    of reducibility described in the last homework, if you find that
    more convenient.

2.  Problem 34-4 (scheduling with profits and deadlines).

3.  The input to the bin-packing problem is a sequence of object
    weights x[1..n], a bin capacity C, and a target number k of bins.
    The question whethe the objects can be placed in the bins so that
    the capacity of no bin is exceeded, and at most k bins are used.

    Show that this is NP-complete

(In all the above problems, you may assume that Graph colouring,
Hamiltonian cycle, Independent Set, Vertex cover, set cover, 3sat are
NP-complete.  Except for graph colouring, we have essentially proved
the np-completeness.  Problem 34-3 shows how to prove np-completeness
of graph colouring in case you are interested.)


----