Text: The following required textbook will be available at the Jeffrey Amherst College Bookstore in downtown Amherst.
- [P] Christos Papadimitriou, Computational Complexity, 1994, Addison-Wesley.
- See the following website for the text's errata.
Meeting times: M,W 10:35 -- 11:50, CMPS 140. First meeting Mon., Jan. 28, 2008.
Optional Discussion Section: New this year, instead of his regular office hours, Philipp will lead a weekly discussion section on Mondays from 12:30 to 1:30, room TBA. These will be used to give pointers on how to solve 601-type-problems and to answer any questions about the assigned problems and the course material. The first discussion section will be Monday, January 28. The first few weeks, Philipp will use part of this time to help you with your review of regular sets and context-free languages.
Prerequisites: Mathematical maturity at the level of Comp Sci 250 is a minimal requirement. One nice book that helps with mathematical background is, How to Prove It by Daniel Velleman.
Most students will have had an undergraduate course in Automata and Formal Languages such as Comp Sci 401. For those who don't, we will have a very fast in-class review of Regular and Context-Free Languages. For students who don't know this material, it would be helpful to read one of the following in advance:
- John E. Hopcroft and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1979: Chapters 1--6.
- Harry Lewis and Christos Papadimitriou, Elements of the Theory of Computation, Prentice-Hall, 1981: Chapters 1--3.
- Michael Sipser, Introduction to the Theory of Computation, 1997: Chapters 1 -- 2.
Here is a diagram of the world of computability and complexity:
