## Announcements

- Lastest Notes are here.
- NP complete practice quiz with answer is here.
- Class notes so far are here.
- Figures used in hw8: figure 1 figure 2 figure 3
- Figures used in hw7: figure 1 figure 2 figure 3 figure 4 figure 5 figure 6 figure 7
- A proof that HALT is undecidable.
- An exmaple Turing Machine solving 0n1n is 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, undecidability, infeasibility, diagonalizations, nondeterminism, information theory, time vs space, complexity classes, regular languages, context free grammars.

**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:** Ben Hescott

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

**Office:** Room 241 Halligan Hall

**Office Hours:** Wednesday 2:30pm - 4:30pm, Thursday 11:00am-12:00noon

**Class Location:** Cabot Hall, ASEAN Auditorium

**Time:** 9:00-10:15am

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

**Finals Week Schedule**

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

Aaron Herman

Adam Plumer

Andre Newland

Brett Fouss

Chase Crumbaugh

David Stalfa

Edwin Jain

Erica Albert

Francesca Caiazzo

Hyun Jun Jin

Jason Fan

Jeanne-Marie Musca

Jenni Niels Matthews

Julia Knight

Justin Sullivan

Kathryn Tweel

Naomi Zarrilli

Nicolas Sempere

Norman Young

Ryan Kohl

Sosena Bekele

Yotam Bentov

Yucheng He

Zachary Flicker