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
Code | Subject | Credits | Winter | Summer | |
NTIN090 | Introduction to Complexity and Computability | 4 | 2/1 C+Ex | — | |
NTIN066 | Data Structures 1 | 6 | — | 2/2 C+Ex | |
NTIN022 | Probabilistic Techniques | 5 | 2/2 C+Ex | — | |
NTIN063 | Complexity | 4 | — | 2/1 C+Ex | |
NTIN100 | Introduction to Information Transmission and Processing | 4 | — | 2/1 C+Ex | |
NSZZ023 | Diploma Thesis I | 6 | — | 0/4 C | |
NSZZ024 | Diploma Thesis II | 9 | 0/6 C | — | |
NSZZ025 | Diploma Thesis III | 15 | — | 0/10 C |
2.2 Elective Courses
The student needs to obtain at least 47 credits for the courses from the following set:
Code | Subject | Credits | Winter | Summer | |
NAIL021 | Boolean Functions and Their Applications | 3 | 2/0 Ex | — | |
NTIN096 | Pseudo-Boolean Optimization | 3 | — | 2/0 Ex | |
NAIL094 | Decision procedures and SAT/SMT solvers | 5 | — | 2/2 C+Ex | |
NDMI010 | Graph Algorithms | 3 | 2/0 Ex | — | |
NDMI018 | Approximation and Online Algorithms | 5 | — | 2/2 C+Ex | |
NDMI025 | Randomized Algorithms | 5 | — | 2/2 C+Ex | |
NSWI072 | Data Compression Algorithms | 3 | 2/0 Ex | — | |
NTIN067 | Data Structures 2 | 3 | — | 2/0 Ex | |
NDMI074 | Algorithms and Their Implementation | 5 | — | 2/2 C+Ex | |
NTIN081 | Computational complexity and interactive protocols | 3 | — | 2/0 Ex | |
NTIN082 | Nonuniform computational models | 3 | — | 2/0 Ex | |
NTIN087 | String Algorithms | 3 | 2/0 Ex | — | |
NTIN097 | Hypercube structures | 3 | 2/0 Ex | — | |
NTIN099 | Algorithms for knowledge representation | 3 | — | 2/0 Ex | |
NTIN103 | Introduction to Parameterized Algorithms | 5 | 2/2 C+Ex | — | |
NOPT034 | Mathematical Programming and Polyhedral Combinatorics | 4 | 2/1 C+Ex | — | |
NTIN104 | Foundations of theoretical cryptography | 4 | 2/1 C+Ex | — | |
NDMI067 | Flows, Paths and Cuts | 3 | 2/0 Ex | — | |
NDMI077 | Algorithms for Specific Graph Classes | 3 | — | 2/0 Ex | |
NDMI088 | Graph Algorithms 2 | 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 | — | |
NTIN017 | Parallel Algorithms | 3 | — | 2/0 Ex | |
NTIN023 | Dynamic Graph Data Structures | 3 | 2/0 Ex | — | |
NTIN064 | Computability | 3 | — | 2/0 Ex | |
NTIN073 | Recursion | 3 | 2/0 Ex | — | |
NTIN084 | Bioinformatics Algorithms | 5 | 2/2 C+Ex | — | |
NTIN085 | Selected Topics in Computational Complexity I | 4 | 2/1 C+Ex | — | |
NTIN086 | Selected Topics in Computational Complexity II | 4 | — | 2/1 C+Ex | |
NTIN101 | Selected Topics in Algorithms | 3 | 2/0 Ex | — | |
NTIN111 | Selected Topics in Algorithms II | 3 | — | 2/0 Ex | |
NTIN110 | Selected Topics in Data Structures | 3 | 2/0 Ex | — | |
NTIN088 | Algorithmic Randomness | 3 | — | 2/0 Ex | |
NTIN102 | Seminar on theory of computing | 3 | 0/2 C | 0/2 C | |
NDMI093 | Seminar on algorithms and data structures | 3 | — | 0/2 C |
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.
Code | Subject | Credits | Winter | Summer | |
NDMI007 | Combinatorial Algorithms | 5 | — | 2/2 C+Ex | |
NAIL116 | Social networks and their analysis | 5 | 2/2 C+Ex | — | |
NOPT042 | Constraint Programming | 5 | 2/2 C+Ex | — | |
NAIL076 | Logic Programming 1 | 3 | 2/0 Ex | — |
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
- 2. Knowledge Representation in Boolean Domain
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
Code | Subject | Credits | Winter | Summer | |
NTIN063 | Complexity | 4 | — | 2/1 C+Ex | |
NTIN081 | Computational complexity and interactive protocols | 3 | — | 2/0 Ex | |
NTIN082 | Nonuniform computational models | 3 | — | 2/0 Ex | |
NTIN104 | Foundations of theoretical cryptography | 4 | 2/1 C+Ex | — |
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
Code | Subject | Credits | Winter | Summer | |
NTIN099 | Algorithms for knowledge representation | 3 | — | 2/0 Ex | |
NAIL094 | Decision procedures and SAT/SMT solvers | 5 | — | 2/2 C+Ex | |
NTIN097 | Hypercube structures | 3 | 2/0 Ex | — | |
NAIL021 | Boolean Functions and Their Applications | 3 | 2/0 Ex | — |
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
Code | Subject | Credits | Winter | Summer | |
NDMI010 | Graph Algorithms | 3 | 2/0 Ex | — | |
NDMI018 | Approximation and Online Algorithms | 5 | — | 2/2 C+Ex | |
NDMI025 | Randomized Algorithms | 5 | — | 2/2 C+Ex | |
NTIN103 | Introduction to Parameterized Algorithms | 5 | 2/2 C+Ex | — |
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
Code | Subject | Credits | Winter | Summer | |
NTIN100 | Introduction to Information Transmission and Processing | 4 | — | 2/1 C+Ex | |
NTIN067 | Data Structures 2 | 3 | — | 2/0 Ex | |
NTIN087 | String Algorithms | 3 | 2/0 Ex | — | |
NDMI010 | Graph Algorithms | 3 | 2/0 Ex | — | |
NSWI072 | Data Compression Algorithms | 3 | 2/0 Ex | — |