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
NP-completeness.
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: stringale@gmail.com
Volunteer grader supervisor: Eric Miles. Email: enmiles@ccs.neu.edu
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.
Contents
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.
-DFAs
-regular operations
-closure properties
-non-determinism
-equivalence of NFAs and DFAs
-regular expressions
-equivalence of RE and FA
-the pumping lemma
Context-free languages and pushdown automata. Reading: Sipser Chapter 2.
-context-free grammars
-ambiguity
-pushdown automata
-equivalence of CFLs and PDAs
-pumping lemma for CFLs
-closure properties
Turing Machines. Reading: Sipser Chapter 3.
-Turing Machine variants
-Church-Turing thesis
Computability. Reading: Sipser Chapter 4 and 5, and Problem 5.28.
-cardinality of infinite sets
-diagonalization
-undecidability
-Halting Problem
-reducibility
-Rice's theorem
Time complexity. Reading: Sipser Chapter 7.
-P and NP
-NP-Completeness
-the Cook-Levin Theorem
Prerequisites
- CS2510, Fundamentals of Computer Science 2
- CS2800, Logic and Computation
As important, perhaps, is the material from CS1800,
Discrete Structures,
which itself is a prerequisite for CS2800.
Text
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 Sipser.
Homework
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
solutions.
- 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
write-up.
Grading
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
problem sets.
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%