Topics for COSC 157 Final Exam

The final exam will be held in our usual classroom at
1:00PM (until 3:00) on Monday, December 10.
The exam will be cumulative, so you should be sure to review
topics for the first two exams.  Since then we've covered
Chapters 4 (except 4.5), 5, and 6.  Specific topics include:

Turing Machines
  Stating and interpreting the Church-Turing thesis.
  Computing a trace of a Turing machine.
  Read and write modular diagrams for defining Turing machines

Variations on Turing Machines  
  Know common variants such as multiple tapes, multiple heads, ...
  Showing that a given variant can be simulated
    by a standard (single tape) machine.
    
Nondeterministic Turing Machines
  Know that dovetailing can be used to simulate a nondeterministic
    machine on a deterministic one.

Universal Turing Machines
  Know what a universal machine is and approximately how
    one operates.
    
Halting Problem
  Be able to state the Halting Problem and know that it defines
    and undecidable language.
    
Rice's Theorem
  Identify functional properties of programs.
  Know the statement and meaning of Rice's Theorem (p.168).
  
The class P
  Know the definition of the class P.
  Know there are languages not in P.
  
The class NP
  Know the definition of the class NP.
  
P=NP?
  Know what this question means and why it's important.
  Know that the Clay Mathematics Institute is offering
    $1,000,000 for its solution.
    
NP-complete
  Know the definition of NP-complete.
  Be familiar with the problems HC, C, SS, SAT, and 3-SAT.
  Be able to describe a polynomial-time reduction from one
    problem to another (such as Exercises 6.6, 6.8 on p. 196).