Reading Assignments

From M. Sipser's Theory of Computation , 3rd Edition (unless otherwise noted) and Nigel Cutland's Computability .

• Week of January 23rd Chapter 0, pages 1-16 (Review of Sets, Functions, and Logic), Section 6.3 (definition of Turing reducibility), Pages 234-235 (Mapping Reducibility Definition)
• Week of February 5th The Classes P and NP, NP-Completeness (Sections 7.1, 7.2, 7.3, 7.4)
• Week of February 12th NP-Completeness and NP-Complete Problems (Sections 7.4, 7.5)
• Week of February 26th URM Model of Computation, URM computable and decidable predicates, Program Encodings (Cutland: Sections 1.1-1.4, 4.1-4.3)
• Week of March 4th SMN Theorem, Universal Programs, Diagonalization Method (Cutland Sections 4.4, 5.1, Sipser pages 202-209)
• Week of March 11th Diagonalization Method, Kleene's 2nd Recursion Theorem (Sipser pages 202-209, Section 6.1)
• Week of March 18th Kleene's 2nd Recursion Theorem (Sipser pages 202-209, Section 6.1)
• Week of April 8th. Deterministic Finite Automata (Sipser, Section 1.1)
• Week of April 15th. Nondeterministic Finite Automata (Sipser, Section 1.2)
• Week of April 22nd. Closure under the Regular Operations, Regular Expressions (Sipser, Section 1.2 pages 58-62, Section 1.3)
• Week of April 29th. Language Equivalence between Regular Expressions and DFA's, Context Free Grammars (Sipser, Sections 1.3 and 2.1)
• Week of May 6th. Deterministic and Nondeterministic Turing Machines (Sipser, Section 3.1 and 3.2)