syllabus
time: Tues/Thurs 10:00 - 11:20am
place: Sci 217
level: advanced
credits: 4
faculty: Jim Mahoney, Matt Ollis
text: Introduction to the Theory of Computation, 2nd Edition,
Michael Sipser, ISBN 053494728X
e.g. http://www.amazon.com/dp/053494728X
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, based on how the course played out in 2006. The interests and abilities of the class may steer us in a different direction this time.
Week starting
1 Jan 28 math and programming preliminaries
2 Feb 4 finite automata
3 Feb 11 regular languages
4 18 context-free grammars
5 25 pushdown automata
6 Mar 4 Turing machines mid-term evals due Mar 7
7 Mar 11 what is an algorithm? VT Town Mtg Mar 4
-- spring break --
8 31 decidable languages
9 Apr 7 the halting problem
10 14 reducibility
11 21 P and NP
12 28 NP-completeness
13 May 5 course round-up
reading days May 8 and 9
last work Wed May 14 1:30pm
