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


Announcements, including problem sets

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.


Course outline

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

Course information

Prerequisites

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:

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: