(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