Tuesday  12:00–1:15 p.m. 
Thursday  12:00–1:15 p.m. 
Sanders Physics 105 
Tuesday  Thursday  

1 
Models of computation

Aug. 30Class 1 
Sep. 1Class 2 
2 
Finite automata

Sep. 6Class 3 
Sep. 8Class 4 
3 
Regular languages and automata

Sep. 13Class 5 
Sep. 15Class 6 
4 
Regular and nonregular languages

Sep. 20Class 7 
Sep. 22Class 8 
5 
Exam 1 
Sep. 27Review 
Sep. 29ExamExam 1 
6 
Contextfree grammars

Oct. 4Class 9 
Oct. 6Class 10 
7 
Pushdown automata

Oct. 11Class 11Pushdown automata 
Oct. 13Class 12The power of PDAs 
8 
October Break

Oct. 18No class🍁 
Oct. 20No class🍂 
9 
Contextfree and noncontextfree languages

Oct. 25Class 13The limits of contextfree languages 
Oct. 27Class 14Parsing with CFGs 
10 
Exam 2 
Nov. 1ReviewExam 2 review 
Nov. 3ExamExam 2 
11 
Turing machines

Nov. 8Class 15Turing machines 
Nov. 10Class 16Designing Turing machines 
12 
Decidable languages

Nov. 15Class 17Turing machines and computation 
Nov. 17Class 18At the foot of the mountains of undecidability 
13 
The limits of computation

Nov. 22Class 19The limits of computation 
Nov. 24No class🥧 
14 
Computability

Nov. 29Class 20Computability and reductions 
Dec. 1Class 21The big picture 
15 
Review 
Dec. 6ReviewExam 3 review 
Dec. 8No class📚 
16 
Final exams 
Dec. 13ExamExam 3 
Presentday computers are built of transistors and wires, but they could just as well be built, according to the same principles, from valves and water pipes, or from sticks and string. The principles are the essence of what makes a computer compute. One of the most remarkable things about computers is that their essential nature transcends technology.W. Daniel Hillis, The Pattern on the Stone, 1998