Models of Computation

Instructor: Rasmus Blanck

Literature:  Introduction to the Theory of Computation by Michael Sipser, 3rd edition, 2013.

Examination: Oral presentation of a topic from the book, a few small hand-in assignments, and a short course paper on a topic chosen in consultation with the instructor.

Schedule: Available on TimeEdit. First meeting/lecture on Monday 28 March 10:15-12:00 in J439.

The full plan:

28 March: Intro
30 March: Rasmus on deterministic and non-deterministic finite automata (Please read Sections 1.1-1.2 before this meeting)
4 April: Armand on generalised non-deterministic finite automata etc (Please read Section 1.3 before this meeting)
6 April: Antonina on the pumping lemma (Please read Section 1.4) 
11 April: Basil on context-free grammars + Rasmus on push-down automata (Sections 2.1-2.2)
13 April: Ida on the pumping lemma for CFL + some linguistic considerations (Section 2.3)
20 April: Rasmus on the equivalence of PDAs and CFGs
25 April: Martina on variants of Turing machines (Section 3.2) + Rasmus on recursive function theory (Slides)
27 April: Maria on Hilbert's 10th problem  (Section 3.3 + paper1 + paper2)
2 May: Rasmus on recursive function theory (Slides)
4 May: Rasmus on recursive function theory (Full set of slides)
9 May: Aleksandar introducing time complexity (Sections 7.1-7.3 + Slides)
11 May: Rasmus on NP completeness + the Cook-Levin theorem (Section 7.4, especially Thm 7.37)
16 May: Rasmus on Space complexity (Sections 8.1-8.3)
18 May: Vlad on cryptography (Section 10.6)
23 May: Yuan
30 May: Yoann