CPSC 421/501: This is a description of specific topics covered in
class and the homework (sample exam problems).

Notation:
When "Sipser 3.1" is written, this means the entire subsection 3.1.
When "Sipser 3.2 (k-tape machines)" is written, this means that we
only covered the part of Section 3.2 concerting k-tape machines; see
the Table of Contents (which is quite detailed) in Sipser's textbook.

--------------------------------------------------------

*** September 3-19: 

  "Uncomputability and Self-Referencing in CPSC 421:" the entire
  handout except for the reduction of the Halting problem to the
  Acceptance problem using Axiom 6, which will be left to the homework
  and sample exam problems.
  
  This includes many topics covered in Sipser 4.2, except that we
  hadn't defined a Turing machine.

*** September 22-29: (Idea: get to P versus NP and Polynomial Time Hierarchy
                      most directly.)

  Sipser 3.1,3.2 (k-tape Machines),
  Discussion of PALINDROME (see blog)
  3.3 (Terminology for describing Turing machines).
  4.2 (Make sure that Turing machines satisfy the axioms of 
    "Uncomputability and ... ")
  7.1, 7.2, 
  9.1 (Theorem 9.10: Time hierarchy theorems.)
  3.3 (Non-deterministic machines) and 7.3.

*** After the midterm: 

  7.3-7.5 (Cook-Levin Theorem and NP Completeness)
  Some of Chapters 8 and 9--see the handout on the course webpage.
  Some of Chapter 1--see the handout on the course webpage.