Date | Topic | Required Readings | Homework notes |
05/16 |
Mathematical Rigor and Proving Things |
0.1–0.4 |
|
05/17 |
Regular Languages and Proving Things Nonregular |
1.1–1.4 |
|
05/18 |
Context-free Languages and Proving Things Non-CF |
2.1–2.3 |
|
05/19 |
Practice with the Pumping Lemmas, Applications, and Advanced Regular Languages* |
- |
HW 1 Out |
05/23 |
Immersing into Turing Machines† |
3.1–3.3 |
HW 1 Due Before Class |
05/24 |
Proving things Decidable |
4.1, 4.2 |
|
05/25 |
Pushing our Understanding of Decidability |
5.1, 5.3 |
HW 2 Out |
05/26 |
Practice with Decidability and Undecidability |
Make sure you are familiar with the template method |
|
05/31 |
A Modern Twist: Complexity Theory |
7.1–7.5 (you can skim pages 304 and onwards) |
HW 2 Due Day Before |
06/01 |
Refining our techniques: Undecidability in practice |
5.3 |
HW 3 Out |
06/02 |
Understanding P and NP in practice |
Make sure you read 7.1–7.5 |
|
06/06 |
Exploring Properties of SAT: Complexity of variants, Self-reducibility, etc. |
- |
HW 3 Due Before Class |
06/07 |
The Deterministic Time and Space Hierarchies |
9.1 |
HW 4 Out |
06/08 |
The Polynomial-Time Hierarchy*, Meta Results*, other models of computation* |
10.3, 9.2 |
|
06/09 |
Class Presentations |
Come with questions! |
|
*: If time permits.