The CS3800 10F Homepage

You have reached the homepage for the Northeastern University, College of Computer and Information Science, Fall 2010 session of Theory of Computation, also known as "CS3800 10F." CS3800 is an undergraduate course on the theory of computation. This course 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 document, and all documents on this website, may be modified from time to time; be sure to reload documents on occasion and check the "last modified" date against any printed version you may have.


Basic Information


Teaching Assistant



As important, perhaps, is the material from CS1800, Discrete Structures, which itself is a prerequisite for CS2800.


Errata for this text are available on-line. If you are concerned that something in the text might be a typo, please check the errata available here: Errata for Introduction to the Theory of Computation, Second Edition, by Michael Sisper.


Homework Policy

Homework Grading



Academic Honesty

Further reading

In case you are interested in learning more about theory of computation, we provide below a few pointers. You do not need any of the material below for this class. For this class you only need Sipser's book.