Review Problems for the Final Exam

CS 482 - Spring 2007

Our Final Exam takes place 9:00 - 11:30 am on Thursday, May 17, in Hollister B14.

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 11 and 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.10 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: In Exercise 5 of Chapter 8, we claimed that the Hitting Set Problem...
Problem 1 of Chapter 11: Suppose you're acting as a consultant for the Port Authority of...
Problem 8 of Chapter 11: Some friends of yours are working with a system that performs...
Problem 10 of Chapter 11: Suppose you are given an n-by-n grid graph G...
Problem 3 of Chapter 13: In Section 13.1, we saw a simple distributed protocol to...
Problem 4 of Chapter 13: A number of peer-to-peer systems on the Internet are based...
Problem 7 of Chapter 13: In Section 13.4, we designed an approximation algorithm...

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 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?