Theoretical Computer Science 2022

Classes

Wednesdays 18:10–21:00, on zoom

Teacher: Bruno Bauwens

For practical information join the telegram group

Grading

Homework: 50%
Project: 50%

There are 2 homeworks with deadlines: 23.02, 09.03 before the lecture

References

Sipser, Introduction to the theory of computation", 3rd edition, chapters 1, 2–8. (Short and good for basic understanding.)

Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading, loads of interesting background, but rather large.)

Arora and Barak, Computational Complexity, 2009. (Use this if you have already made many exercises in the previous books.)

Fomin and 7 others. Parameterized algorithms, 2015. (This is an advanced book.)

Course Materials

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
09.02	undecidability of: Halting program, Wang tiling, Fractran Godel's incompleteness theorems	lecture 3.A 3.B
16.02	The classes P, EXP, PSPACE, EXPSPACE. Dynamic programming. Time and space hierarchy theorems.	seminar
23.02	Holliday
02.03	The class NP and NP-completeness	notes
02.03	Circuits, proof of the Levin-Cook theorem (see also Mertens&Moore chapter 5), more reductions	circuits
16.03	More NP-complete problems	reductions
23.03	Games, PSPACE, Savich theorem, completeness of TQBF	pspace
30.03	Parameterized complexity I: the class FPT and kernelization
13.04	Parameterized complexity II: the W-hierarchy
20.04	Projects

Office hours

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

Warn me in advance by email.