Schedule for Spring 2024.
| No. |
Date |
Day |
Topic |
Homework |
Miscellany |
| 01 |
Jan 16 |
T |
UCT: Overview
pdf
|
|
Computation |
| 02 |
Jan 18 |
H |
Computability
pdf
|
hw 1
sol
|
|
| 03 |
Jan 23 |
T |
Fundamental Results
pdf
|
|
Ari. Hier. |
| 04 |
Jan 25 |
H |
Hardness and Completeness
pdf
|
hw 2
sol
|
|
| 05 |
Jan 30 |
T |
Time Complexity
pdf
|
|
|
| 06 |
Feb 1 |
H |
Polynomial Time
pdf
|
hw 3
sol
|
|
| 07 |
Feb 6 |
T |
Satisfiabilty
pdf
|
|
|
| 08 |
Feb 8 |
H |
Nondeterminism and NP
pdf
|
hw 4
sol
|
|
| 09 |
Feb 13 |
T |
Cook-Levin Theorem
pdf
|
|
|
| 10 |
Feb 15 |
H |
Karp's List
pdf
|
hw 5
sol
|
|
| 11 |
Feb 20 |
T |
Ladner's Theorem
pdf
|
|
|
| 12 |
Feb 22 |
H |
Space Complexity
pdf
|
|
|
| 13 |
Feb 27 |
T |
Midterm
|
|
midterm sample
|
| 14 |
Feb 29 |
H |
Small Space
pdf
|
|
|
| 15 |
Mar 12 |
T |
Polynomial Space
pdf
|
|
|
| 16 |
Mar 14 |
H |
Counting and Immerman-Szelepcsenyi
pdf
|
hw 6
sol
|
|
| 17 |
Mar 19 |
T |
Polynomial Hierarchy
pdf
|
|
|
| 18 |
Mar 21 |
H |
Kolmogorov Complexity
pdf
|
hw 7
sol
|
|
| 19 |
Mar 26 |
T |
Kolmogorov Complexity II
pdf
|
|
|
| 20 |
Mar 28 |
H |
Randomness
pdf
|
hw 9
sol
|
|
| 21 |
Apr 2 |
T |
Randomized Algorithms
pdf
|
|
|
| 22 |
Apr 4 |
H |
Probabilistic Classes
pdf
|
|
|
| 23 |
Apr 9 |
T |
Interactive Proofs
pdf
|
hw 10
sol
|
|
| 24 |
Apr 16 |
T |
Circuit Complexity
pdf
|
|
|
| 25 |
Apr 18 |
H |
Descriptive Complexity
pdf
|
|
|
| 26 |
Apr 23 |
T |
Reversible Computation
pdf
|
|
|
| 27 |
Apr 25 |
H |
MIP* = RE
pdf
|
|
|
| - |
Apr 29 |
M |
Final |
final 2023 |
|
There may be small, local changes to this schedule, but
overall things are stable.