Bachelor
2023/2024
Theory of Computation
Type:
Compulsory course (Applied Mathematics and Information Science)
Area of studies:
Applied Mathematics and Information Science
Delivered by:
Big Data and Information Retrieval School
Where:
Faculty of Computer Science
When:
3 year, 1, 2 module
Mode of studies:
offline
Open to:
students of one campus
Language:
English
ECTS credits:
5
Contact hours:
56
Course Syllabus
Abstract
The aim of computational complexity is to classify computational problems by their difficulty. Here, difficulty, is measured by various resources needed to provide answers, such as computation time, space, randomness, circuits sizes. In particular, we train to distinguish polynomial time solvable problems and NP-hard problems. The latter are believed to require exponential time for worst case instances, and hence, in applications, one needs to restate the problem, use heuristics, or optimize exhaustive searches. The latter, is studied theoretically in the field of parameterized complexity
Learning Objectives
- Know the parameterized complexity classes FPT, W[i], XP. Apply kernelization technique to obtain FPT-algorithms
- Know famous streaming algorithms, such as SpaceSaving, CountMinSketch to find the most frequent element
- Oracle computation and understand the diagonalization barrier in solving the P vs NP problem
- Prove that PSPACE = NPSPACE and that the TQBF problem is PSPACE complete
- Know the proof of the Cook-Levin theorem: 3SAT is NP-complete
Expected Learning Outcomes
- Definitions of Turing machines. Classes TIME(f(n)) and SPACE(f(n)). Time and space hierarchy theorems
- Definitions of the classes L, NL, P, NP, PSPACE, EXP, NEXP, EXPSPACE, BPP, RP, #P, and inclusions between them. Know some famous problems in these classes
- In particular, distinguishing between problems in P, that are NP-complete, and that are PSPACE-complete
Course Contents
- This course: what and why?
- Turing machines
- Hierarchy theorems
- The class NP
- NP-completeness
- Circuits
- Complexity zoo
- PSPACE
- Probabilistic computation
- Streaming algorithms
- Parameterized complexity
- Approximation algorithms
Assessment Elements
- ColloquiumIn December. The student receives 2 questions from a list of questions, given 2 weeks in advance. Answers are prepared in writing and the teacher checks understanding of the answers by asking for details or to work out simple examples. Students may not consult anything
- HomeworkEvery seminar list contains 2 homework questions similar as the questions in the seminar. Every 14 days, 4 questions need to be submitted. Sometimes the HW contains bonus marks, they are added to the score of the exam.
- ExamDuring session in December. A written examination is held past Module 1. Students may use the major textbooks and the lecture notes given in the wiki. The exam happens in a computer room. There are 4 questions similar to the one of the seminars and the homework. The marks
