Navigation

CMPT 308

Computability & Complexity   -   Summer 2019

Announcements

  • Aug 2: I'll have 2-hour office hours on Wed, Aug 7, 11:30-13:30.
  • Aug 2: The final exam on Aug 8 will be on all topics of the course, with equal emphasis. You'll have 3 hours for an exam that will be roughly two quizzes in size. To prepare, go over all lecture slides and notes, HWs, quizzes, and the textbook. The questions on the final exam will be similar to those on the quizzes we had.
  • July 30: Quiz 4 solutions are posted.

older announcements...

  • July 25: Quiz 4 will cover lectures 19-27 (inclusive).
  • July 21: The soutions to HW 4 are now posted.
  • July 14: Quiz 3 solutions are now posted.
  • July 4: No classes on Wed, July 10, and Fri, July 12, as I'm away at a conference.
  • July 1: Quiz 3 will cover the material from Lectures 12-18 (inclusive).
  • June 20: There will be no class on Wed, June 26 (as I'll be away).
  • June 16: Quiz 2 will cover the material from lectures 7-12, excluding the Recursion Theorem. That is, Quiz 2 will cover TMs, decidability, undecidability, non-semi-decidability, Rice's Theorem, and reductions.
  • June 16: The solutions to HW 2 are now posted.
  • May 24: Quiz 1 will cover the material from Lectures 1-6 (inclusive), that is, Regular Languages, their properties, as well as the Pumping Lemma. The problems on the quiz will be similar to those in HW 1.
  • May 16: HW 1 is now available.

Course description

This course focuses on the inherent ''complexity'' of solving problems using a computer. The goal is to understand why some seemingly simple problems cannot be solved on computers and others have no efficient (i.e., fast) solution. Formal notions of computers, computability and complexity will be given. At the successful completion of this course, students will understand why, for example, computer viruses are so pervasive and why no one will ever write a perfect virus checker. We will see how these concepts are related to logic, in particular, the famous Incompleteness Theorem of Gödel. Finally, we will see a few surprising results from modern complexity, in particular, the results making use of randomness in computation.

  • Topics
  • Texts
  • Lectures
  • Office hours
  • Marking scheme
  • Models of Computation: Finite automata and Turing machines
  • Decidable and undecidable problems
  • Recursion theorem
  • Kolmogorov complexity
  • Gödel's Incompleteness theorems
  • NP-completeness
  • Time & Space complexity
  • Randomized computation
  • Interactive proofs
  • Probabilistically Checkable Proofs and the PCP Theorem
  • Time & Space Hierarchy Theorems
  • Cryptography

Teaching staff

Instructor: Valentine Kabanets (kabanets@cs.sfu.ca), Office: TASC1 8011

TAs: Fatemeh Hasiri (fhasiri@sfu.ca) and Young Shin Oh (sophieo@sfu.ca)

If you have grading-related questions, please email the TAs and ask for an appointment. If you still have questions after meeting with the TA, then come and see me.

Important dates

The 50-minute quizzes will be given during our regular lecture times on the following dates.

Quiz 1 Quiz 2 Quiz 3 Quiz 4
June 3 June 24 July 8 July 29

 

Final exam:  Thu, Aug 8, 15:30-18:30, AQ 3159

Assignments

I'll post homework assignments & solutions.

Lecture notes

I'll post my lecture notes for each class, and a reading assignment.

Finite Automaton and Turing Machine simulators