Classes
Wednesdays 18:10–21:00, on zoom
Teacher: Bruno Bauwens
Grading
Exam: 40%
Homework: 20%
Project: 40%
There are 3 homeworks with deadlines: 09.02, 16.02, 23.02, 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.
19.01 || Regular languages: (non)deterministic automata and their equivalence, pumping lemma, closure properties ||
lecture 1
25.01 || Turing machines, undecidability of: Halting theorem, Wang tiling, Fractran ||
02.02 || Godel's incompleteness theorems, classes P and NP ||
09.02 || NP-hardness, EXP, PSPACE, PSPACE-hardness, BPP, Polynomial time hierarchy||
16.02 || Parameterized complexity(1): the class FPT and kernelization ||
23.02 || Parameterized complexity(2): W-hierarchy ||
02.03 || Projects ||
09.03 || Porjects ||
16.03 || Final exam ||
Office hours
| Person |
Monday |
Tuesday |
Wednesday |
Thursday |
Friday
|
| Bruno Bauwens, S834, Zoom |
|
|
|
|
14:00-20:00
|