and the
Theory of

Fall 2019


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

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

31 Oct Plan /cours /fall2019 /formal_languages /syllabus
last modified Thu February 29 2024 9:20 am