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, information theory, time vs space, and complexity classes.

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

Primary Textbook: Introduction to the Theory of Computation by Michael Sipser
Other Reading: Gödel's Proof by Ernest Nagel and James Newman
Other Reading: The Annotated Turing by Charles Petzold

Instructor: Megan Monroe
Email: mmonroe@cs.tufts.edu
Office: Joyce Cummings Center, Room 440D
Office Hours: Wednesday, 2:00-4:00pm

Class Location: Joyce Cummings Center, Room 270
Time: (Tues/Thurs) 1:30 - 2:45am
Final Exam: Monday, December 19th, 3:30-5:30pm

Course Piazza: CS170 Fall 2022

Teaching Fellows:
Alexandra Scott
Claudia Aranda Barrios
Abby Larsen