CS 46 Theory of Computation Swarthmore College Dr. C. Kelemen Spring 2009 WEEK TOPIC READINGS 1 Mathematical Preliminaries and 1-60 Intro to Finite Automata 2, 3 Finite Automata, Regular Languages, 63-129 Intro to Context Free Languages and Pushdown Automata 4, 5 Pushdown Automata and Context Free 130-173 Languages, deterministic CFLs 6 Turing Machines 179-200 7, 8 Robustness of the TM Model 200-226 Other models of computation, the 227-250 Church-Turing Thesis 9-10 Unsolvable Problems 251-271 11-14 Computational Complexity, NP-complete 275-333 problems, Complexity Hierarchies and notes Space - the final frontier