CS 3800: Theory of Computation Winter 2010

Administrivia

Instructor: William D Clinger
Course web page: http://www.ccs.neu.edu/course/cs3800wc/
Directory: /course/cs3800wc/

Textbook: Michael Sipser Introduction to the Theory of Computation, Second Edition. See also the online errata for the second edition.

Catalog description: CS 3800 Theory of Computation 4 SH
Introduces the theory behind computers and computing aimed at answering the question: "What are the capabilities and limitations of computers?" Covers automata theory, computability, and complexity. The automata theory portion includes finite automata, regular expressions, non-determinism, non-regular languages, context-free languages, pushdown automata, and non-context-free languages. The computability portion includes Turing machines, the Church-Turing Thesis, decidable languages, and the Halting Theorem. The complexity portion includes big-O and small-o notation, the classes P and NP, the P versus NP question, and NP-completeness.
Prerequisite: CS 2510 (CS U213)
Recommended: CS 1800 (discrete structures) and CS 2800 (logic and computation)

Homework will be assigned on an almost-weekly basis. All students will be required to present some of their solutions to homework problems to the rest of the class. Some of the homework problems will be difficult, while others will be easier. The instructor does not expect every student to solve every problem; the number of problems you are expected to solve will be indicated when the problems are assigned.

Here are a few hints on doing homework:

Start early. Difficult problems are seldom solved in one sitting. The sooner you start on a problem, the more time your brain will have to think about it.
Be rigorous. If your solution is not rigorous enough to convince the other students and the instructor of its correctness, then it is not a solution.
Be concise. Do not belabor the obvious, but do not skip any of the essential ideas.
Talk to others. Talking to other students may help you to understand a problem or to come up with an idea for its solution. On the other hand, you are not allowed to show your written solution to any other student(s), and you are not allowed to read a solution written by any other student(s).

All work submitted for credit must be your own. You may discuss any homework problem with your classmates and the instructors, but you must write up your own solutions. When you submit a written solution, your solution must begin with a list of all students with whom you discussed the problem, even if you don't think those discussions contributed to your solution of the problem. You must also acknowledge any written sources (apart from the textbook) that you consulted, including sources found on the World-Wide Web. You are not allowed to read solutions from previous years' assignments.

Failure to acknowledge oral discussions or written sources constitutes plagiarism, which is a form of academic dishonesty that is forbidden by Northeastern University's Academic Honesty and Integrity Policy and the university's Code of Student Conduct.

Homework and class presentations will account for approximately one third to one half of your final grade. The rest of your final grade will be determined by midterm and final exams. There are likely to be two midterm exams.

Outline

Mathematical proof
Regular languages and finite automata
- Equivalence of DFA, NFA, regular expressions
- Pumping lemma
- Closure properties
Context-free languages and pushdown automata
- Derivations and parse trees
- Ambiguity, precedence, associativity
- Equivalence of PDA, CFG
- Pumping lemma
- Closure properties
Recursively enumerable languages and Turing machines
- Turing Machines (TM)
- Church-Turing Thesis
- Equivalents of Turing machines
Computability
- Decidable and recognizable languages
- Diagonalization
- The Halting Problem
- Undecidable languages
- Reducibility
- Unrecognizable languages
Complexity classes
- P and NP
- Polynomial time reducibility
- NP-completeness

Last updated 20 February 2010.