New Course Proposal


Graduate:  Level I ______  Undergraduate: ___X___ 
Level II ______ 
Unit: College of Computing Date: 1/27/03

1. Course Number 
Program Number: CS3xxx 
2. Hours: Lecture Lab Recitation Total Semester Credit
___3___  ___  ________  _____3___ 
4. Descriptive Title: Automata and Complexity Theory
5. Recommended Abbreviation for Transcript (24 characters including spaces): 

Automata and Complexity 
6. Catalog Description (25 words or less):
Computational machine models and their language classes. Undecidability. Resource-bounded computations. Central complexity-theoretic concepts such as complexity classes, reducibility, and completeness.
7. Basis: L/G ____X_____ P/F ____X______ Audit ____X______
8. Prerequisites: CS 1050, CS 1322, and MATH 3012*
Corequisites:
10. Expected Mode of Presentation: MODE % OF COURSE
Lecture ____100______
Laboratory (Supervised) _______________
Laboratory (Unsupervised) _______________
Discussion _______________
Seminar _______________
Independent Study _______________
Library Work _______________
Demonstration _______________
Other (Specify) _______________
11. Planned Frequency of Offering: TERM TO BE OFFERED EXPECTED ENROLLMENT
Fall  _______
Spring ___x___
Summer _______
________________
______30________
_________________
12. Are you requesting this course satisfy: Humanities ________ Social Science ________ (Must be 1000 or 2000 level) 
13. Probable instructor(s) (Please mark with an asterix any non tenure-track individuals):
Yan Ding, Richard Lipton, H. Venkateswaran
15. Required _____________ Elective _____x______ 
16. Please attach a topical outline of the course.


 
Course Description and Topical Outline
Course Outline and Syllabus
INTRODUCTORY CONCEPTS: Formal languages, operations on languages, and basic properties.
REGULAR LANGUAGES: Deterministic and nondeterministic finite automata and their equivalence. Closure properties. Pumping lemma. Myhill-Nerode theorem.
CONTEXT-FREE LANGUAGES: Context-free grammars. Ambiguity. Normal forms such as Chomsky Normal Form. Closure properties. Pumping lemms. Pushdown automata. Equivalence of pushdown automata and context-free grammars. Cocke-Kasami-Younger algorithm. Deterministic context-free languages.
DECIDABILITY: Turing machines. Recursively-enumerable and recursive languages. Equivalence of varieties of models such as multi-tape and non-deterministic Turing machines with the deterministic Turing machines. Diagonalization. Undecidability of the Halting problem.
REDUCIBILITY: Undecidable problems from Language theory. Post Correspondence Problem. Many-one reducibility.
COMPLEXITY THEORY: Time complexity. Complexity classes P and NP. Polynomial time reducibility. NP-Completeness. The Cook-Levin theorem. Examples of NP-Complete problems.
Space complexity. Savitch's theorem. PSPACE-Completeness. The classes L and NL. NL-Completeness. NL equals CONL.
Probabilistic complexity classes.
 
Suggested Texts M. Sipser. Introduction to the theory of Computation, PWS Publishing Company.