CS 48300 --- Theory of Computation --- Spring 2014


Greg N. Frederickson
Office: LWSN 2116E
Office hours: TTh 2:00-3:30pm
email: gnf at cs.purdue.edu
Time and location:  MWF 3:30-4:20pm, in LWSN B134


M. Sipser, Introduction to the Theory of Computation,
third edition, Cengage Learning, 2013.


Why you should take this course (from the preface to Sipser's book)


CS 38100 and CS 35200, or the consent of the instructor.
Note: Since CS 35200 has not been offered the last several semesters,
students will be allowed in without having taken that course.

Topics will include:

Pumping lemmas for regular and context-free languages
Equivalence of pushdown automata and context-free grammars
Turing machines and the Church-Turing thesis
Decidability and the Halting problem
Reducibility and undecidable problems
Time classes: P, NP, NP-complete
Space classes: Savitch's theorem, PSPACE-completeness, NL-completeness
Applications of complexity to parallel computation

Possible additional topics (as time allows):

Decidability of logical theories, Kolmogorov complexity
Approximation algorithms, Probabilistic algorithms

Course Work:

Approx. weight in grade
Written assignments (8-10) 20%
Midterm exam I (evening) 20%
Midterm exam II (evening) 25%
Final Exam (in exam period) 35%