Theory of Computation

In 2023 and 2025 (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. Slides from 2023 -- which "only" contain my improvements (one new section) can be found here: 2023 slides. The 2025 version is furthermore significantly improved. I changed the order of the content and could free one further week of content, into which I expanded examples from AI planning. Now, the last two weeks practice the material from the first ten with examples from classical and hierarchical planning.

Below, the 2025 course outline, roughly following the book Automata Theory, Languages, and Computation by Hopcroft, Motwani, Ullman (2006).

• 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))