| # | 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) |
| 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) | Sipser §8.3-8.4 | |
| 9 | 09-22 | T | Space (pdf) | Sipser §8.5-8.6 | |
| 10 | 09-24 | R | Intractability (pdf) | Sipser §9.1 |