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.
- 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 S1,
..., Sm 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 S1,
..., Sm 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 w1, ..., wn,
and a target number W, is there a subset of {w1, ..., wn}
that adds up to precisely W?
- 3-SAT: Given a set of clauses C1, ..., Ck,
each of length 3, over a set of n boolean variables, does there exist a
satisfying truth assignment?