| . | Name | Email address | Office hours |
| Instructor | Dror Fried | dror.fried@rice.edu | WF 10AM-11AM DH 3054 |
| Teaching Assistant | Jeffrey Dudek | jeffreydudek@rice.edu | W 1PM-2PM DH 3062 |
| . | Date | Topics/Notes | Book Section |
| 1 | 8/21 | Introduction, Big-O Notation | 1.1 |
| 2 | 8/23 | Turing Machines (Turing machine simulator) |
1.2-1.4 |
| 3 | 8/25 | ||
| 4 | 9/6 | ||
| 5 | 9/8 | Time Complexity: DTIME, P, and EXP | 1.5 |
| 6 | 9/11 | NP | 2.1 |
| 7 | 9/13 | ||
| 8 | 9/15 | Karp Reductions (Clique => VC, VC => Set Cover) | 2.2 |
| 9 | 9/18 | Boolean Formulas | 2.3.1 |
| 10 | 9/20 | ||
| 11 | 9/22 | 3-colorability => SAT | |
| 12 | 9/25 | 3SAT => Clique, SAT => 3SAT | |
| 13 | 9/27 | SAT => 3-colorability | |
| 14 | 9/29 | The Cook-Levin Theorem | 2.3.2 |
| 15 | 10/2 | ||
| 16 | 10/4 | Self-Reducibility | 2.5 |
| 17 | 10/6 | Mid-Semester Overview | |
| 18 | 10/11 | Nondeterministic Turing Machines | 2.1.2 |
| 19 | 10/13 | Midterm Review | |
| 20 | 10/16 | Space Complexity: SPACE, NSPACE, DL, and NL Configuration Graphs |
4.1, 4.2 |
| 21 | 10/18 | ||
| 22 | 10/20 | ||
| 23 | 10/23 | ||
| 24 | 10/25 | PSPACE Completeness, TQBF, Savitch's Theorem | 4.3 |
| 25 | 10/27 | ||
| 26 | 10/30 | Logarithmic Reductions, NL-Completeness | 4.4 |
| 27 | 11/1 | ||
| 28 | 11/3 | ||
| 29 | 11/6 | NL = CoNL | 4.4.2 |
| 30 | 11/8 | ||
| 31 | 11/10 | ||
| 32 | 11/13 | Diagonalization, Hierarchy Theorems Poem on the undecidability of the halting problem |
3 |
| 33 | 11/15 | ||
| 34 | 11/17 | ||
| 35 | 11/20 | ||
| 36 | 11/22 | Polynomial Hierarchy | 5 |
| 37 | 11/27 | ||
| 38 | 11/29 | ||
| 39 | 12/1 |
| . | Posting Date | Due Date | Problem Set | Solutions |
| 1 | 9/13 | 9/22 | Exercise 1 | (on Canvas) |
| 2 | 9/25 | 10/6 | Exercise 2 | (on Canvas) |
| 3 | 10/19 | 10/30 | Exercise 3 | (on Canvas) |
| 4 | 10/31 | 11/10 | Exercise 4 | (on Canvas) |
| 5 | 11/17 | 12/1 | Exercise 5 |