CS 584 - - - Spring 2009

Theory of Computation and Computational Complexity

Professor:

Greg N. Frederickson
Office: LWSN 2116E
Office hours: Monday 2:00-3:00pm and Wednesday 2:00-3:00pm
email: gnf at cs.purdue.edu
Temporary course URL: http://www.cs.purdue.edu/homes/gnf/cs584_09.html
Permanent course URL is on Blackboard
Time and location of class: Tuesday, Thursday 10:30-11:45am, in Lawson B134

Texts:

Ingo Wegener,

Complexity Theory, Springer (2005).

C. H. Papadimitriou,

Computational Complexity, Addison-Wesley (1994).

Prerequisites:

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

Partial List of Topics:

Turing machines
Computability
Time Complexity
Reductions and Completeness
NP-completeness
Approximation Problems
Polynomial Hierarchy
Interactive Proofs
PCP Theorem
Space Complexity

Course Work:

	Approx. weight in grade
Written assignments (6-9)	30%
Midterm exam (evening - TBA)	35%
Final Exam (during exam period)	35%

Last updated January 21, 2009.