CS 3800: Theory of Computation
Fall 2015

Links and a Directory

Instructor: William D Clinger
Home page: http://www.ccs.neu.edu/course/cs3800f15wc/
Piazza signup: https://piazza.com/northeastern/fall2015/cs3800honors
Piazza: https://piazza.com/northeastern/fall2015/cs3800honors/home
Course Directory: /course/cs3800f15wc (on the CCIS shared file system)


Required Textbook: Michael Sipser Introduction to the Theory of Computation, Third Edition. Cengage Learning, 2013.

Catalog Description

Introduces the theory behind computers and computing aimed at answering the question: "What are the capabilities and limitations of computers?" Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, non-determinism, non-regular languages, context-free languages, pushdown automata, and non-context-free languages. The computability portion includes Turing machines, the Church-Turing Thesis, decidable languages, and the Halting Theorem. The complexity portion includes big-O and small-o notation, the classes P and NP, the P versus NP question, and NP-completeness.

Prerequisites: CS 2510
Recommended: CS 1800 (discrete structures) and CS 2800 (logic and computation)


Homework will be assigned on an almost-weekly basis. Honors students will be required to present some of their solutions to homework problems to the rest of the class.

Here are a few hints on doing homework:

Academic Integrity

All work submitted for credit must be your own. You may discuss any homework problem with your classmates and the instructors, but you must write up your own solutions. When you submit a written solution, your solution must begin with a list of all students with whom you discussed the problem, even if you don't think those discussions contributed to your solution of the problem. You must also acknowledge any written sources (apart from the textbook) that you consulted, including sources found on the World-Wide Web. You are not allowed to read solutions to previous years' assignments or to another section's assignments.

Failure to acknowledge oral discussions or written sources constitutes plagiarism, which is a form of academic dishonesty forbidden by Northeastern University's Academic Integrity Policy and the university's Code of Student Conduct.


Homework and class presentations will account for approximately 40% of your final grade. The rest of your final grade will be determined by the exams.


Every student will need a CCIS student account.

Every student will need to sign up for the Piazza course site.

Last updated 10 September 2015.

For debugging: Click here to validate.