## Announcements

- Recitations the week of 4/16 are CANCELLED
- You are expected to check the course webpage frequently. Any changes to assignments, errata, office hours, deadlines, snow days, etc. will be posted here!

## Course Information

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

**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:** Megan Monroe

**Email:** mmonroe@cs.tufts.edu

**Office:** Halligan Hall Extension, Room 06

**Office Hours:** Friday 10:00am - 12:00pm

**Class Location:** Braker Hall, Room 001

**Time:** (Tues/Thurs) 9:00 - 10:15am

**Email Address for Questions:**
ta170@cs.tufts.edu

**Teaching Assistants** (office hours click here):

Adam Plumer

Andy Valenti

Ben Machlin

Maddy Duke

Matt Turner

Monsurat Olaosebikan

Pulkit Jain

Sam Burck

Sammy Saltzman

Zach Kirsch