Computing Theory Course

Computing Theory

Time: 2:10--5:00 Wednesday and Thursday



If IP=PSPACE, then TCP=NP.
---Class of 2000, M.S. (overheard)

A professor always included this question on his final exams:
"What did you think of this course?"
He discontinued the practice after receiving this response:
"This was the most complete course I ever took.
Anything we didn't go over during class
was covered in the final exam."
---Adapted from Reader's Digest

Two hunters are being pursued by a bear;
one stops to change into his running shoes.
The other tells him he is crazy: there is no
way he can run faster than a bear.
``I don't have to run faster than a bear,''
replies the first. ``I only have to run faster than you.''
The Economist, 18 March 2002



To the students,

This course emphasizes computational complexity and its applications. We will go over, in my opinion, the most interesting and/or important results in the field. You are expected to read the textbook for any background knowledge not covered in the lectures if your undergraduate education has not prepared you for this course. The textbook will, in general, be followed.

The mathematical techniques used in this course are wide-ranging but accessible. Undergraduate discrete mathematics course should be more than adequate. Math majors should be prepared to find standard mathematics used in unexpected ways. Combinatorics, probability, graph theory, number theory, and, to a less extent, group theory are the principal analytical tools. We shall skip predicate logic (Frege 1879) and the associated profound results of completeness and incompleteness (Godel 1930, 1931).

I hope you will be rewarded with the insights, sense of beauty, and applications that some of the results convey. There is also the satisfaction that, unlike many other fields in computer science (including those taught by me), many of the topics will still be taught to students decades from now.

Homework should be turned in on time. No late homework will be accepted without legitimate reasons. You are expected to finish your own homework on your own. Do not copy or collaborate with fellow students. Never give your homework to other students or publish your homework because it may be copied and you in turn may be suspected of copying other's homework!


Notes [ 2001, 2002, 2003, 2004, 2005, 2006, 2008 ]

  1. 2008.02.21
  2. 2008.02.28
  3. 2008.03.06
  4. 2008.03.13
  5. 2008.03.20 & 1st homework due & solutions
  6. 2008.03.27
  7. 2008.04.03
  8. 2008.04.10 & 2nd homework due & solutions
  9. 2008.04.17 & mid-term exam & solutions
  10. 2008.04.24
  11. 2008.05.01 & 3rd homework due & solutions
  12. 2008.05.08
  13. 2008.05.15
  14. 2008.05.22 & 4th homework due & solutions
  15. 2008.05.29
  16. 2008.06.05
  17. 2008.06.12 & 5th homework due & solutions
  18. 2007.06.19 & final exam & solutions

Examinations and grading

  1. There was a mid-term exam on April 17, 2008 (closed book).
  2. There will be a final exam on June 19, 2008 (closed book).

The major results covered in the course, time permitting, are listed below for your reference.