All dates in the future should be considered tentative.
week | date (Monday) | topic | reading | assignment | |
---|---|---|---|---|---|
00 | 2023-08-28 | course introduction | |||
01 | 2023-09-04 | mathematical preliminaries | Mathematical Preliminaries | homework 1 | |
02 | 2023-09-11 | finite state automata | DFAs, Sipser §1.1 or Savage §4.1 | ||
03 | 2023-09-18 | nondeterimism | NFAs, Sipser §1.2 or Hopcroft §2.3 | homework 2 | |
04 | 2023-09-25 | regular expressions | REs, Sipser §1.3, Savage §4.3 or Hopcroft §3.1, 3.4 | ||
05 | 2023-10-02 | non-regular languages | NonRegular, Sipser §1.4 or Hopcroft §4.1 | homework 3 | |
06 | 2023-10-09 | Fall Break, Midterm 1 | |||
07 | 2023-10-16 | context-free languages | ContextFree, Sipser §2.1-2.2 or Hopcroft §5.1-5.2, 6.1-6.2 | ||
08 | 2023-10-23 | Turing machines | Turing Machines, Sipser §3.1-3.2, or Hopcroft §8.2-8.4 | homework 4 | |
09 | 2023-10-30 | Turing computability | Turing Computability, Sipser §4.1-4.2 or Hopcroft §9.1-9.2 | ||
10 | 2023-11-06 | λ-calculus | Lambda Calculus, Selinger §2 | ||
11 | 2023-11-13 | the Church-Turing Thesis | Church-Turing Thesis, SEP | homework 5 | |
12 | 2023-11-20 | Midterm 2, Thanksgiving Break | |||
13 | 2023-11-27 | the Curry-Howard Isomorphism | Curry-Howard Isomorphism, Selinger §6-7 | ||
14 | 2023-12-04 | other models of computation (student presentations) |