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.
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
Decidability of logical theories, Kolmogorov complexity
Approximation algorithms, Probabilistic algorithms
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%