Theoretical Computer Science

Coordinated by: Department of Theoretical Computer Science and Mathematical Logic; Computer Science Institute of Charles University
Study branch coordinator: Doc. Mgr. Michal Koucký, Ph.D.

This study program has no specializations.

The program provides broad education in various aspects of theoretical foundations of computer science. Students are expected to have strong mathematical background which is further developed during the study with focus on exact thinking. Students gain overview and understanding in many areas of contemporary theoretical computer science - from cryptography and limits of computational systems to state-of-the-art techniques in the design of efficient algorithms and data structures. They will learn about frontiers of current knowledge in areas of their interest. Study may include working in international environment under guidance of recognized experts while writing a master thesis. Graduates are sought after by companies developing future technologies based on current research. At the same time, the study program excellently prepares for doctoral study at any university worldwide.

2.1 Obligatory Courses

2.2 Elective Courses

The student needs to obtain at least 47 credits for the courses from the following set:

Some of the courses are taught once every two years.

2.3 Other Recommended Courses

The list of recommended optional courses contains courses that expand and broaden the topics of the study program. Additionally, a student can chose other courses from the extensive collection of computer science courses at the Charles University.

2.4 State Final Exam

The student will select three examination areas from the following list, and he will get one question from each of the selected areas. Questions for each examination area address topics covered by the obligatory courses and recommended courses for the examination area. In total, each student will get three questions.

Examination areas

1. Complexity and Cryptography

2. Knowledge Representation in Boolean Domain

3. Algorithms

4. Data Structures

Knowledge requirements

1. Complexity and Cryptography
Oracle computation and relativized complexity classes. Polynomial hierarchy. Probabilistic complexity classes. Non-uniform models of computation. Interactive protocols. Communication complexity. Relationships and separations among complexity classes. Cryptography based on computational hardness. One-way functions and hard-core predicates. Pseudo-random generators. Data integrity (message authentication codes). Cryptographically secure hash functions. Commitment schemes. Zero-knowledge proof systems.

Recommended courses

2. Knowledge Representation in Boolean Domain
Resolution and its completeness. Dualization. Classes of Boolean functions with special properties. Exponential algorithms for k-SAT and general SAT. Parameterized algorithms for SAT. Algorithms for MAXSAT. Knowledge representation based on NNF. SAT solvers based on DPLL and CDCL and their use for SMT. Partial hypercubes and median graphs. Gray codes. Isoperimetric inequalities and linear distribution. Turán problems. Circuits, class P/poly and its properties. QBFs and their properties with respect to the polynomial hierarchy and PSPACE. Algorithms for QBF decision making. Error-correcting codes.

Recommended courses

3. Algorithms
Advanced graph algorithms, network flows. Linear and semidefinitive programming, polynomial algorithms, applications in graph and approximation algorithms. Combinatorial approximation algorithms and schemes. Pseudopolynomial algorithms, strong NP-completeness. Parameterized algorithms - FPT, parameterized lower bounds, parameterized approximation algorithms. Probabilistic algorithms, approximate counting, hashing and its applications. Interactive protocols and verification, PCP theorem and its applications.

Recommended courses

4. Data structures
Computational models (RAM and its variants). Entropy and information. Error-correcting codes. Data compression. Search trees. Hashing. Advanced heaps. Data structures for storing integers. Multidimensional data structures. Data structures for storing strings. Text algorithms. Data structures for storing graphs. Dynamization and persistence. Handling the memory hierarchy. Data-streaming problems.

Recommended courses