Institut für Theoretische Informatik, Algorithmik

Praktikum: Algorithm Engineering

Allgemeines

  • Vorbesprechung: Freitag, 26. Oktober um 9:45 Uhr im SR -119
  • Teilnahme: Die Teilnehmerzahl ist auf zwölf Personen begrenzt. Der Kurs kommt ab einer Mindestzahl von vier Teilnehmern zustande.
    Die Anmeldung ist abgeschlossen.

Aktuelles

Inhalt

Ein dynamischer Graph ist ein Graph, der Operationen wie Einfügen und Entfernen von Kanten unterstützt. Entgegen dem ersten Anschein ist die Implementierung einer schnellen und effizienten Datenstruktur für dynamische Graphen schwieriger als man erwartet. Im Praktikum soll jedes Team an der Entwicklung einer solchen Datenstruktur arbeiten.

Grundkenntnisse in höheren Programmiersprachen wie C++ oder Java sind vorausgesetzt, vertiefte Kenntnisse von Vorteil.

Am Ende des Praktikums wird es einen Wettbewerb geben, in dem dann die „beste“ Datenstruktur gekürt werden soll.

Ablauf

Nach ein paar gemeinsamen Terminen mit einführendem Charakter und einigen Aufwärmaufgaben werden Teams von etwa 3 Personen gebildet. Ziel ist sowohl eine effiziente und „schnelle“ Implementierung einer dynamischen Graphdatenstruktur. Kurz vor Weihnachten wird jede Gruppe in einer Kurzpräsentation ihre bisherige Arbeit vorstellen. Zum Ende des Semesters wird es einen Wettbewerb geben, in dem die Effizienz der erarbeiteten Lösungen getestet wird. Ferner ist eine schriftliche Ausarbeitung zu erstellen und die Ergebnisse in einer Abschlusspräsentation vorzustellen.