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.

- Problem 1 of Chapter 7: (a) List all the minimum
*s-t*cuts in the network... - Problem 2 of Chapter 7: Figure 7.26 shows a flow network...
- Problem 9 of Chapter 7: Network flow issues come up in dealing with natural disasters...
- Problem 11 of Chapter 7: Your friends have written a very fast piece of maximum flow code...
- Problem 1 of Chapter 8: For each of the two questions below, decide...
- Problem 3 of Chapter 8: Suppose you're helping to organize a summer sports camp,...
- Problem 8 of Chapter 8: Your friends' preschool-age daughter...
- Problem 10 of Chapter 8: Your friends at WebExodus have recently been doing some consulting work...
- Problem 11 of Chapter 8: As some people remember, and many have been told, the idea of hypertext...
- 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:

*Independent Set*: Given a graph G and a number k, does G contain an independent set of vertices?*Set Packing*: Given a set U of n elements, a collection S_{1}, ..., S_{m}of subset of U, and a number k, does there exist a collection of at least k of these subsets such that no two of them intersect?*Vertex Cover*: Given a graph G and a number k, does G contain a vertex cover of size at most k?*Set Cover*: Given a set U of n elements, a collection S_{1}, ..., S_{m}of subset of U, and a number k, does there exist a collection of at most k of these subsets whose union is all of U?*3-Dimensional Matching*: Given disjoint sets X, Y, and Z, each of size n; and given a set T of ordered triples of the form (x, y, z), does there exist a set of n of these triples so that each element of X, Y, and Z is contained in exactly one of these triples?.*Graph Coloring*: Given a graph G and a bound k, does G have a k-coloring?*Hamiltonian Cycle*: Given a directed graph G, does it contain a Hamiltonian cycle?*Hamiltonian Path*: Given a directed graph G, does it contain a Hamiltonian path?*Traveling Salesman*: Given a set of distances on n cities, and a bound D, is there a tour of length at most D?*Subset Sum*: Given natural numbers w_{1}, ..., w_{n}, and a target number W, is there a subset of {w_{1}, ..., w_{n}} that adds up to precisely W?*3-SAT*: Given a set of clauses C_{1}, ..., C_{k}, each of length 3, over a set of n boolean variables, does there exist a satisfying truth assignment?