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