Review Problems for Prelim II

CS 482 - Spring 2005

Our second prelim takes place on Tuesday, Apr 12, from 7:30 to 9:00pm. The exam takes place in Olin 155 (the large lecture hall downstairs from our normal meeting place).

The exam includes material from lecture and from assigned reading up through Friday, April 8.  See the Schedule for the sections of the text assigned for reading (this includes most of Chapters 1 through 8); although we have discussed material from Chapters 9 and 10 this material will not be included on the exam.  The exam is primarily about Network Flow and NP-Completeness (i.e., the topics covered since Prelim I), but the exam is cumulative and includes material from the earlier chapters (Stable Matching, Basics of Algorithms Analysis, Graphs, Greedy Algorithms, Divide & Conquer, and Dynamic Programming).

Prelim II 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.9 of the text.

The questions below are meant to help you study for the prelim. They will not be collected and they will not be graded. The lecture on Monday, Apr 11, is meant to be a review session; this would be a good time to ask about any of these review questions. You are also welcome to ask about these questions during any of the course office hours. The text has many more questions (some easier, some harder) that you are also welcome to ask about.

  1. Problem 1 of Chapter 7: (a) List all the minimum s-t cuts in the network...
  2. Problem 3 of Chapter 7: (a) In the figure below is a flow network,...
  3. Problem 8 of Chapter 7: Statistically, the arrival of spring typically results in...
  4. Problem 11 of Chapter 7: Your friends have written a very fast piece of maximum flow code...
  5. Problem 1 of Chapter 8: For each of the two questions below, decide...
  6. Problem 2 of Chapter 8: A store trying to analyze the behavior of its customers...
  7. Problem 7 of Chapter 8: Since the 3-DIMENSIONAL MATCHING problem is NP-complete,...
  8. Problem 10 of Chapter 8: Your friends at WebExodus have recently been doing some consulting work...
  9. Problem 11 of Chapter 8: As some people remember, and many have been told, the idea of hypertext...
  10. Problem 20 of Chapter 8: There are many different ways to formalize the intuitive problem of clustering...
    (This last one is a bit harder than would be asked on an exam.)

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

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