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 branch has no specializations.

Theoretical Computer Science provides comprehensive education in theoretical aspects of computational models, algorithm and data structure design, and structural properties of Boolean functions. Students gain understanding of the state-of-the-art techniques in the design of efficient algorithms and data structures, and also learn the limits and possibilities for solving algorithmic problems. In addition to that students acquire mathematical tools necessary to analyze and model algorithmic processes. Students can utilize gained knowledge in practical setting or they can continue by a doctoral study in theoretical computer science or related areas.

The graduate thoroughly understands the limits and possibilities of computational systems, has a broad overview of algorithmic techniques, and is able to apply these techniques to new problems. He also has skills necessary to convey abstract ideas with precision and clarity. The graduate can apply his skills in the design and analysis of complex systems and in the development of innovative solutions and transformative technologies. The graduate is also well prepared for doctoral studies in theoretical computer science and related areas.

3.1 Obligatory courses

3.2 Elective courses

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

3.3 Other recommended courses

3.4 State Final Exam

In addition to the two examination areas that are obligatory for all study branches, the student will select three other examination areas. Two of them must be from the following list of examination areas; the last one can be either from the following list as well, or it can be any area from the study branch Discrete Models and Algorithms, any area from the specialization Intelligent agents or the specialization Machine learning of the study branch Artificial Intelligence, or any area from the specialization Computer graphics of the study branch Computer Graphics and Game Development. In total, each student will get five questions from the five examination areas.

Examination areas

1. Complexity and computability

2. Boolean functions

3. Algorithms

4. Advanced data structures

Knowledge requirements

1. Complexity and computability
Oracle computation and relativized complexity classes. Polynomial hierarchy. Non-uniform models of computation. Probabilistic complexity classes. Interactive protocols, PCP Theorem. One-way functions and pseudo-random generators. Communication complexity. Proof complexity. Relationships and separations among complexity classes. Recursion theorems and their application. Effectively inseparable sets. Relativized computability and the jump operation. Arithmetic hierarchy.

Recommended courses

2. Boolean functions
Resolution and its completeness. Classes of Boolean functions with special properties. Algorithms for SAT and MAXSAT. Representing Boolean functions using BDD's and OBDD's. SAT solvers and their use for the SMT Problem. Parameterized complexity. Hypercube graphs.

Recommended courses

3. Algorithms
Advanced graph algorithms, flows in graphs, algorithms for planar graphs. Linear and semidefinitive programming, polynomial algorithms, applications in graph and approximation algorithms. Combinatorial approximation algorithms and schemes. Probabilistic algorithms, approximate counting, hashing and its applications. Interactive protocols and verification, PCP Theorem and its applications. Parallel models of computation and complexity classes, techniques and examples of parallel algorithms. String algorithms, sequences, sub-sequences, regular expressions and search.

Recommended courses

4. Advanced data structures
Entropy and information. Error-correcting codes. Data compression. Data structures for string processing. Dynamic data structures for graphs. Dictionary data structures. Probabilistic search data structures. Advanced heaps. Data structures for storing integers. Persistent data structures. Self-adjusting data structures. Cache oblivious analysis and optimal algorithms. Data-streaming algorithms.

Recommended courses