syllabus
info
title Formal Languages
and the Theory of Computation
term Spring 2006
credits 4
time TuTh 11:30 - 12:50
place Sci 217
level advanced
faculty Matt Ollis and Jim Mahoney
prereq Math literacy and some programming.
blurb
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.
Often a course like this is entirely proof oriented, but we
also want to play around with some simple programming examples.
Once we see who's enrolled, we'll pick a programming language
that everyone can put up with - perhaps perl or java or
javascript or python or Mathematica.
This is the first time either Matt or Jim has taught this
course, so we'll be feeling our way into just how it's
going to work.
text
- Introduction to the Theory of Computation, by Michael Sipser,ISBN 534950973
resources
schedule
This should give you an idea of the topics we'll be covering and when they'll be covered. We probably won't stick exactly to this timetable.
Week starting
intro classes Tu 17th and Wed 18th
1 Jan 23 math and programming preliminaries
2 31 finite automata
3 Feb 6 regular languages
4 13 context-free grammars
5 20 pushdown automata
6 27 Turing machines mid-term evals due 3/3
7 Mar 6 what is an algorithm? VT Town Mtg Tues 7th
-- spring break --
8 27 decidable languages
9 Apr 3 the halting problem
10 10 reducibility
11 17 P and NP
12 24 NP-completeness
13 May 1 course round-up
reading days May 3 and 4
last work Wed May 10 1:30pm
