Review Problems for Prelim II

CS 482 - Spring 2007

Our second prelim takes place on Tuesday, Apr 10, from 7:30 to 9:00pm. The exam takes place in Hollister B14.

The exam includes material from lecture and from assigned reading up through Monday, April 2.  See the Schedule for the sections of the text assigned for reading (this includes most of Chapters 1 through 9); although we have begun discussing material from Chapter 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 9, 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 2 of Chapter 7: Figure 7.26 shows a flow network...
  3. Problem 9 of Chapter 7: Network flow issues come up in dealing with natural disasters...
  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 3 of Chapter 8: Suppose you're helping to organize a summer sports camp,...
  7. Problem 8 of Chapter 8: Your friends' preschool-age daughter...
  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: