Modules at the chair

AlgoK-ALDAI-B  //  6 ECTS  //  Offered every second winter semester

The past few decades saw an unprecedented increase in the size and complexity of data. We are surrounded by data in everyday life wherever we look. Understanding and analysing this data poses a huge challenge. Many current methods rely in neural networks and heuristics, at the price of sacrificing any guarantees on the computed output. However, guarantees are indispensable in many application areas, such as aviation, cyber-security, finance, medicine and scientific research.

In this module we discuss modern algorithmic approaches that come with guarantees both on the quality of the computed output and on the resource consumption. We also show lower bounds, i.e. infeasibility results. Furthermore, we uncover and exploit surprising connections between different areas of computer science.

The topics include machine learning with guarantees, highly efficient property testing algorithms for huge graphs, networks and databases, exploiting tame structure of inputs via treewidth, designing 
fixed-parameter algorithms for notoriously hard problems, tackling various computational problems simultaneously through logic, highlighting applications in computational biology and exploiting connections between database query evaluation and constraint satisfaction in AI.

Prerequisites: Successful completion of Inf-DM-B, Inf-LBR-B and AI-AuD-B. Solid mathematical skills, including proof techniques and first-order logic, and a general interest in theoretical methods.
Preferable but not compulsory: AlgoK-AK-B. Good English language skills.

No ECTS credit  //  Every semester

This is an interactive tutorial addressing content from ongoing maths and theory modules, open to all students at our faculty, organised on a drop-in basis. Sessions are based on questions and suggestions from attendees. All students are invited and attendance is optional with no registration needed.

Drop in to ask questions if you need help, or to work on your current exercises in a supervised setting, or to fill gaps in your maths and theory knowledge, or to take your knowledge further.

Welcome topics include:

• Any basic mathematics for computer science
• Theoretical computer science and complexity
• General computer science areas

Prerequisites: none.

Note: the basic language of the tutorial is English.

Inf-DM-B  //  9 ECTS  //  Winter semester

Modeling is a fundamental tool for working in many areas of computer science and beyond. Models are used to describe scenarios precisely, which is the first step to solving problems using computer science methods. It is important to choose a model which suits the problem you are working on, and the discrete mathematics offers a wide range of tools for this.

Precise argumentation is essential for sustainable, reliable modeling and problem solving, so practicing the language of mathematics is a central theme of this module. This offers the security of being able to rely on the models you use and the solutions they give.

In the modules we will introduce and discuss propositional and predicate logic, sets, relations, functions, graphs, trees, combinatorics, formal languages and finite automata, using modeling examples. Further, techniques of mathematical proof will be taught and practised.

Prerequisites: this module is recommended for students at the start of their studies. Good English language skills.

AlgoK-TAG  //  6 ECTS  //  Offered every second winter semester

Many classical algorithmic problems on graphs are hard, e.g. NP-hard, in general. However, they lie at the core of many applications, so they need to be solved in practice. These problems include the famous Graph Colouring Problem, and problems such as Hamiltonian Cycle, Independent Set, Dominating Set, Vertex Cover and many more. Ideally, we would like to solve these problems exactly and efficiently.

Indeed, many problems become solvable in linear time if we only allow trees as inputs. This observation is the starting point of the module. We then identify more general classes of input graphs that allow solving many problems efficiently. For this we make use of so-called tree decompositions of graphs. Tree decompositions allow us to obtain "tree like" graphs that are more general than trees but maintain the favourable algorithmic properties of trees.

In the first part of the module we study tree decompositions via a cops-and-robber game played on graphs, where the winning strategies for the cops yield the desired decompositions. We then develop algorithms for tree decompositions and algorithms to solve problems efficiently making use of tree decompositions. In the second part of the module we introduce monadic second order logic (MSO) on graphs and we prove a famous theorem by Bruno Courcelle that shows how to solve all problems expressible in MSO efficiently on "tree-like" graphs. This includes all aforementioned algorithmic problems.
We make links to state-of-the-art research in the area and to practical applications, e.g. in compiler construction.

Note: This module is formally a BSc module. However, it can of course also be taken by MSc students within the allowed limit of BSc credits.

Prerequisites: Algorithms and data structures, basic knowledge of predicate logic, proof techniques, interest in combinatorial games on graphs. Good English language skills.

AlgoK-Algo-M  //  6 ECTS  //  Summer semester

Algorithms and algorithmic problem solving are at the heart of computer science. This module introduces students to the design and analysis of efficient algorithms. Students learn how to quantify the efficiency of an algorithm and what algorithmic solutions are efficient. Techniques for designing efficient algorithms are taught, including efficient data structures. We begin with standard methods such as Divide-and-Conquer and Dynamic Programming. We then move on to more advanced techniques and we discuss ways of dealing with computationally intractable problems and large data sets. This is done using illustrative and fundamental problems relevant to Computer Science and AI.

Prerequisites: Basic knowledge of algorithms and data structures, proof techniques, mathematical skills. Good English language skills.

AlgoK-AK-B  //  6 ECTS  //  Summer semester

Algorithms and problem solving lie at the heart of computer science. Given an algorithmic problem, such as the Traveling Salesperson Problem, how can we design an efficient algorithm? Once we found an algorithm that solves the problem correctly, can we be sure that the resources, such as running time, storage space (and related: energy), required by this algorithm are really necessary for solving the problem? Perhaps we can do better?

Prerequisites: algorithms and data structures, basic knowledge of computability theory, proof techniques. Good English language skills.

AlgoK-Sem-B/M  //  3 ECTS  //  Every semester

Offered every semester on varying topics.

Prerequisites: Successful completion of a course on scientific work, LaTeX, mathematical skills, proof techniques, and a general interest in theoretical methods. Good English language skills. 

AlgoK and GdI  //  No ECTS credit  //  Every semester

This is our joint research seminar, in particular for PhD students and postdocs in the groups. We use it as a platform to exchange research ideas and current interests. Guests, including students, are also very welcome.

AlgoK-Proj-B/M  //  6 ECTS  //  new from SS2026

Planned to start in SS2026.