CS500/CS491, Theory of Computation
My office hours
My office is in Farris Engineering Center, FEC335. My office hours are
Tuesdays from 3:30 to 4:30 and Wednesdays from 2:00 to 3:00. You should also feel free to email me, which is often the quickest way to get help.
Mailing List
Please subscribe to the mailing list.
Books
Required: The Nature of Computation by Moore and Mertens, available in the bookstore. This is a draft of a new book, so I would be very grateful if you would tell me about any typos --- and, more importantly, about sections which are unclear or difficult to understand. I will gratefully acknowledge your comments in the Preface!
Recommended: Introduction to the Theory of Computation by Sipser. We will only use this in the first few weeks in our discussion of finite-state automata and context-free grammars, but it does also give an alternate perspective on the material later on in the course. You can often find a cheap used copy on the Web.
If you want to know more, I also recommend Papadimitriou's 1994 book Computational Complexity.
Homework
Midterm
Final