| Tuesday | 1:30–2:45 p.m. |
| Thursday | 1:30–2:45 p.m. |
Sanders Physics 105
| Part 1: Regular languages | Tuesday | Thursday |
|---|---|---|
Models of computation
|
Jan. 22 |
|
Finite automata
|
Jan. 27 |
Jan. 29 |
Nondeterminism
|
Feb. 3 |
Feb. 5 |
Models of the regular languages
|
Feb. 10 |
Feb. 12 |
Regular and nonregular languages
|
Feb. 17 |
Feb. 19 |
End of Part 1 |
Feb. 24Review |
Feb. 26Exam 1 |
| Part 2: Context-free languages | ||
Context-free grammars
|
Mar. 3 |
Mar. 5 |
Spring break |
Mar. 10🐥 |
Mar. 12🐝 |
Spring break |
Mar. 17🌧 |
Mar. 19🌱 |
Pushdown automata
|
Mar. 24 |
Mar. 26 |
Context-free and non-context-free languages
|
Mar. 31 |
Apr. 2 |
End of Part 2 |
Apr. 7Review |
Apr. 9Exam 2 |
| Part 3: Beyond context-free | ||
Turing machines
|
Apr. 14 |
Apr. 16 |
Decidable languages
|
Apr. 21 |
Apr. 23 |
The limits of computation
|
Apr. 28 |
Apr. 30 |
End of Part 3 |
May 5The big picture |
|
Study week
Optional Extra-credit Quiz 1
Wednesday, 6 May, 9:30–10:15 a.m., SP 105
Optional Extra-credit Quiz 2
Thursday, 7 May, 9:30–10:15 a.m., SP 105
Optional Review for Exam 3
Friday, 8 May, 9:30–10:45 a.m., SP 105
Exam week
Exam 3
Wednesday, 13 May, 9:00–11:00 a.m., NE 105
Present-day 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
