Review Problems for Prelim II

CS 482 - Summer 2007

Our second prelim takes place in class on Tuesday, Aug 7.

The exam includes material from lecture and from assigned reading up through Friday, Aug 3. See the Schedule for the sections of the text assigned for reading (this includes most of Chapters 1 through 9). 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, Aug 6, 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.

(Some of the problems below are more difficult than would be asked on an exam.)

Problem 1 of Chapter 7: (a) List all the minimum s-t cuts in the network...
Problem 3 of Chapter 7: Figure 7.27 shows a flow network...
Problems 4 and 5 of Chapter 7: Decide whether you think the following statement...
Problem 11 of Chapter 7: Your friends have written a very fast piece of maximum flow code...
Problem 17 of Chapter 7: You've been called in to help some network administrators...
Problem 1 of Chapter 8: For each of the two questions below, decide...
Problem 2 of Chapter 8: A store trying to analyze the behavior of its customers...
Problem 8 of Chapter 8: Your friends' preschool-age daughter...
Problem 10 of Chapter 8: Your friends at WebExodus have recently been...
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...

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 k vertices?
Set Packing: Given a set U of n elements, a collection S₁, ..., 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₁, ..., 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₁, ..., w_n, and a target number W, is there a subset of {w₁, ..., w_n} that adds up to precisely W?
3-SAT: Given a set of clauses C₁, ..., C_k, each of length 3, over a set of n boolean variables, does there exist a satisfying truth assignment?