Complexity and Computability

Lectures: Tuesday-Thursday 14:20 – 15:40  (Caldwell Lab 220)

Midterm: Thursday October 3rd
— Midterm – Solutions
— Median: 74 — Average: 65.5 — Max possible: 100,
— Median with Bonus: 80 — Average with Bonus: 70.8 — Max possible with Bonus: 110

Final Exam: Friday, December 6th, 4:00pm to 6:00pm (Caldwell Lab 220)
The final exam will cover all of the material covered in class up to and not including the randomized complexity theory. While containing computability theory, the exam will more so emphasize  the complexity theory portion of the material. The following pdf contains some sample problems to solve as preparation for the final exam. Please note that the final exam is not bound to these sample problems, and the student is expected to be familiar with all the material covered in the lecture notes.
sample final questions (updated dec 5)

Instructor:  Pooya Hatami (Dreese Lab 489,
TA:  Minghao Tian (Dreese Lab 474,

Office Hours:
Pooya Hatami: Tuesdays 17:00-18:00 (Dreese 489) or by appointment
Minghao Tian: Wednesdays 16:00-17:00 (Dreese 474)

Lecture Notes

I will maintain the pdf file below, gradually adding new lectures:

Lectures 1-24 (last updated Nov 14)


Assignment #1, due September 10th at the start of class,
        Assignment#1 — Solutions
        Total points possible: 100/100, Median: 78/100
Assignment #2, due October 3rd at the start of class
        Assignment#2 – Solutions
        Note: HW2.7 is now a bonus problem worth 10 points
        Total points possible: 85/85, Median: 55.5/85=65/100
Assignment #3 due November 26th at the start of class

Course Summary (tentative):

  • This course intends to introduce the student to theory of computability, and computational complexity theory, with a slight more emphasis on the latter.
  • Computability Theory: Notions of algorithms, Turing Machines (deterministic, nondeterministic, …), Church-Turing Thesis,  Decidability, Turing-recognizability and Enumerability, Diagonilization, Reducibility
  • Complexity Theory: Complexity classes and measures, P, NP, coNP,  NP-completeness, Hierarchy Theorems, Space Complexity, Boolean circuits, randomized computation, RP, ZPP, BPP, RL, BPL

Related Reading: 

25% homeworks — 30% midterm — 45% last exam

Policy on Collaboration:
Studying in groups is encouraged, however we also encourage students to work on the current homework set on their own. If you do collaborate, state it clearly at the beginning of your solution (give name of collaborator). Acknowledged collaboration does not mean copying someone else’s solution: Discuss the solutions, understand the ideas and give your own rendering.