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 11 
Oct. 13Class 12 
8 
October Break 
Oct. 18No class🍁 
Oct. 20No class🍂 
9 
Contextfree and noncontextfree languages

Oct. 25Class 13 
Oct. 27Class 14 
10 
Exam 2 
Nov. 1Review 
Nov. 3ExamExam 2 
11 
Turing machines

Nov. 8Class 15 
Nov. 10Class 16 
12 
Decidable languages

Nov. 15Class 17 
Nov. 17Class 18 
13 
The limits of computation

Nov. 22Class 19 
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