Course syllabus

Models of Computation

Instructor: [Insert data]

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 [Insert data] [Insert data] [Insert data] in [Insert data].

The full plan:

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