CS 584 - - - Fall 2002

Theory of Computation and Computational Complexity

NOTE: The qualifiers are not completely graded yet. I hope that results will be ready on Friday.

Professor:

Greg N. Frederickson
Office: CS 224
Office hours: MWF 9:00-10:00
email: gnf at cs.purdue.edu
course URL: http://www.cs.purdue.edu/homes/gnf/cs584.html
Time and location: MWF 12:30-1:20, CS G066

Texts:

M. Sipser,

Introduction to the Theory of Computation, Brooks/Cole (1997).

C. H. Papadimitriou,

Computational Complexity, Addison-Wesley (1994).

Prerequisites:

CS 381 and CS 352, or comparable courses (that contain algorithm design techniques, analysis of algorithms, finite automata, regular expressions, context-free grammars, and pushdown automata)

List of Topics:

Turing machines
Decidability, Halting problem
Reducibility, Undecidable problems
Decidability of logical theories, Kolmogorov complexity
Time classes: P, NP, NP-complete
Space classes: Savitch's theorem, PSPACE-completeness, NL-completeness
Hierarchy theorems, Relativization
Approximation algorithms, Probabilistic algorithms, Alternation
Interactive proof systems, Parallel Computation, Cryptography

Course Work:

	Approx. weight in grade
Written assignments (6-9)	20%
Midterm exam (8:20-9:40 pm - Oct. 10, BRNG 2290)	40%
Final Exam (7:00-9:00 pm - Dec. 10, room TBA)	40%
Qualifier supp. (11:00am-noon - Dec. 12, CS G66)

Assignments

Assignment 1: (ps file) or (pdf file) with grading groups: (ps file) or (pdf file)
Assignment 2: (ps file) or (pdf file) with grading groups: (ps file) or (pdf file)
Assignment 3: (ps file) or (pdf file)
Assignment 4: (ps file) or (pdf file)
Assignment 5: Problem 1 has been deleted. (ps file) or (pdf file)
Assignment 6: (ps file) or (pdf file)
Assignment 7: (ps file) or (pdf file)

Last updated November 20, 2002.