CSCI 4470/6470 Algorithms (Fall 2006)

Homework Assignment #7 ( Due Thursday November 30, 2006)

(Total: 150 points)

  1. (25 points) Problem 34.2-1 on page 982 (hint: strictly follow the definition of the class NP).

  2. (25 points) problem 43.2-5 on page 983 (hint: you need to use the definition of the class NP).

  3. (25 points) Problem 34.3-2 on page 994 (hint: strictly follow the definition of the polynomial-time reduction).

  4. (25 points) Problem 34.3-7 on page 995.

  5. (50 points) Problem 34-3 (all questions) on page 1019