CMPT 308 - Computability and Complexity - Spring'05

Apr 5. HW 4 is graded. The next lecture (Thu, April 7) will be the last lecture of our course. I'll review the material that we covered, and talk about the final exam.
Apr 2. The solutions to HW 4 are now posted.
Mar 31. Midterm 2 is graded; the grades are available on the web (via gradebook). Note that the grades are out of 45 (ignoring the 10 bonus points), so some people may have gotten more than 100% on the midterm. I'll bring the midterms to class next Tuesday.
Past Announcements

Course information handout: in PostScript and in PDF

Course Text: "Introduction to the Theory of Computation" by Michael Sipser, PWS, 1996. You can find the Errata for the book here

Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: ASB 9921

TA: Habil Zare (hzare@sfu.ca)

Lectures: T 12:30-13:20 & R 12:30-14:20 in AQ 3159
Office Hours by Instructor: TR 15:00-16:00, in ASB 9921 (or by appointment).
Office Hours by TA: TBA

I will post a brief outline of what I have done in class.

Alan Turing's famous paper introducing the concept of a Turing machine. You may skip the technical parts. Overall, the paper is quite readable and very interesting.
Turing machine simulator. You can program Turing machines, and watch them run.
Want a Million? Just solve the "P versus NP" Problem.