CS 3800: Theory of Computation

WVH 108

MWR - 1:35 PM ~ 2:40 PM

Sep 05, 2012 - Dec 05, 2012

■ 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.

We will be following closely the slides available on this page (see resources tab), so you do not need to buy any book for this class. However, we list next a few books that cover overlapping material:

■ Introduction to the Theory of Computation, 3rd Edition, Sipser.
■ Introduction to Automata Theory, Languages, and Computation, 3rd Edition, Hopcroft, Motwani, Ullman.

For links to errata, go to the tab Resources then section General Resources.

Slides corresponding to each part of the course can be found in the Resources tab. Some bigger files are also available in smaller chunks.

Note 1: Slides will be updates throughout the course. Make sure you have the last version.

Note 2: Direct links to course materials are available on the instructor's web page at http://www.ccs.neu.edu/home/viola/

+ Overview of class — Readings: Slide #01

+ Math primer — Readings: Think like pros, Slide #02

+ Regular languages and finite automata — Readings: Slides #03-10
--- 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 — Readings: Slide #11
--- context-free grammars
--- ambiguity
--- pushdown automata
--- equivalence of CFLs and PDAs
--- pumping lemma for CFLs
--- closure properties

+ Turing Machines and Computability — Readings: Slides #12-14
--- Turing Machine variants
--- Church-Turing thesis
--- cardinality of infinite sets
--- diagonalization
--- undecidability
--- Halting Problem
--- reducibility
--- Rice's theorem

+ Complexity — Readings: Slides #15-18
--- P and NP
--- NP-Completeness
--- the Cook-Levin Theorem

2012-09-05 Wednesday -- First class
2012-09-06 Thursday
2012-09-10 Monday
2012-09-12 Wednesday
2012-09-13 Thursday
2012-09-17 Monday -- PS 1 OUT
2012-09-19 Wednesday
2012-09-20 Thursday
2012-09-24 Monday -- PS 1 DUE
2012-09-26 Wednesday
2012-09-27 Thursday
2012-10-01 Monday -- QUIZ 1
2012-10-03 Wednesday
2012-10-04 Thursday -- PS 2 OUT
2012-10-08 Monday -- Columbus Day -- no classes
2012-10-10 Wednesday
2012-10-11 Thursday
2012-10-15 Monday -- PS 2 DUE
2012-10-17 Wednesday
2012-10-18 Thursday
2012-10-22 Monday -- QUIZ 2
2012-10-24 Wednesday
2012-10-25 Thursday
2012-10-29 Monday -- PS 3 OUT / MID-CLASS SURVEY
2012-10-31 Wednesday
2012-11-01 Thursday
2012-11-05 Monday -- PS 3 DUE
2012-11-07 Wednesday
2012-11-08 Thursday
2012-11-12 Monday -- Veterans Day -- no classes
2012-11-14 Wednesday
2012-11-15 Thursday
2012-11-19 Monday -- QUIZ 3
2012-11-21 Wednesday -- Thanksgiving -- no classes
2012-11-22 Thursday -- Thanksgiving -- no classes
2012-11-26 Monday -- PS 4 OUT
2012-11-28 Wednesday
2012-11-29 Thursday
2012-12-03 Monday -- PS 4 DUE
2012-12-05 Wednesday -- last class

Your final grade is calculated as follows:

● Quizzes: 80%
● Problem Sets: 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.

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.