Theory of Computation (CS3800 11F) homepage
You have reached the webpage for the Northeastern
University, College of Computer and Information Science,
Fall 2011 session of Theory of Computation, also
known as "CS3800 11F." 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
This course meets 9:15 am - 10:20 am MWR West Village G 106
The instructor is Emanuele Viola. Email:
(instructor's five-letter last name)@ccs.neu.edu.
Office hours are Wednesdays 2:00 pm - 4:00 pm, West Village H 246.
Grader: Seth Tringale. Email: firstname.lastname@example.org
Volunteer grader supervisor: Eric Miles. Email: email@example.com
This page, especially the problem sets below, will 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.
Final Exam: 8:00 am - 10:00 am R West Village G 104 Dec 15, 2011.
Midterm: Monday, October 24th, 7:00 - 9:00 PM (2 hours). In 150 Dodge.
No class on Midterm day (above).
Problem Set 1. Assigned on 9/21, due on 9/28.
1: Exercise 1.3.
2: Give the formal descriptions of the machines pictured in Exercise 1.21, (a) and (b).
3: Exercise 1.6, parts f, g, h, i.
4: Exercise 1.14.a (closure under complement).
5: Prove that regular languages are closed under intersection.
Problem Set 2. Assigned on 9/28, due on 10/5.
1: Exercise 1.7. Parts b, c.
2: Exercise 1.14b.
3: Problem 1.31.
Problem Set 3. Assigned on 10/5, due 10/12.
1: Exercise 1.16. Part a.
2: Exercise 1.19. Part a.
3: Exercise 1.21. Part b.
Problem Set 4. Assigned on 10/12, due 10/19.
Note: some parts are solved in Sipser. I encourage you to tackle them without reading the solution. No need to include them in your write-up.
1: Problem 1.46.
2: Exercise 2.6.
3: Exercise 2.9.
Problem Set 5. Assigned on 11/7, due 11/14.
1: Exercise 3.8.c.
2: Exercise 4.3.
3: Exercise 4.6.
Problem Set 6. Assigned on 11/14, due 11/21.
1: Problem 5.9.
2: Exercise 7.1.
Problem Set 7. Assigned on 11/28, due 12/5.
1: Problem 7.20. Note: a "simple path" is a path which does not repeat any node.
2: Problem 7.21.
Math primer. Reading: Sipser Chapter 0.
Think like the pros, sections 1,2, and 4.4.
Regular languages and finite automata. Reading: Sipser Chapter 1.
-equivalence of NFAs and DFAs
-equivalence of RE and FA
-the pumping lemma
Context-free languages and pushdown automata. Reading: Sipser Chapter 2.
-equivalence of CFLs and PDAs
-pumping lemma for CFLs
Turing Machines. Reading: Sipser Chapter 3.
-Turing Machine variants
Computability. Reading: Sipser Chapter 4 and 5, and Problem 5.28.
-cardinality of infinite sets
Time complexity. Reading: Sipser Chapter 7.
-P and NP
-the Cook-Levin Theorem
As important, perhaps, is the material from CS1800,
which itself is a prerequisite for CS2800.
- CS2510, Fundamentals of Computer Science 2
- CS2800, Logic and Computation
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:
Introduction to the Theory of Computation, Second
Edition, by Michael Sipser.
Problem sets are due at the beginning of class on the
announced due date. If you cannot come to class, slide your homework under my door
(West Village H 246) before the class starts.
Late problem sets are not accepted.
If you will have a valid reason for turning in an assignment late, please see me in advance.
When solving a problem you can use all the results seen in class.
You should not use other sources. I want you to spend
your time thinking about the problems, not searching for a solution
on the web.
Some of the exercises
will be routine, but others will be more challenging. I do not
expect you to solve all of the homework problems, but I hope that you
will benefit from working on the more difficult ones. A few hints
on the homework assignments:
- Start early: Difficult problems are not typically
solved in one sitting. Start early and let the ideas come to you
over the course of a few days.
- Be rigorous: CS3800 is a theory course, and as such,
a certain level of mathematical rigor will be expected in your
- Be concise: Express your solutions at the proper
level of detail. Give enough details to clearly present your
solution, but not so many that the main ideas are obscured.
- Work with others: Some of the problems will be
difficult, and it will often be helpful to discuss them with others.
Feel free to form study groups. However, the idea is for everyone
to understand the problems and experience working through the
solutions, so you may not simply "give" a solution to another
classmate. In particular, each student must write up his or her
own homework solutions and must not read or copy the solutions
of others. If you work with others on a problem, you must note
with whom you discussed the problem at the beginning of your solution
For each problem on each problem set you will receive a number
between 0 and 1. Your grade for the problem set is the sum of the
grades of the problems on that problem set, divided by the number of problems.
Your least-scoring problem-set grade will be "dropped." That is,
it will not count toward your final problem-set grade.
Your final problem-set grade is the sum of the grades of all the other
There will be a midterm and a final exam. The midterm exam will be held
during a regularly scheduled class period, and the final exam will be held
during finals week. Both exams are open book and open notes. You cannot use any electronic device.
Your final grade is calculated as follows:
- Problem sets: 50%
- Midterm: 25%
- Final: 25%