Zur Anmeldung bitte eine kurze E-Mail an: hans-peter.lehmann AT kit.edu und daniel.seemaier AT kit.edu und sascha.witt AT kit.edu
Wir bieten folgende Wahlmöglichkeiten für die Zusatzaufgabe zur Vorlesung Algorithm Engineering an:
Wir stellen ein C++ Framework bereit, das Laufzeit und Speicherplatzverbrauch messen sowie Plots erstellen kann. Das Framework stellt naive Beispielimplementierungen zum Vergleich bereit. Die Aufgaben können gerne auch in anderen Sprachen implementiert werden, dazu haben wir aber kein Framework. Gerne kann dann trotzdem das Plot-Skript aus dem Framework verwendet werden, indem das gleiche CSV-Ausgabeformat verwendet wird.
Zusätzlich zur Implementierung soll ein kurzes Dokument verfasst werden, das den verfolgten Ansatz erläutert und anhand von Messungen evaluiert.
Eine Zuordnung von n Keys zu je einer Zahl kleiner m. Diese Zahlen könnten beispielsweise als Adresse benutzt werden, um Daten abzuspeichern. Für eine gegebene Menge von Keys dürfen keine Kollisionen auftreten. Die Funktion wird einmal konstruiert und dann nur noch mit Queries benutzt. Bei Anfrage von Keys, die nicht in der Menge waren, darf ein beliebiger Wert zurückgegeben werden. Zu optimieren sind Speicherplatzverbrauch und "Füllgrad", also n/m. Häufige Werte sind n/m=0.98, n/m=0.81 oder n/m=0.5. Der Spezialfall n=m heißt Minimum Perfect Hash Function.
Relevante Literatur:Perfekte Hashfunktionen, die bis zu K Kollisionen pro Funktionswert erlauben. Eine Anwendung wäre es, dass nur die Speicherseite abgerufen werden soll und dort dann Daten gespeichert werden. K-Perfect hashing erlaubt eine platzeffizientere Repräsentation der Funktion.
Relevante Literatur:Ein statischer Key-Value-Store. Die Datenstruktur wird mit allen Keys generiert und kann dann queries beantworten. Bei Anfrage von Keys, die nicht abgespeichert wurden, darf ein beliebiger Wert zurückgegeben werden. Im Gegensatz zu beispielsweise hash maps kann die Datenstruktur repräsentiert werden, ohne dass die Keys mit abgespeichert werden. Dadurch ist für r-bit werte ein Speicherplatzverbrauch von etwa (1+O(1))*n*r bits möglich.
Relevante Literatur:Eine mögliche Implementierung von Perfect Hashing ist es, eine Zuordnung g(x) von Elementen zu (normalen) Hashfunktionen h_i zu bestimmen, sodass h_{g(x)} minimum perfect ist. Im Framework wird das über eine Cuckoo-Hashtabelle gelöst: Alle Elemente werden eingefügt, aber uns interessiert am Ende nur noch, an welcher der Positionen das Element dann abgespeichert wurde. Eine alternative Herangehensweise ist es, einen Hypergraphen zu konstruieren, wobei jede Hyperkante für ein Element x die Positionen h_i(x) verbindet. Peeling bezeichnet dann den Vorgang, schrittweise die Kanten wegzunehmen, sodass am Ende jedem Element eine Position (und damit eine der Hashfunktionen) zugeordnet ist.
Relevante Literatur: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. 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.
Aufgabe 1: Perfect Hash Function: Aktuelle praktikable Konstruktionsmethoden mit O(n) Bits zusammenfassen und ein konkretes Beispiel ausführen (z.B. CHD). (Vergeben: JM)
Relevante Artikel: Relevante Literatur:Aufgabe 2: Static Function Data Structure: Seite neu erstellen, Beispiele für konkrete Implementierungen und für Anwendungen. (Vergeben: JW)
Relevante Literatur:Zu jedem Thema soll ein 20 minütiger Vortrag gehalten werden mit anschließender 5-minütiger Diskussion. Die Vorträge finden voraussichtlich am letzten Vorlesungstermin, dem 20.07.2021 um 16:00 statt. Wenn notwendig, wird es noch einen zweiten Termin kurz danach geben. Die unten aufgelisteten Themen sind nur Vorschläge. Weitere Themen zu einem bestimmten Bereich können auf Nachfrage besprochen werden.
Aufgaben: