CS500/CS491, Theory of Computation

Syllabus

Here is the syllabus.

My office hours

My office is in Farris Engineering Center, FEC155. My office hours are Mondays 3:00-3:50. 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 and other readings

Required: The Nature of Computation by Moore and Mertens.

Here are the lecture notes on automata and languages.

Recommended alternate books: Introduction to the Theory of Computation by Sipser, and Computational Complexity by Papadimitriou. I also really like Algorithms by Dasgupta, Papadimitriou, and Vazirani, and Algorithm Design by Kleinberg and Tardos.

Homework

Here is homework zero, and the solutions.