481: Syllabus

1. Week 1 (9/1) - Chapters 2-8
2. Week 2 (9/8) - Chapters 7-9,11
3. Week 3 (9/15) - Chapters 12-16. Extra Tuesday session will cover Chapters 13 and 14.
4. Week 4 (9/22) - Mealy and Moore machines, Decision problems for finite automata (emptiness and infiniteness of L), inferring automata with the help of a teacher
5. Week 5 (9/29) - Inferring automata, Chapter 19.
6. Week 6 (10/6) - Chapter 20,21,22.
7. Week 7 (10/15) - Chapter 22,23.
8. Week 8 (10/24) - Chapter 23, rough sketch of Chapter E (optional), Beginnings of Chapter 24.
9. Week 9 (10/27) - Chapters 24,25(optional),26,27,28.
10. Week 10 (11/3) - Chapters 29,30.
11. Week 10 (11/10) - Chapters 31,32,33.
12. Week 11 (11/17) - Chapters 34,35.
13. Week 12 (11/24) - prelim 2, optional lecture on randomized computation
14. Week 13 (12/1) - Computational complexity: time and space complexity classes, time hierarchy theorem, relationships between time and space complexity classes. Savitch's theorem. A complexity theoretic definition of random strings: Kolmogorov-Chaitin-Solomonoff complexity.