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

CodeSubjectCreditsWinterSummer
NTIN090Introduction to Complexity and Computability 42/1 C+Ex
NTIN066Data Structures 1 62/2 C+Ex
NTIN022Probabilistic Techniques 52/2 C+Ex
NTIN063Complexity 42/1 C+Ex
NTIN100Introduction to Information Transmission and Processing 42/1 C+Ex
NSZZ023Diploma Thesis I 60/4 C
NSZZ024Diploma Thesis II 90/6 C
NSZZ025Diploma Thesis III 150/10 C

2.2 Elective Courses

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

CodeSubjectCreditsWinterSummer
NAIL021Boolean Functions and Their Applications 32/0 Ex
NTIN096Pseudo-Boolean Optimization 32/0 Ex
NAIL094Decision procedures and SAT/SMT solvers 52/2 C+Ex
NDMI010Graph Algorithms 32/0 Ex
NDMI018Approximation and Online Algorithms 52/2 C+Ex
NDMI025Randomized Algorithms 52/2 C+Ex
NSWI072Data Compression Algorithms 32/0 Ex
NTIN067Data Structures 2 32/0 Ex
NDMI074Algorithms and Their Implementation 52/2 C+Ex
NTIN081Computational complexity and interactive protocols 32/0 Ex
NTIN082Nonuniform computational models 32/0 Ex
NTIN087String Algorithms 32/0 Ex
NTIN097Hypercube structures 32/0 Ex
NTIN099Algorithms for knowledge representation 32/0 Ex
NTIN103Introduction to Parameterized Algorithms 52/2 C+Ex
NOPT034Mathematical Programming and Polyhedral Combinatorics 42/1 C+Ex
NTIN104Foundations of theoretical cryptography 42/1 C+Ex
NDMI067Flows, Paths and Cuts 32/0 Ex
NDMI077Algorithms for Specific Graph Classes 32/0 Ex
NDMI088Graph Algorithms 2 32/0 Ex
NMAG536Proof Complexity and the P vs. NP Problem 32/0 Ex
NMAI067Logic in Computer Science 32/0 Ex
NTIN017Parallel Algorithms 32/0 Ex
NTIN023Dynamic Graph Data Structures 32/0 Ex
NTIN064Computability 32/0 Ex
NTIN073Recursion 32/0 Ex
NTIN084Bioinformatics Algorithms 52/2 C+Ex
NTIN085Selected Topics in Computational Complexity I 42/1 C+Ex
NTIN086Selected Topics in Computational Complexity II 42/1 C+Ex
NTIN101Selected Topics in Algorithms 32/0 Ex
NTIN111Selected Topics in Algorithms II 32/0 Ex
NTIN110Selected Topics in Data Structures 32/0 Ex
NTIN088Algorithmic Randomness 32/0 Ex
NTIN102Seminar on theory of computing 30/2 C0/2 C
NDMI093Seminar on algorithms and data structures 30/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.

CodeSubjectCreditsWinterSummer
NDMI007Combinatorial Algorithms 52/2 C+Ex
NAIL116Social networks and their analysis 52/2 C+Ex
NOPT042Constraint Programming 52/2 C+Ex
NAIL076Logic Programming 1 32/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

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

CodeSubjectCreditsWinterSummer
NTIN063Complexity 42/1 C+Ex
NTIN081Computational complexity and interactive protocols 32/0 Ex
NTIN082Nonuniform computational models 32/0 Ex
NTIN104Foundations of theoretical cryptography 42/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

CodeSubjectCreditsWinterSummer
NTIN099Algorithms for knowledge representation 32/0 Ex
NAIL094Decision procedures and SAT/SMT solvers 52/2 C+Ex
NTIN097Hypercube structures 32/0 Ex
NAIL021Boolean Functions and Their Applications 32/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

CodeSubjectCreditsWinterSummer
NDMI010Graph Algorithms 32/0 Ex
NDMI018Approximation and Online Algorithms 52/2 C+Ex
NDMI025Randomized Algorithms 52/2 C+Ex
NTIN103Introduction to Parameterized Algorithms 52/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

CodeSubjectCreditsWinterSummer
NTIN100Introduction to Information Transmission and Processing 42/1 C+Ex
NTIN067Data Structures 2 32/0 Ex
NTIN087String Algorithms 32/0 Ex
NDMI010Graph Algorithms 32/0 Ex
NSWI072Data Compression Algorithms 32/0 Ex