CS 5114 Homework 7 (Spring 2009)

Assigned on Thursday, April 30, 2009. You do not have to turn in solutions, since I will not be grading this homework. I will provide the "official" solutions on Tuesday, May 5, 2009.

Many of these exercises involve proving that some problem or the other is NP-complete. Make sure you prove the reduction in the right direction. In your reductions, you may use any problem that the textbook proves is NP-complete in Chapter 8, even if we did not consider that problem in class. Be sure to state what the problem is and which chapter in the textbook proves its NP-completeness. Also prove the running time of the transformation.

Some exercises also involve describing an algorithm. The same rules apply to these exercises as in previous homeworks. Describe your algorithms as clearly as possible. The style used in the book is fine, as long as your description is not ambiguous. Do not make any assumptions not stated in the problem. If you do make any assumptions, state them clearly, and explain why the assumption does not decrease the generality of your solution. If you use any new words or phrases, define them, especially if we have not used these words/phrases in class. Do not describe your algorithms only for a specific example you may have worked out. You must also provide a clear proof that your solution is correct (or a counter-example, where applicable). Describe an analysis of your algorithm and state its running time.

  1. (10 points) Solve exercise 6 in Chapter 8 (page 507) of your textbook.
  2. (30 = 15 + 15 points) Solve exercise 10 in Chapter 8 (pages 508-509) of your textbook.
  3. (30 = 15 + 15 points) Solve exercise 19 in Chapter 8 (pages 514-515) of your textbook.
  4. (30 points) Solve exercise 37 in Chapter 8 (pages 526-527) of your textbook.