CPSC 433: Review for Final Exam
Spring 2006

You may bring two 8.5 by 11 inch sheets of paper to the exam with your notes on them. You may write on both sides.

In addition to the material listed on the review sheets for Exams 1 and 2, review the following:

• Lectures since March 28.

• Readings:
  • Ch 9 (skip sec 9.4 and sec 9.5)
  • Ch 10. Read it all except:
    • skim sec 10.1.2
    • skip sec 10.2.2 and sec 10.2.3 (just remember that SAT is NP-complete),
    • skip sec 10.3.2 (just remember that CSAT is NP-complete)
    • skip sec 10.3.3 (just remember that 3SAT is NP-complete)
    • skip sec 10.4.4 (just remember that HC is NP-complete)
    • skip sec 10.4.5 but do read the part on p. 461 about TSP

• Quizzes 10-12 and their solutions (given in class)

• Homework assignment 6 and its solutions (provided in class)

The format of the exam will be some short answers and some "work-out" problems. Difficulty will be in between the quizzes and the homework. Here are some suggestions for things to know:

• definitions of decision problem, decidable and undecidable

• Church-Turing thesis: TMs can compute anything we would think of as being computable

• know in principle how to encode a TM as a binary string (details are not important); this implies that all TMs can be listed (in an infinite list)

• definition of L_d, the diagonalization language; how to show it is not r.e.

• recursive languages are closed under complement

• if L and its complement are both r.e., then both are recursive

• definition of L_u, the universal language; how to show it is r.e. but not recursive

• definition of the halting problem; how to show it is r.e. but not recursive

• definition of problem P1 reducing to problem P2 and the implications thereof regarding decidability (and "r.e."-ness) of the two problems

• definition of a nontrivial property of the r.e. languages; statement (but not proof) of Rice's theorem; how to use Rice's theorem to prove that certain languages are not recursive

• Definitions of time complexity for deterministic and non-deterministic Turing machines, big-oh notation, polynomial time for DTMs and NTMs, the sets P and NP.

• Why it is reasonable to think of P as the "tractable" problems.

• Why the question whether P equals NP is of practical importance.

• Definition of polynomial time reduction and its implications.

• Definition of NP-complete and its implications.

• Definitions of TSP, HC, SAT, CSAT, 3SAT, IS, NC (also called VC for vertex cover).

• Statement of Cook's theorem.

• Know the two ways to show a problem is NP-complete: directly with brute force vs. using a reduction. For reductions, be sure to get the direction correct!

• Show a problem is not recursive or not r.e. using a reduction

• Show a problem is NP-complete using a reduction.

• Given a language, figure out how to classify it (regular, context-free, recursive, r.e., not r.e.) and prove it. For instance, if you decide a language is context-free but not regular, you could, for example, show a context-free grammar for the language and use the pumping lemma for regular languages to show that it is not regular.