| L | M | D | W | Topic | Slides | HW |
| 1 | Aug | 30 | T | CDM: The Idea | pdf 6up | |
| 2 | Sep | 1 | H | Register Machines | pdf 6up | HW 1 sol |
| 3 | Sep | 6 | T | Computability and Decidability | pdf 6up | |
| 4 | Sep | 8 | H | More Models of Computation | pdf 6up | HW 2 sol |
| 5 | Sep | 13 | T | Iteration, Orbits, Fixed Points | pdf 6up | |
| 6 | Sep | 15 | H | More Iteration | pdf 6up | HW 3 sol |
| 7 | Sep | 20 | T | Yet More Iteration | pdf 6up | |
| 8 | Sep | 22 | H | Finite State Machines | pdf 6up | HW 4 sol |
| 9 | Sep | 27 | T | Constructing Machines | pdf 6up | |
| 10 | Sep | 29 | H | Constructing Machines II | pdf 6up | HW 5 sol |
| 11 | Oct | 4 | T | Minimization | pdf 6up | |
| 12 | Oct | 6 | H | Minimization II | pdf 6up | HW 6 sol |
| 13 | Oct | 11 | T | Kleene's Theorem | pdf 6up | |
| 13 | Oct | 6 | H | Kleene's Theorem II | ||
| 15 | Oct | 18 | T | Midterm (take home) | 10 09 08 | sol |
| 16 | Oct | 20 | H | No Class | ||
| 17 | Oct | 25 | T | Automata and Logic | pdf 6up | |
| 20 | Oct | 27 | H | Infinite Words | pdf 6up | HW 7 sol |
| 19 | Nov | 1 | T | Determinization | pdf 6up | |
| 20 | Nov | 3 | H | Semigroups and Groups | pdf 6up | HW 8 sol |
| 21 | Nov | 8 | T | Actions and Burnside | pdf 6up | projects |
| 22 | Nov | 10 | H | Polya Counting | pdf 6up | HW 9 sol |
| 23 | Nov | 15 | T | Equational Reasoning | pdf 6up | |
| 24 | Nov | 17 | H | Finite Fields | pdf 6up | |
| 25 | Nov | 22 | T | Finite Fields II | ||
| 26 | Nov | 29 | T | FF Applications | pdf 6up | |
| 27 | Dec | 1 | H | Feedback Shift Registers | pdf 6up | HW 10 sol |
| 28 | Dec | 6 | T | Cellular Automata | pdf 6up | |
| 29 | Dec | 8 | H | CA and Universality | pdf 6up | |
| 30 | Dec | - | - | Final |
The syllabus is globally stable but may change locally.
Staff
- Instructor: Klaus Sutner
sutner AT cs DOT cmu DOT edu
Office hours: Thursday, 1:30-3:00.
- TA: Matthew Mirman
mmirman AT andrew DOT cmu DOT edu