Greg N. Frederickson
Office: LWSN 2116E
Office hours: M 10:00-11:00, WF 1:30-2:30pm
email: gnf at cs.purdue.edu
official course URL: TBA
Time and location: MWF 11:30 in LWSN 1106. (That's in the new CS building!)
Tiancheng Li
Office: LWSN B132
Office hours: TuTh 2:00-3:00
email: li83 at cs.purdue.edu
- M. Sipser,
- Introduction to the Theory of Computation, second edition, Course Technology, 2005.
Why you should take this course (excerpted from the preface to Sipser's book)
CS 483 - recent history
CS 381 and CS 352, or the consent of the instructor.
Pumping lemmas
Equivalence of PDAs and CFGs
Turing machines and the Church-Turing thesis
Decidability, Halting problem
Reducibility, Undecidable problems
Decidability of logical theories, Kolmogorov complexity
Time classes: P, NP, NP-complete
Space classes: Savitch's theorem, PSPACE-completeness, NL-completeness
Approximation algorithms, Probabilistic algorithms
Applications of complexity to parallel computation and cryptography
Approx. weight in grade Written assignments (8-10) 30% Midterm exam (evening
- Oct. 18, 8:30-10:00pm, LWSN 1106)35% Final Exam
(Dec. 11, 8:00am-10:00am, LWSN 1106)35%
Assignment 6 in pdf and in ps, due Nov. 1.
Assignment 7 in pdf and in ps, due Nov. 8.
Assignment 8 in pdf and in ps, due Nov. 17.
Assignment 9 in pdf and in ps, due Dec. 1.