Theory of Computation (CS3800)

This is the webpage for the Northeastern University course Theory of Computation, also known as "CS3800", Fall 2013 session.
This is an undergraduate course on the theory of computation. It serves as an introduction to formal models of languages and computation. Topics covered include finite automata and regular languages, pushdown automata and context-free languages, Turing machines, computability, and NP-completeness.

This course meets 1:35 pm - 2:40 pm M,W,Th
Behrakis Health Sciences Cntr, room 310.

The instructor is Daniel Wichs. Email: (instructor's five-letter last name)@ccs.neu.edu.
Office hours: West Village H, Office 340. Monday 2:45 - 4 pm or by appointment.

Part-time Teaching Assistant: Chin Ho Lee. West Village H, Office 266. Office hours: Wednesday 4:45 - 5:45 pm.

Syllabus

Read over the syllabus for the class: syllabus.pdf
It has information on prerequisites, grading, textbook etc.

Discussion

There is a Piazza page for the course at https://piazza.com/northeastern/fall2013/cs3800/home. You can ask questions about the course material or the problem sets and they will be answered by the professor or the TAs.

Problem Sets

Problem Set 1 Due: Thursday, 9/19 at the beginning of class.

Course Slides

We will rely on course slides by Prof. Emanuele Viola as our main source of material. Here are the links to these slides. Each set of slides covers an entire large topic and spans multiple lectures.