Course Information: Computation Theory

This course is intended as an introduction to the theory of computation for senior level undergraduates and graduate students looking for background material in theory. The major topics within the course include: models of computation, finite automata, regular languages, context free grammars, Turing machines, undecidability, infeasibility, diagonalizations, nondeterminism, time and space, and complexity classes.

Class information: Details of COMP 170 can be found in a number of places:

Prerequisites: MATH/COMP 61 and COMP 15 are recommended, but any prior course with rigorous mathematical proofs should suffice.

Textbook: Introduction to the Theory of Computation by Michael Sipser
ISBN: 9781133187790 (3rd Edition) or 9780534950972 (2nd Edition)
List of errata: Errata for 3rd Edition and Errata for 2nd Edition

Instructor: Marty Allen
Email: martin.allen@tufts.edu
Office: 237 Halligan Hall (office hours online this term)
Office Hours: see hours here

Class Location: Online (Zoom link on Canvas)
Time: Monday/Wednesday, 6:00 – 7:30 PM

Questions about the Course? The best place to get questions answered is via the course Piazza page. Email will not be used to answer questions requiring lots of detail. Start with office hours and Piazza.

Teaching Assistant (office hours here):
Rui Chen