CS500, 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
We will be using two texts: The Nature of Computation by Mertens and Moore, and Introduction to the Theory of Computation by Sipser. The Nature of Computation will be provided free of charge:
you can download the Prologue, and
Chapter 2.
Also highly recommended is Papadimitriou's 1994 book Computational Complexity.
Homework
Here is homework #1, due on Thursday, January 31st, and the solutions.
Here is homework #2, due on Tuesday, February 19th, and the solutions.
Here is homework #3, due on Tuesday, April 15th,
and the solutions.
Here is homework #4, due on Tuesday, May 6th,
and the solutions.
Midterm
Final