3 Degree Plans – 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

Code Subject Credits Winter Summer
NTIN090 Introduction to Complexity and Computability   5 2/1 C+Ex
NTIN066 Data Structures I   5 2/1 C+Ex
NTIN022 Probabilistic Techniques   6 2/2 C+Ex
NTIN063 Complexity   5 2/1 C+Ex
NTIN100 Introduction to Information Transmission and Processing   5 2/1 C+Ex
NSZZ023 Diploma Thesis I   6 0/4 C 0/4 C
NSZZ024 Diploma Thesis II   9 0/6 C 0/6 C
NSZZ025 Diploma Thesis III   15 0/10 C 0/10 C

3.2 Elective courses

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

Code Subject Credits Winter Summer
NAIL021 Boolean Functions and Their Applications   3 2/0 Ex
NAIL031 Representations of Boolean Functions   3 2/0 Ex
NAIL094 Decision Procedures and Verification   6 2/2 C+Ex
NMAG563 Introduction to complexity of CSP   3 2/0 Ex
NDMI010 Graph Algorithms   3 2/0 Ex
NDMI013 Combinatorial and Computational Geometry II   6 2/2 C+Ex
NDMI018 Approximation and Online Algorithms   6 2/2 C+Ex
NDMI025 Randomized Algorithms   6 2/2 C+Ex
NDMI067 Flows, Paths and Cuts   3 2/0 Ex
NDMI074 Algorithms and Their Implementation   6 2/2 C+Ex
NDMI077 Algorithms for Specific Graph Classes   3 2/0 Ex
NDMI088 Graph Algorithms II   3 2/0 Ex
NMAG446 Logic and Complexity   3 2/0 Ex
NMAG536 Proof Complexity and the P vs. NP Problem   3 2/0 Ex
NMAI067 Logic in Computer Science   3 2/0 Ex
NOPT034 Mathematical Programming and Polyhedral Combinatorics   5 2/1 C+Ex
NSWI072 Data Compression Algorithms   3 2/0 Ex
NTIN017 Parallel Algorithms   3 2/0 Ex
NTIN018 Probabilistic Analysis of Algorithms   3 2/0 Ex
NTIN033 Experimental Analysis of Algorithms   6 2/2 C+Ex
NTIN064 Computability   3 2/0 Ex
NTIN067 Data Structures II   3 2/0 Ex
NTIN073 Recursion   3 2/0 Ex
NTIN081 Structural Complexity   3 2/0 Ex
NTIN082 Computational Complexity   3 2/0 Ex
NTIN084 Bioinformatics Algorithms   6 2/2 C+Ex
NTIN085 Selected Topics in Computational Complexity I   5 2/1 C+Ex
NTIN086 Selected Topics in Computational Complexity II   5 2/1 C+Ex
NTIN087 String Algorithms   3 2/0 Ex
NTIN088 Algorithmic Randomness   3 2/0 Ex
NTIN096 Pseudo-Boolean Optimization   3 2/0 Ex
NTIN097 Hypercube Problems   3 2/0 Ex
NTIN098 Advanced Data Structures   3 2/0 Ex
NTIN099 Algorithmic Aspects of Boolean Functions and Parameterized Complexity   3 2/0 Ex
NTIN104 Foundations of theoretical cryptography   5 2/1 C+Ex
NTIN103 Introduction to Parameterized Algorithms   6 2/2 C+Ex

3.3 Other recommended courses

Code Subject Credits Winter Summer
NOPT016 Integer Programming   6 2/2 C+Ex
NOPT042 Constraint Programming   6 2/2 C+Ex
NTIN023 Dynamic Graph Data Structures   3 2/0 Ex

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

Code Subject Credits Winter Summer
NTIN063 Complexity   5 2/1 C+Ex
NTIN081 Structural Complexity   3 2/0 Ex
NTIN082 Computational Complexity   3 2/0 Ex
NMAG536 Proof Complexity and the P vs. NP Problem   3 2/0 Ex
NTIN064 Computability   3 2/0 Ex
NTIN100 Introduction to Information Transmission and Processing   5 2/1 C+Ex

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

Code Subject Credits Winter Summer
NTIN099 Algorithmic Aspects of Boolean Functions and Parameterized Complexity   3 2/0 Ex
NAIL094 Decision Procedures and Verification   6 2/2 C+Ex
NTIN097 Hypercube Problems   3 2/0 Ex
NAIL021 Boolean Functions and Their Applications   3 2/0 Ex
NAIL031 Representations of Boolean Functions   3 2/0 Ex

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

Code Subject Credits Winter Summer
NDMI010 Graph Algorithms   3 2/0 Ex
NDMI018 Approximation and Online Algorithms   6 2/2 C+Ex
NDMI025 Randomized Algorithms   6 2/2 C+Ex
NTIN017 Parallel Algorithms   3 2/0 Ex
NTIN087 String Algorithms   3 2/0 Ex

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

Code Subject Credits Winter Summer
NTIN100 Introduction to Information Transmission and Processing   5 2/1 C+Ex
NTIN067 Data Structures II   3 2/0 Ex
NTIN087 String Algorithms   3 2/0 Ex
NDMI010 Graph Algorithms   3 2/0 Ex
NTIN098 Advanced Data Structures   3 2/0 Ex
NSWI072 Data Compression Algorithms   3 2/0 Ex