Computing Theory Course

Computing Theory

Time: 9:10--12:20 Tuesday
Location: Room 111



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, before 9:10. Otherwise, it will be considered late. Homework can be written in Chinese or English. If you have to use emails to turn in the homework, please use the PDF format with your student ID number as the file name and send it using your NTU or NTUCSIE email account. Time stamp will be used to determine if the homework is late or not. Beware of the potential email reliability problem. 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, 2008a, 2008b, 2009, 2010, 2011, 2012, 2013 ]

  1. 2013.09.10
  2. 2013.09.17
  3. 2013.09.24
  4. 2013.10.01 & 1st homework due & solutions
  5. 2013.10.08
  6. 2013.10.15
  7. 2013.10.22 & 2nd homework due & solutions
  8. 2013.10.29
  9. 2013.11.05 & mid-term exam & solutions
  10. 2013.11.12
  11. 2013.11.19 & 3rd homework due & solutions
  12. 2013.11.26
  13. 2013.12.03
  14. 2013.12.10 & 4th homework due & solutions
  15. 2013.12.17 & mid-term exam & solutions
  16. 2013.12.24 & 5th homework due & solutions
  17. 2013.12.31
  18. 2014.01.07 & final exam & solutions

Examinations and grading

  1. There is a mid-term exam on November 5, 2013 (closed book).
  2. There is a mid-term exam on December 17, 2013 (closed book).
  3. There is a final exam on January 7, 2014 (closed book).

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