Reading Assignments

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

• Week of April 27th: Turing Machines (Chapter 3 Section 2)
• Week of April 20th: Turing Machines (Chapter 3 Section 1)
• Week of April 13th. Context Free Languages and Grammars (Section 2.1)
• Week of April 6th Regular Expressions and their equivalence with Finite Automata (Section 1.3)
• Weeks of March 16th and 23rd Language Operations and Regular Expressions (Section 1.3)
• Weeks of March 2nd and March 9th Deterministic and Nondeterministic Finite Automata (Sections 1.1, 1.2)
• Week of February 23rd NP-Completeness, NP-Complete Problems (Sections 7.4-7.5)
• Week of February 9th Measuring Complexity, Complexity Classes P and NP (Sections 7.1-7.3)
• Week of February 2nd Definition of mapping reducibility (Pages 234-235)
• Week of January 20th Review of Sets, Functions, and Logic (Chapter 0, pages 1-16)