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)