Review Problems for the Final Exam

CS 482 - Summer 2007

Our Final Exam takes place in class from 8:30 to 11:00am on Friday, Aug 17.

The exam includes material from lecture and from assigned reading up through Thursday, Aug 16.  See the Schedule for the sections of the text assigned for reading (this includes most of Chapters 1 through 11 and 13 of the text and the text's Epilogue).  The exam includes material from the entire semester. You can expect several questions related to recent material, along with questions on a selection of earlier topics.

The Final Exam follows our usual exam rules: closed book; closed notes; no calculators. The exam will include a brief list of NP-Complete problems; this will be an abbreviated version of the list given in Section 8.10 of the text.

The questions below are meant to help you study for the final exam. They will not be collected and they will not be graded. The text has many more questions (some easier, some harder) that you are also welcome to ask about.

  1. Problem 30 of Chapter 8: One thing that's not always apparent when thinking about traditional...
  2. Problem 1 of Chapter 10: In Exercise 5 of Chapter 8, we claimed that the Hitting Set Problem...
  3. Problem 2 of Chapter 11: At a lecture in computational biology one of us attended...
  4. Problem 8 of Chapter 11: Some friends of yours are working with a system that performs... 
  5. Problem 9 of Chapter 11: Consider the following maximization version of the 3-Dimensional...
  6. Problem 2 of Chapter 13: Consider a country in which 100,000 people vote...
  7. Problem 4 of Chapter 13: A number of peer-to-peer systems on the Internet are based...
  8. Problem 6 of Chapter 13: One of the (many) hard problems that arises in genome mapping...

Also, consider taking a look at the earlier Review Problems used for Prelim I and for Prelim II.

The following list of NP-Complete problems will be included within the exam: