CS 46 Comprehensive Final Exam is scheduled for Friday, 8 May 9am-12n in Sci 264.

Due: Wednesday, April 22

1. Write solutions to: 6.2.4, 7.2.2, 7.3.4e, 7.3.4h
   
   For the two 7.3.4 problems, I want you to prove that they are NP-complete. For each, I would prefer that you argue that it is in NP and then use a reduction to show that it is NP-complete. You do not have to treat these as generalizations of known NP-complete problems unless you want to.
   
   Note: In 7.3.4e, the index under the sigma should be j.
   
   You can get Cook's paper by going to tripod;
   put acm digital in a title search and click go
   Click on:
   Connect to ACM Digital Library from SWARTHMORE
   Under Publication Click on Proceeding
   in find publication field, put
   Annual ACM Symposium on Theory of Computing
   Select 1971 in both the published since and published before fields
   Scroll down to:
   The complexity of theorem-proving procedures
   Stephen A. Cook
   and click on
   pdf