(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 Time Hierarchy |
S3 7.2-7.3,9.1 | |
| 6 | M,11/04 | NPC | S3 7.4,7.5 |
| W,11/06 | More NPC NP Intermediate and beyond |
S3 7.5 AB 2.6,3.4 draft book |
|
| 7 | M,11/11 | Veteran’s day no Class | |
| W,11/13 | Space complexity PSPACE,L,NL |
AB 4.1-4.3 S3 8.1,8.2 |
|
| 8 | M,11/18 | Relativization | S3 6.3,9.2 AB 3.5 |
| W,11/20 | EXAM (In-Class) 14:00 - 16:00 EB 92 |
||
| 9 | M,11/25 | Randomized computation | S3 10.2 AB 7.1-7.3 Probability review note |
| W,11/27 | BPP and friends | S3 10.2 AB 7.4,7.5 | |
| 10 | M,12/02 | Practice session led by Chuhan Lu |
|
| W,12/04 | Interactive proofs Guest lecture by Shravas Rao |
S3 10.4 |