time: Tues/Thurs 10:00am - 11:30am place: Sci 217 level: advanced credits: 4 faculty: Jim Mahoney & Matt Ollis text: Introduction to the Theory of Computation, 2nd Edition, Michael Sipser, ISBN 8131501620 e.g. http://www.amazon.com/dp/8131501620
A mathematical introduction to the theory of computation. Topics include automata such as Turing machines, formal languages such as context-free grammar, and computability questions as described by "NP-complete" problems and Godel's incompleteness theorem. This is an upper-level course that presents the foundations of theoretical computer science. Expect practice with lots of mathematical proofs, with programming examples to build intuition. Prerequisite: Formal mathematics and programming experience
Here is an approximate schedule. The interests and abilities of the class may steer us in a different direction; we'll see.
1 math and programming preliminaries 2 finite automata 3 regular languages 4 context-free grammars 5 pushdown automata 6 Turing machines 7 what is an algorithm 8 decidable languages 9 the halting problem 10 reducibility 11 P and NP 12 NP-completeness 13 course round-up