Review Problems for the Final Exam

CS 482 - Spring 2005

Our Final Exam takes place 9:00-11:30am on Friday, May 20, in Olin 155 (the same room our other exams have been in; the large lecture hall downstairs from our normal meeting place).

The exam includes material from lecture and from assigned reading up through Friday, May 6. See the Schedule for the sections of the text assigned for reading (this includes most of Chapters 1 through 13 of the text and the text's Epilogue ). The exam includes material from the entire semester. You can expect several questions related to recent material, along with questions on a selection of earlier topics.

The Final Exam 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 final exam. They will not be collected and they will not be graded. You are welcome to ask about these questions during any of the course office hours; office hours will continue up until the final exam. The text has many more questions (some easier, some harder) that you are also welcome to ask about.

Problem 30 of Chapter 8: One thing that's not always apparent when thinking about traditional...
Problem 1 of Chapter 10: Earlier, we considered an exercise...
Problem 8 of Chapter 11: Consider the following maximization version of the three-dimensional matching...
Problem 10 of Chapter 11: Suppose you are given a set of positive integers A=...
Problem 3 of Chapter 12: Suppose you're consulting for a biotech company that...
Problem 4 of Chapter 13: A number of peer-to-peer systems on the Internet are based...
Problem 6 of Chapter 13: One of the (many) hard problems that arises in genome mapping...
Problem 9 of Chapter 13: Suppose you're designing strategies for selling items...

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

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 size at least k?
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?