Theory of Computation

In 2023, 2025, and 2026 (semester 1) I was the convenor of the course Theory of Computation. I improved all slides, some of them significantly (I believe) by adding additional explanations and even slides altogether.

Below, the 2025 course outline, roughly following the book Automata Theory, Languages, and Computation by Hopcroft, Motwani, Ullman (2006). (Note that a 2026 update will be made available soon.)

• week 1:

  • chapter 2: Finite Automata (Slides (handout) (single))
  • chapter 3: Regular Expressions and Languages (Slides (handout) (single))

• week 2:

  • chapter 4: Properties of Regular Expressions (Slides (handout) (single))
  • chapter 5: Regular Expressions and Languages (Slides (handout) (single))

• week 3:

  • chapter 6: Pushdown Automata (Slides (handout) (single))

• week 4:

  • chapter 7: Properties and Normal Forms of Context-free Languages (Slides (handout) (single))
  • The Chomsky Hierarchy (Slides (handout) (single))

• week 5:

  • chapter 8: Introduction to Turing Machines (Slides (handout) (single))

• week 6:

  • chapter 9: Decidability and Undecidability (Slides (handout) (single))

• week 7:

  • Reductions and Complexities (Slides (handout) (single))

• week 8:

  • chapters 10 and 11: Classes P, NP, and co-NP (Slides (handout) (single))

• week 9:

  • chapter 11: PSPACE to (N)EXPTIME (Slides (handout) (single))

• week 10:

  • Alternating Time (Slides (handout) (single))
  • On Polytime Reductions, Karp vs. Cook Reductions, Optimizations (Slides (handout) (single))

• week 11:

  • Examples from Classical Planning (Slides (handout) (single))

• week 12:

  • Examples from Hierarchical Planning (Slides (handout) (single))