Theory of Computation (CS3800 12S) homepage
You have reached the webpage for the Northeastern
University, College of Computer and Information Science,
Spring 2012 session of Theory of Computation, also
known as "CS3800 12S." 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
1:35 pm - 3:15 pm TF
West Village H 110
The instructor is Emanuele Viola. Email:
(instructor's five-letter last name)@ccs.neu.edu.
Office hours, West Village H 246.
Part-time Teaching Assistant: Eric Miles, West Village H 266. Office hours: held in the lounge outside room 208
Thursday 11 - 12:30. 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
2012-02-10 Friday QUIZ 1.
2012-03-02 Friday QUIZ 2.
2012-03-13 Tuesday Mid-course survey.
2012-03-30 Friday QUIZ 3.
2012-04-20 Friday Extra office hours 1:35 pm - 3:15 pm.
2012-04-23 Monday QUIZ 4, 8:00 am - 10:00 am, Shillman Hall 105
Quiz sample.
Note: You should pick up your graded homework and quizzes during the TA's office hours. This gives you an opportunity to discuss solutions and any corrections.
Note: The next exercises refer to the textbook Introduction to the Theory of Computation, Second Edition, by Michael Sipser.
Problem Set 1. Assigned on 1/20, due on 1/27.
1: Exercise 1.6 parts: b, c, d, and e.
2: Give the formal definition of the DFA pictured in Exercise 1.21, (b). Show that this DFA accepts the string aab using the formal definition of accepting seen in class. For your reference, this definition is on Slide 45 and also in the book on Page 40.
Problem Set 2. Assigned on 1/27, due on 2/3.
1: Exercise 1.16.
2: Exercises 1.8 part a, 1.9 part a, and 1.10 part a.
Problem Set 3. Assigned on 2/17, due on 2/24.
1: Exercise 1.21.
2: Exercises 1.29(b).
3: Use the pumping lemma for regular languages to show that the following language is not regular: L = {a^{i} b^{ j } | i > 3j }.
4: Exercise 2.4, part b, part c, and part e.
5: Exercise 2.9.
6: Consider the following CFG grammar: S -> aSaS | aSa | ε. Show that the grammar is ambiguous.
Problem Set 4. Assigned on 3/16, due on 3/23.
The next exercises refer to the file
Quiz sample.
22: (b) and (c).
27: (c) and (d).
34: (a) and (e).
36: (b).
Problem Set 5. Assigned on 4/6, due on 4/13.
The next exercises refer to the file
Quiz sample.
39: (c) and (d).
46: (d).
47: (e).
Note: Slides will be updates throughout the course. Make sure you have the last version.
Overview of class.
Slides .PDF,
.ODP.
Math primer. Reading: Sipser Chapter 0.
Think like the pros, sections 1,2, and 4.4.
Slides .PDF,
.ODP.
Regular languages and finite automata. Reading: Sipser Chapter 1.
Slides .PDF,
.ODP.
-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.
Slides .PDF,
.ODP.
-context-free grammars
-ambiguity
-pushdown automata
-equivalence of CFLs and PDAs
-pumping lemma for CFLs
-closure properties
Turing Machines and Computability. Reading: Sipser Chapter 3, 4, 5, and Problem 5.28.
Slides .PDF,
.ODP.
-Turing Machine variants
-Church-Turing thesis
-cardinality of infinite sets
-diagonalization
-undecidability
-Halting Problem
-reducibility
-Rice's theorem
Complexity. Reading: Sipser Chapter 7.
Slides .PDF,
.ODP.
-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 should be placed in the "CS 3800" box in front of room West Village H 266 by the start of class on the due date.
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
Your final grade is calculated as follows:
- Quizzes: 80%
- Homework: 20%
There will be about 4 quizzes. The last quiz will be held during exam week. The other quizzes will be held during regular class times. Half of your least-scoring quiz will be "dropped." That is, it will not count towards your final grade. Quizzes are "closed-book." You cannot bring any book, notes, or electronic device.
Your least-scoring problem-set will also be "dropped." That is,
it will not count toward your final problem-set grade.