Theoretical Computer Science 2022

Classes

Wednesdays 18:10–21:00, on zoom

Teacher: Bruno Bauwens

For practical information join the telegram group

Grading

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

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

Course Materials

The main reference for the first 4 lectures is Sipser's book "Introduction to the theory of computation", 3rd edition, chapters 1, 2–7. Also, Mertens and Moore, The Nature of Computation, 2011.

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	PSPACE, completeness of TQBF, generalized geography	[1]
30.03	Approximations. More complexity classes.	approximations
13.04	Parameterized complexity: the class FPT and kernelization
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.