Modules at the chair

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.

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?

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.

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.

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

AlgoK-TAG  //  6 ECTS  //  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.