CZECH TECHNICAL UNIVERSITY IN PRAGUE
STUDY PLANS
2020/2021

# Complexity Theory

Code Completion Credits Range Language
01TSLO ZK 3 3+0 Czech
Lecturer:
Jan Volec (guarantor)
Tutor:
Supervisor:
Department of Mathematics
Synopsis:

The course is devoted to incorporation of complexity questions during algorithm development, introduction to NP completeness and generally to complexity classes of deterministic or nondeterministic Turing machines bounded by time or space. Emphasis is placed on mutual relations among these classes. Aside from nondeterministic classes we examine probability classes. Class of interactive protocols is presented at the end of lecture course.

Requirements:
Syllabus of lectures:

1.Complexity dimensions - expected, randomized, amortized; basic data structures 2. Divide &amp; conquer - recurrence, Strassen algorithm, sorting (+lower bound), median algorithm, prune and search 3. Fibonacci heaps, Dijkstra algorithm, minimum spanning tree - Fredman+Tarjan algorithm, Kruskal algorithm and DFU. 4. NP-completeness and basic transforms (SAT, tiling, clique) 5. Further NP complete examples (Hamiltonian paths and cycles, knapsack) Fully polynomial approximation scheme for the knapsack problem 6. Turing machines, linear compression and speedup, tape reductions, universal machines 7. Constructability, inclusions among complexity classes, hierarchy theorems 8. Padding argument, Borodin?s theorem, Blum?s theorem 9. Generalised nondeterminism and probability classes 10. Polynomial hierarchy, complete problems. 11. Interactive protocols

Syllabus of tutorials:
Study Objective:

Learn to incorporate complexity questions during algorithms development, learn to think about lower bounds of problem?s complexities. Learn basic relations among complexity classes.

Study materials:

Key references:

[1] J. L. Balcázar, J. Díaz, J Gabarró: „Structural Complexity I“, Springer - Verlag Berlin Heidelberg New York London Paris Tokyo 1988

Recommended references:

[2] Hopcroft, Ullmann „Introduction to Automata Theory and Computing“, ISBN 0-201-02988-X

Note:
Time-table for winter semester 2020/2021:
Time-table is not available yet
Time-table for summer semester 2020/2021:
Time-table is not available yet
The course is a part of the following study plans:
Data valid to 2020-09-23
For updated information see http://bilakniha.cvut.cz/en/predmet12074805.html