Introduction to the Theory of Computation,
3rd edition, by Michael Sipser, Cengage Learning, 2013. This is for
the first half of the course, and should be available in the bookstore.
Introduction to Algorithms, 3rd edition, by T. Cormen, C.
Leiserson, R.
Rivest, and C. Stein, MIT Press, 2009. This and the extra notes
will be used in the second half of the course.
Extra notes (available from Course Materials in Blackboard):
Lecture notes and problems for discussions sections:
Slides for the formula in the Cook-Levin Theorem:Slides.
May be used at the oral exam.
Slides for the 2-approximation algorithm for TSP with the triangle
inequality:Slides.
Teaching assistant's, David Hammer's ("instruktors")
homepage.
Exam information for 2020:
Compared to 2018, for 2020, there
is less about finite automata, and there is the material in "Course Materials" in Blackboard about parameterized algorithms. More information will be available later.