(Fall 2024) CS 581 -- Theory of computation
Schedule
Schedule (subject to change)
| Week | Date | Topic | Reading & Note |
|---|---|---|---|
| 1 | M,09/30 | Intro | Widgerson Chapter 20 S3 Chapter 0 |
| W,10/02 | Math proofs | S3 0 | |
| 2 | M,10/07 | Finite automata | S3 1 |
| W,10/09 | Regular expressions NFA |
S3 1 | |
| 3 | M,10/14 | Pushdown automata | S3 2.2 |
| W,10/16 | Turing Machines | S3 3.1-3.2 | |
| 4 | M,10/21 | Decidability | S3 4,5.1,5.3 |
| W,10/23 | Reducibility | S3 5.1,5.3 | |
| 5 | M,10/28 | Time Complexity | S3 7.1 |
| W,10/30 | P,NP,NPC | S3 7.2-7.4 | |
| 6 | M,11/04 | More NPC NP-Intermediate |
S3 7.5 AB 3.4 draft book |
| W,11/06 | Relativization | S3 6.3,9.2 AB 3.5 |