Содержание

Classes

Thursdays 18:10–21:00, in room S834.

Homeworks need to be emailed to brbauwens -at- gmail.com before the start of the lecture next lecture. Start the subject line with: tcs

For practical information click the this link to join the telegram group.

Video	Summary	Notes	Homework
01.02	Regular languages 1: deterministic automata, pumping lemma, closure properties (old recording)	lecture 1 & 2	hw1
08.02	Regular languages 2: nondeterministic automata and regular expressions. Definition of Turing machines.	Turing machines	hw2
15.02	Undecidable problems and computability theory	Turing completeness	hw3
07.03	The classes P, EXP, PSPACE, EXPSPACE, NP, reductions and completeness.	Sipser chapt 7, class_NP.pdf	hw4
14.03	Circuits and completeness of 3SAT. More reductions.	circuits.pdf	hw5
21.03	Parameterized complexity, the class FPT, kernelization, colorcoding. Colorcoding and background: in this lecture	presentation	hw6
25.03?	Treewidth. (this course)	Slides	hw7 ex 1,2,4

Main reference

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

Basic math

Golovnev, Kulikov, Podolskii, Shen, Discrete mathematics for computer science, 2020.

Computational complexity

Mertens and Moore, The Nature of Computation, 2011. (Pleasant reading with a lot of interesting background, but perhaps too much.)

Arora and Barak, Computational Complexity, 2009. (Use this after you made many exercises in the above books.)

Mathematical writing

Knuth, Technical writing, transcripts of lectures, 1987.

Gillman, Writing Mathematics Well, 1987.

Parameterized complexity

M. Cygan, F. Fomin and 6 others, Parameterized algorithms, 2016

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

Warn me in advance by email.