Greg N. Frederickson
Office: LWSN 2116E
Office hours: TTh 1:00-2:00pm (now finished for the semester)
email: gnf@cs.purdue.edu
Time and location: MWF 11:30am-12:20pm, in BRNG B260
Hao Yuan
Office: LWSN B132, cube 20
Office hours: TuTh 2:00-3:00pm
email: yuan3@cs.purdue.edu
- M. Sipser, Introduction to the Theory of Computation,
- second edition, Thomson Course Technology, 2005.
Why you should take this course (from the preface to Sipser's book)
CS 381 and CS 352, or the consent of the instructor.
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) 30% Midterm exam (evening) 35% Final Exam (in exam period) 35%