Theoretical Computer Science 2022

Classes

Wednesdays 18:10–21:00, on zoom

Teacher: Bruno Bauwens

Grading

Exam: 40%
Homework: 20%
Project: 40%

There are 3 homeworks with deadlines: 16.02, 23.02, 02.03, before the lecture

Course Materials

The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", chapters 1, 2–7.

Video	Summary	Notes
19.01	Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties	lecture 1
25.01	Turing machines and register machines	lecture 2.A lecture 2.B (drafts)
09.02	undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems
16.02	time and space hierarchy theorems classes P and NP,
23.02	NP-completeness
02.03	PSPACE, PSPACE-hardness, EXP, BPP, Polynomial time hierarchy
09.03	Parameterized complexity (1): the class FPT and kernelization
16.03	Parameterized complexity (2): W-hierarchy, graph domination
23.03	Final exam

Office hours

Person	Monday	Tuesday	Wednesday	Thursday	Friday
Bruno Bauwens, S834, Zoom					14:00-20:00

Warn me in advance by email.