CPSC 311: Review for Final Exam
Spring 2004
You may bring two 8.5-by-11 inch sheets of paper with your own
notes on it to the exam. You may write on both sides.
The exam is cumulative.
However, there will be especial focus on the material since Exam 2.
In addition to the list of things to review for Exams 1 and 2,
review the following:
- Notes for lectures since April 12 (NP-completeness and
approximation algorithms).
- Readings:
Ch 34 (you can skip the material on pp. 987-994 about
circuit satisfiability and the proof of Theorem 34.9);
Ch 35 through Sec 35.2.
- Homework problems and their solutions.
The format of the final exam will be like the midterms.
In addition to the lists of things to know for Exams 1 and 2,
here are some suggestions for things to know:
- Definitions of the complexity classes P, NP and NP-complete
(including notion of a polynomial reduction/transformation)
and their importance.
- Implications of the existence of a polynomial reduction
from language (problem) L1 to language (problem) L2.
- Implications of a language (problem) L being NP-complete.
- How to show a language (problem) is NP-complete using reduction.
- Definition of SAT and fact that SAT is NP-complete.
- Definitions of 3SAT and VC (vertex cover) and idea of how to
show that they are NP-complete.
- Relationships between VC, IS (independent set) and CLIQUE
and how to show one is NP-complete given that another is.
- Definitions of optimization, minimization and maximization problems.
- Definition of a (polynomial time) approximation algorithm.
- Different ways to measure the performance of an approximation algorithm
(e.g., ratio bound).
- Min VC approximation algorithm and its analysis.
- Definition of TSP with triangle inequality problem, its approximation
algorithm and its analysis.
- Proof that if there is a (polynomial time) approximation algorithm
for the general TSP problem, then P would equal NP.