Reading Assignments

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

• Week of January 29th Diagonalization Method (pages 202-209), Kleene's 2nd Recursion Theorem (Section 6.1)
• Week of February 12th Kolmogorov Complexity (Section 6.4)
• Week of March 15th Mapping Reducibility, classes P and NP, NP-completeness, NP-completeness reductions (5.3,7.1-7.5)
• Week of March 22nd Review of Turing Machines, Cook's Theorem, Space Complexity (3.1, 3.2, 7.5 Cook-Levin Theorem and onward, 8.1)
• Week of March 29th Review of Cook's Theorem, Space Complexity, Savitch's Theorem, Logspace (7.5 Cook-Levin Theorem and onward, 8.1, 8.2)
• Week of April 12th Context-Free Languages (Section 2.1)
• Week of April 19th Polynomial Space Complexity (Section 8.2, 8.3)
• Week of April 26th Logarithmic Space Complexity (Section 8.4,8.5, 8.6)