Past Courses

The course addresses problems at the interface of economics, social choice theory, and computer science. The focus is on processes of algorithmic decision making, such as voting rules or fair division. We discuss fundamental concepts from collective decision making and related topics and investigate algorithmic and computational aspects.

Specific topics include:

• aggregating preferences (rank aggregation) and voting,
• algorithmic game theory,
• cake cutting protocols,
• fair allocation of resources,
• judgment aggregation,
• opinion diffusion, and
• stable matching.

This course was offered in winter term '22/'23 and winter term '23/'24. It will be repeated regularly.

DE:
Spiele und Berechnungen sind eng miteinander verknüpft. Zum Beispiel sind teils komplexe Berechnungen nötig um erfolgreich zu spielen. Doch auch Spiele mit ihren festen Regeln können genutzt werden, um Berechnungen darzustellen und zu simulieren.

In diesem Seminar werden zum einen (bekannte und weniger bekannte) Spiele (Brett-, Karten-, oder auch Computerspiele) bzgl. ihrer Berechnungskomplexität analysiert. Andererseits aufgezeigt, dass auch einfache Spielregel alternative mächtige Brechnungsmodelle bereitstellen können (welche oft Turingmachinen nicht unterlegen sind).

Teilnehmende Studierende erarbeiten sich selbstständig ihr gewähltes Thema. Hierzu wird Literatur bereitgestellt, die als Startpunkt dienen soll. Eigene Literaturrecherche wird erwartet. Regelmäßiger Fortschritt vor dem Vortrag wird durch Treffen mit dem Betreuer überprüft.

ENG:
Games and computations are closely linked. For example, sometimes complex calculations are necessary to play successfully. However, games with their fixed rules can also be used to visualize and simulate calculations.

In this seminar, (well-known and less known) games (board, card, or computer games) are analyzed with regard to their computational complexity. Moreover, it is shown that simple game rules can also provide powerful alternative computation models (which are often not inferior to Turing machines).

Participating students work independently on their chosen topic. Literature is provided for this purpose, which should serve as a starting point. Own literature research is expected. Regular progress before the lecture is checked by meetings with the supervisor.

This course was offered in winter term '22/'23 and winter term '23/'24. It will be repeated regularly.

Lecture: Advanced Algorithmics / Fortgeschrittene Algorithmik (Master)

After successful completion of the course, students will be able to develop and analyze algorithms for computational problems from various application areas. For a concrete computational problem, they will be able to chose a strategy to efficiently solve the problem from a wide range of advanced techniques.This includes strategies for solving problems that are computationally hard in the worst case. In particular, the students know about current research topics in algorithmics. Particular topics include:

• algorithmic game theory,
• algorithmic graph theory,
• approximation and online algorithms,
• computational geometry,
• computational social choice,
• distributed algorithms,
• online algorithms,
• parameterized and exact algorithms,
• randomized algorithms and analysis,
• universal solvers.

This course was offered in summer term '22, summer term '23, summer term '24. For details, please visit the studip course page.

DE:

Graphenalgorithmen sind eine der wichtigsten Komponenten der Algorithmik und haben viel Aufmerksamkeit von Mathematikern und Informatikern erhalten. Darüber hinaus werden die Algorithmen auf Graphen in der Praxis weithin eingesetzt und bieten Lösungen für verschiedene Bereiche. 

In diesem Seminar werden wir uns mit den Ideen und Werkzeugen fortgeschrittener Graphenalgorithmen befassen, wie z. B. Baumzerlegung, Flussnetzwerke, Spiele auf Graphen, usw. Darüber hinaus werden wir auch Graphenalgorithmen in enger Verbindung mit einer Analyse ihrer Komplexität diskutieren.

Die Studierenden müssen ihr eigenes Thema wählen und dazu recherchieren.    Eine Liste von Büchern und Arbeiten wird zur Verfügung gestellt, um den Studenten bei der Auswahl eines geeigneten Themas zu helfen. Die Tutoren werden den Fortschritt überprüfen und während des Semesters Hilfestellung leisten.

EN:

Graph algorithms are one of the most important components of algorithmics and have received much attention from mathematicians and computer scientists. Furthermore, algorithms on graphs are widely used in practice and offer solutions for various fields.

In this seminar, we will deal with the ideas and tools of advanced graph algorithms, such as tree decomposition, flow networks, games on graphs, etc. Additionally, we will discuss graph algorithms in close connection with an analysis of their complexity.

Students must choose their own topic and research it. A list of books and papers will be provided to help students select a suitable topic. The tutors will review the progress and provide assistance throughout the semester.

This course was offered in summer term '23. It will be repeated regularly.