Review Problems for the Final Exam

CS 482 - Summer 2007

Our Final Exam takes place in class from 8:30 to 11:00am on Friday, Aug 17.

The exam includes material from lecture and from assigned reading up through Thursday, Aug 16. 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. 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 2 of Chapter 11: At a lecture in computational biology one of us attended...
Problem 8 of Chapter 11: Some friends of yours are working with a system that performs...
Problem 9 of Chapter 11: Consider the following maximization version of the 3-Dimensional...
Problem 2 of Chapter 13: Consider a country in which 100,000 people vote...
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...

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