Updated: 2015-01-14

**
A preliminary version of the course outline. Changes possible.
(2015)
**

The course is meant for *n*^{th} year undergraduate and graduate students
of XXXX.

**Prerequisites**

Lectures are given on **periods 3 and 4**, i.e., the spring semester.
Weekly schedule includes 4 h of lectures and 2 h exercises.

- Lectures Tuesdays and Thursdays, 14--16 (TB222 and TB219, resp)
- Exercises Wednesday 10--12 (TC133)

The course will consist of **exercise assignments and exam**.
Grading is based on the exam.

There will be lecture slides, which will partially be given on this web page. Exercise assignments will also be given here.

- The first set of slides (Download PDF) Covers: Regular languages and finite automata (UPDATED for 2015)
- The second set of slides (Download PDF) Covers: context free languages and pushdown automata (UPDATED)
- The third set of slides (Download PDF) Covers: Turing machines
- The 4th set of slides (Download PDF) Covers: Undecidability
- The 5th set of slides (Download PDF) Covers: Reducibility
- The 6th set of slides (Download PDF) Covers: Recursion theorem, logic, Kolmogorov Complexity
- The 7th set of slides (Download PDF) Covers: Time complexity
- The 8th set of slides (Download PDF) Covers: Space complexity
- The 9th set of slides (Download PDF) Covers: Intractability
- The 10th set of slides (Download PDF) Covers: approximation algorithms

- The first exercise (21.1.) (Download PDF) (OK for 2015)
- The 2nd exercise (28.1.) (Download PDF) (OK for 2015)
- The 3rd exercise (4.2.) (Download PDF)
- The 4th exercise (11.2.) (Download PDF)
- The 5th exercise (18.2.) (Download)
- The 6th exercise (25.2.) (Download PDF)
- The 7th exercise (4.3.) (Download PDF)
- The 8th exercise (18.3.) (Download PDF)
- The 9th exercise (25.3.) (Download PDF)
- The 10th exercise (1.4.) (Download
- The 11th exercise (15.4.) (Download PDF With answers: (Download PDF)
- The 12th exercise (22.4.) (Download pdf)
- The 13th exercise (29.4.) (Download pdf)
- The 14th exercise (6.5.) (Download
- The 15th exercise (13.5.) (Download pdf)

The course lectures and exercises will be based on the book:
*Introduction to the Theory of Computation*, by Michael Sipser
(3rd international edition, CENGAGE Learning 2013).
Those wishing to pass the course by self-study, should obtain the book
by some means.

Course **teacher in charge** is Henri Hansen.

- Regular languages and finite automata
- Finite automata
- Nondeterminism
- Regular expressions
- Nonregular languages (pumping lemma)

- Context-free languages and push down automata
- Context Free Grammar
- PushDown Automata
- Pumping lemma
- deterministic CFLs and parsing

- The Church-Turing thesis
- Turing Machine
- Variants of TM
- Algorithms

- Decidability
- Decidable languages
- Undeciability

- Reducibility
- Undecidable problems in language theory
- Undecidable problem
- Mapping reducibility

- Computability theory
- Recursion theorem
- Logical theories
- Turing Reducibility
- Definition of information

- Time complexity
- Measure of complexity
- Class P
- Class NP
- NP-completeness

- Space complexity
- Savitch's theorem
- PSPACE
- PSPACE-completeness
- L and NL
- NL-completeness

- Intractablitity
- Hierarchy theorems
- Relativization
- Circuit complexity

- Advanced Complexity theory
- Approximation algorithms
- Probabilistic algorithms
- Alternation
- Interactive proof systems
- Parallel computation
- Cryptography