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 Thursdays 3:30-4:30. You should also feel free to email me, which is often the quickest way to get help.

Our TA is Yaojia Zhu; his email is yaojia.zhu@liamg(backwards).com. His office hours are Mondays and Fridays, 1:30-3:00, in FEC301A.

Mailing List

Please subscribe to the mailing list.

Books

Required: The Nature of Computation by Moore and Mertens, available in the UNM Copy Center in Dane Smith Hall for $19.75. 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!

Here is the mathematical appendix, which has some material on asymptotic notation and the basics of probability (as well as a lot of more advanced stuff that we won't need this semester).

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

Here is homework zero, and the solutions.

Here is homework one, due Friday, Feb. 5th, and the solutions.

Midterm

Final