Computer Models and Limitations (CSC 280) — Summer 2022

Tentative Schedule

This schedule is subject to change based on the class's pace. Any change will be announced in class and will be reflected here.
DateTopicRequired ReadingsHomework 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.
: From today onwards (until the end of the course), this is now your favorite model of computation ;)