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 gradeWritten assignments (8-10) 20% Midterm exam I (evening) 20% Midterm exam II (evening) 25% Final Exam (in exam period) 35%