Reading Assignments

From the 3rd edition of M. Sipser's Theory of Computation

• Week of August 25th Review of Sets, Functions, and Logic (Chapter 0, pages 1-16), Definition of Turing reducibility (Section 6.3)
• Week of September 1st Definition of mapping reducibility (Pages 234-235)
• Week of September 8th Measuring Complexity, Complexity Classes P and NP (Sections 7.1-7.3)
• Week of September 15th Measuring Complexity, Complexity Classes P and NP, NP-Completeness, NP-Complete Problems (Sections 7.1-7.5)
• Weeks of September 22nd and 29th NP-Completeness, NP-Complete Problems (Sections 7.4-7.5)
• Week of October 6th Deterministic and Nondeterministic Finite Automata (Section 1.1, 1.2)
• Week of October 13th Nondeterministic Finite Automata (Section 1.2), Regular Expressions (Section 1.3)
• Weeks of October 20th and 27th Regular Expressions and their equivalence with Finite Automata (Section 1.3)
• Week of November 3rd. Context Free Languages and Grammars (Sipser Section 2.1)
• Week of November 10th: Turing Machines (Chapter 3 Section 1)
• Week of November 17th: Turing Machines, Decidability (Chapter 3 Page 178, Section 4.1)
• Week of December 1st: Decidabiity, Undecidability and the Diagonalization Method (Chapter 4)