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 | — |