To path indicator To navigation To quick access To footer with other services
To content
Algorithm Engineering
Fakultät für Informatik
Students in summer on north campus, red gears in background. © Roland Baege​/​TU Dortmund

Courses given by Algorithm Engineering

Sommer 2023

Geometrische Algorithmen umfasssen den Entwurf und die Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. In der Vorlesung werden zunächst einige grundlegende Probleme betrachtet: Das Berechnen der konvexen Hülle einer Punktmenge, der Schnittpunkte einer Menge von Strecken, oder einer Triangulierung eines einfachen Polygons. Anschließend sehen wir Algorithmen zum Berechnen bekannter geometrische Strukturen, wie Voronoi-Diagramme, Delaunay-Triangulierungen und Arrangements. Ebenfalls betrachten wir Datenstrukturen für effiziente Anfragen auf geometrischen Daten, wie Range-trees, kd-Bäume und Quadtrees. Dabei kommen vor allem drei Arten von Algorithmen zum Einsatz: inkrementell, teile-und-herrsche, und sweep. Manche von diesen treten als randomisierte Algorithmen auf.

Als Vorkenntnisse wird die Vorlesung “Algorithmen und Datenstrukturen” oder vergleichbare Kenntnisse erwartet.

Prüfung:
  • Studienleistung: aktive Teilnahme (inkl. Präsentation eigener Lösungen)
  • mündliche Prüfung

Weitere Informationen zum Kurs finden Sie im Moodle und LSF.

Prüfungen

  • Studienleistung: erfolgreiche Teilnahme (50% der Punkte) an den wöchentlichen Moodle Quizzen

  • Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik: Klausur, 90 Minuten, 2 Termine

  • Studierende anderer Fachrichtungen haben entweder mündliche Prüfungen oder auch Klausur. Die genauen Konditionen werden in der Vorlesung bekannt gegeben (s. Folien). Im Falle einer Klausur findet diese zeitgleich mit den obigen Klausuren statt. Bitte beachten Sie die Anmeldefristen für die Prüfungen beim Prüfungsamt, die für Klausuren sehr früh sind (i.d.R. 2 Wochen vorher).

Materialien

  • Alle Materialien sind im Moodle-Raum zu finden

Thematische Zusammenfassung

Die in DAP 2 eingeführten Basistechniken werden vertieft und auf komplexere Probleme angewendet, hinzu kommen ausgewählte Probleme mit großen Anwendungsbereichen, weitergehende Aspekte wie Approximation und weitergehende Entwurfsmethoden.

Die Themen lauten u.a.:

  • Hashing Verfahren, String Matching

  • Graphenalgorithmen, wie z.B. starker Zusammenhang in Graphen, Maximale Matchings, Netzwerkflussprobleme, Schnittprobleme (Min Cut und Max Cut), Traveling Salesman Problem, Vertex Cover, MaxSAT

  • Fortgeschrittene Datenstrukturen, wie B-Bäume, Datenstrukturen für Disjunkte Mengen, Augmentierung von Datenstrukturen

  • Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen

  • Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsgüte und -schemata

Literatur

  • Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms. Das Buch ist auch in der Universitätsbibliothek als E-Book in englischer und deutscher Sprache (Algorithmen - Eine Einführung) verfügbar

  • weitere Literaturhinweise und Skripte werden im Moodle bereitgestellt

Course page.

Competitive Programming is about developing algorithmic solutions for concrete problems and implementing them in the shortest possible time. In this course, students deepen their understanding of basic efficient algorithms on the one hand, and practice applying the algorithms and programming under time pressure on the other. The Association for Computing Machinery (ACM) has been organizing the International Collegiate Programming Contest (ICPC) annually since 1970, which we will follow.

In our event, important algorithms and data structures for solving problems from previous years of the ICPC will be presented in talks and solution approaches will be discussed together. In addition to the lectures, tasks will be solved and programmed in a simulated competitive situation in teams of 3. At the end of the semester there is the possibility to participate in the German Winter Contest.

Winter 2022/2023

Course page.

Competitive Programming is about developing algorithmic solutions for concrete problems and implementing them in the shortest possible time. In this course, students deepen their understanding of basic efficient algorithms on the one hand, and practice applying the algorithms and programming under time pressure on the other. The Association for Computing Machinery (ACM) has been organizing the International Collegiate Programming Contest (ICPC) annually since 1970, which we will follow.

In our event, important algorithms and data structures for solving problems from previous years of the ICPC will be presented in talks and solution approaches will be discussed together. In addition to the lectures, tasks will be solved and programmed in a simulated competitive situation in teams of 3. At the end of the semester there is the possibility to participate in the German Winter Contest.

Course page.

An assignment problem seeks an assignment from some set to another that satisfies certain properties. In most assignment problems, so-called agents give preferences about who they want to be assigned to. According to these specifications, the assignment takes place under various optimality criteria, e.g., stability, envy-free, or Pareto optimality (fair matchings). An assignment problem is one-sided or multi-sided depending on how many groups give preferences over the others. The hospital-residents problem is two-sided because both physicians give preferences over hospitals and hospitals give preferences over physicians. In a one-sided assignment problem, a set of agents gives preferences over a set of divisible or indivisible and homogeneous or heterogeneous goods (fair division).

Example: Cut & Choose

  •     Player A divides the bun.
  •     Player B chooses one piece.
  •     Player A gets the other piece.

This algorithm is fair under the criteria of envy-free and proportionality, since both players have equal influence on the outcome.

Course page.

In this seminar we will deal with current research topics of the Algorithm Engineering working group based on selected recent publications in the field of algorithms. The group conducts research on a wide range of algorithmic topics, in particular Algorithm Engineering, Geometric Algorithms and Data Structures, Geometric Networks, Algorithms for Geoinformation Systems, and Algorithms for Motion Planning.

Algorithm Engineering combines theoretical and experimental approaches to algorithm development: design, analysis, implementation, and experimental evaluation of algorithms are equally important in Algorithm Engineering. Accordingly, the research papers on which the seminar is based deal with algorithms theoretically and/or experimentally.

To top of page