Theory of computation

CS-251

This file is part of the content downloaded from Theory of computation.
Course summary

Part I: Finite Automata

Lecture 1: Introduction and Finite Automata

Chapters 0 and 1.1 from Sipser's book. A few recommended exercises from Sipser's book: 1.4-1.6

Lecture 2: Non-Determinism and Closure Properties

Chapter 1.2 in Sipser. A few recommended exercises: 1.7-1.10, 1.14

Lecture (and exercises) cancelled

Continuing next week with Lecture 3

Lecture 3: Non-Regular Languages

Chapter 1.4 in Sipser. A few recommended exercises: 1.29-30

  • Guest lecturer: Nathan Harms

First homework released Tuesday 11 March, deadline Thursday 20 March.

Part II: Computability

Lecture 4: Turing Machines and its variants, Decidability

Chapters 3.1, 3.2, 4.1 in Sipser. A few recommended exercises: 3.5,4.3

Lecture 5: Decidability and Undecidability

Chapters 4.1 and 4.2. A few recommended exercises: 4.3, 4.5

Lecture 6: Undecidability and Reducibility

Chapters 4.2, 5.1 and 5.3 in Sipser. A few recommended exercises: (3rd ed.) 5.4, 5.6, 5.9, 5.13. (3rd ed.: International version) 5.4, 5.6, 5.25, 5.29

Second homework published 8 April with deadline 17 April.

Recap of Part II

Recap of mapping reductions and we solve midterm exam II from 2019.
For the exercise sessions, we have a selection of problems from the final exam from 2020.

Lecture cancelled

Continuing after Easter with Part III

Easter break

However, to get hyped up for Part III, you can get a sneak peek from the following videos (by EPFL MSc student Victor Braun)

Part III: Complexity

Lecture 7: Time complexity, Class P

Chapters 7.1 and 7.2 in Sipser. Start on class NP (Chapter 7.3).

Lecture 8: NP, NP-completeness

Chapters 7.3 and 7.4.


Lecture 9: NP-completeness

Chapters 7.4 and 7.5. Additional recommended exercises: 7.32, 7.38

Third homework published 13 May with deadline 22 May.

Lecture 10: More NP-completeness: 3-matching, subset sum.

Chapter 7.5.

Lecture 11: Circuit complexity and Cook–Levin

Chapter 9.3


Bonus material

Past exams together with solutions (to help you with exam prep)