| # | Date | lecture topic | reading | pset | |
|---|---|---|---|---|---|
| 1 | 08-27 | T | Introduction (pdf, ) | Sipser §0-1.2, §3 | |
| 2 | 08-29 | R | Time complexity, def of P (pdf, ) | Sipser §7.1-7.2 | pset1 (tex/pdf/soln) |
| 3 | 09-01 | T | Non-determinism (pdf) | Sipser §7.3 | |
| 4 | 09-03 | R | Non-determinism (pdf) | Sipser §7.4 | |
| 5 | 09-08 | T | Non-determinism (pdf) | Sipser §7.4 | |
| 6 | 09-10 | R | Space (pdf) | Sipser §8.0 | pset1 due (). pset2 (tex/pdf) |
| 7 | 09-15 | T | Space (pdf) | Sipser §8.1-8.3 | |
| 8 | 09-17 | R | Space (pdf, mp4) | Sipser §8.3-8.4 | |
| 9 | 09-22 | T | Space (pdf, mp4) | Sipser §8.5-8.6 | |
| 10 | 09-24 | R | Intractability (pdf, mp4) | Sipser §9.1 | pset2 due (soln). pset3 (tex/pdf) | out
| 11 | 09-29 | T | Intractability (pdf, mp4) | Sipser §9.2 | |
| 12 | 10-01 | R | Circuits (pdf, mp4) | Sipser §9.3, AB §6 | |
| 13 | 10-06 | T | Circuits (pdf) | AB §6 | |
| 14 | 10-08 | R | Alternation (pdf, mp4) | Sipser §10.3, AB §5.0-5.3 | pset3 due () |