Wir bieten folgende Wahlmöglichkeiten für die Zusatzaufgabe zur Vorlesung Algorithm Engineering an:
! Sie finden die Anforderungen zum kurzen schriftlichen Dokument, das zur Abgabe der Programmieraufgabe gehört nun im README.md des C++ Framework !
Wir stellen ein C++ Framework bereit, das Laufzeit und Speicherplatzverbrauch messen (sowie Plots erstellen, [aktuell noch nicht verfügbar]) kann. (Die finalen Benchmarkgraphen/graphkonfigurationen sind ebenfalls noch nicht verfügbar und werden noch bekannt gegeben.) Das Framework stellt naive Beispielimplementierungen zum Vergleich bereit. Jede Aufgabe kann von mehreren Personen bearbeitet werden. Einzelne Aufgaben könnten dabei (nach Rücksprache) auch zu zweit bearbeitet werden. Zusätzlich zur Implementierung soll ein kurzes Dokument verfasst werden, das den verfolgten Ansatz erläutert und anhand von Messungen evaluiert (Details zu den Anforderungen an das Dokument finden Sie im README.md des C++ Framework). Falls Aufgaben zu zweit bearbeitet werden, erwarten wir eine etwas umfangreichere Evaluation/mehr Implementierungsvarianten als bei einer Einzelbearbeitung.
Allgemein geht es bei der Programmieraufgabe nicht nur um eine korrekte Implementierung des jeweiligen Algorithmus, vielmehr erwarten wir, dass Techniken und Optimierungsvarianten, wie sie in der VL vorgestellt werden, auf das jeweilige Problem angewendet werden. Optimierungsvarianten, die ausprobiert wurden, aber zu keiner Laufzeitverbesserung geführt haben, können natürlich ebenso im Bericht aufgeführt werden.
Für die Programmieraufgaben ist es vollkommen ausreichend, sich auf sequentiellen Code zu beschränken. Eine Parallelisierung ist nicht erforderlich.
Ein MST-Konstruktions-Algorithmus berechnet für einen Eingabegraphen G einen minimalen Spannbaum (bzw. aufspannenden Wald, falls G nicht zusammenhängend ist) von G und gibt diesen als Kantenliste aus.
Implementierung des Filter-Kruskal Algorithmus. Neben allgemeinen Optimierungen sollen insbesondere auch verschiedene Rekursionsabbruchbedingungen und Partitionierungssvarianten (z.B. skewed Partitionierung) evaluiert werden.
Relevante Literatur:Implementierung eines MST-Algorithmus, der sich am oben genannten Filter-Kruskal Algorithmus orientiert, aber den Algorithmus von Boruvka als Basis-Algorithmus nutzt. Neben allgemeinen Optimierungen können auch verschiedene Rekursionsabbruchbedingungen und Partitionierungsvarianten (z.B. skewed Partitionierung) evaluiert werden.
Relevante Literatur:Implementierung des Jarnik-Prim Algorithmus für MSTs. Als Priority Queue soll eine der folgenden Datenstrukturen verwendet (und optimiert) werden:
Implementierung des unten genannten MST Algorithmus mit (erwartet) linearer Laufzeit. Der MST-Verifikationsschritt wird dabei mittels einer von uns bereitgestellten BlackBox-Implementierung gelöst und muss nicht selbst implementiert werden. Diese fließt auch nicht in die Laufzeitmessung mit ein.
Relevante Literatur:Implementierung des unten genannten MST Algorithmus. Als Datenstruktur zur Kantenverifikation soll eine der folgenden Strategien verwendet werden:
Bei der MST-Verifikation bekommt man anders als bei der MST-Konstruktion als Eingabe bereits einen Graphen G und einen Spannbaum T von G. Ein MST-Verifikationsalgorithmus gibt aus, ob es sich bei T um einen minimalen Spannbaum handelt. Falls T kein minimaler Spannbaum ist, wird zusätzlich eine Kante aus T ausgegeben, die nicht in einem MST von G enthalten sein kann.
Implementierung eines MST-Verifikationsalgorithmus auf Basis des oben genannten MST Algorithmus. Hierbei muss auf dem Eingabe-Spannbaum T der Jarnik-Prim-Algorithmus ausgeführt werden. Anschließend wird die Kantenklassifikation wie im Paper beschrieben auf allen Kanten von G ausgeführt. Falls hierbei eine T-leichte Kante gefunden wird, die nicht in T enthalten ist, kann diese als Zeuge ausgegeben und der Algorithmus terminiert werden. Als Datenstruktur zur Kantenverifikation soll eine der folgenden Strategien verwendet werden:
Wir wollen den Themenbereich Algorithm Engineering in Wikipedia deutlich verbessern. Als Zusatzaufgabe zur Vorlesung Algorithm Engineering soll daher ein oder mehrere Wikipedia-Artikel neu geschrieben oder verbessert werden.
Es folgt unten eine Liste mit Themen aus der Vorlesung, zu denen jeweils die Wikipedia-Artikel zu wünschen übrig lassen. Eigene Ideen für Artikel zu anderen Themen im Bereich Algorithm Engineering sind auch willkommen. Diese sollen mit neuem Text, hinreichend vielen Referenzen, schönen (animierten) Illustrationen, Pseudocode, Analysen, und vielem mehr angereichert oder neu erstellt werden. Eine Aufgabe kann durch mehrere Personen bearbeitet werden, wovon eine/r den englischen Wikipedia-Artikel schreibt und die/der andere die deutsche Version. Die Liste der Vorschläge ist nicht vollständig und kann durch sinnvolle Vorschläge ergänzt werden.
Teil der Aufgabe besteht auch darin den bearbeiteten Text zu "verteidigen", falls Wikipedia-Editoren den Inhalt anfechten. Sollte es zu unbegründeten Konflikten kommen, fließt dies jedoch natürlich nicht in die Bewertung ein.
Zu jedem Thema soll ein 20 minütiger Vortrag gehalten werden mit anschließender 5-minütiger Diskussion.
Aufgaben: