Wir bieten folgende Wahlmöglichkeiten für die Übungsaufgabe zur Vorlesung Algorithm Engineering an:
Programmierwettbewerb: Sliding Block Hashing (Slick), Benchmarkergebnisse
Wir wollen SlickHash in seinen unterschiedlichen Varianten implementieren und gegeneinander antreten lassen. Dazu stellen wir ein C++ Framework bereit, das Laufzeit und Speicherverbrauch messen, visualisieren und gegen anderen Hashtabellen vergleichen kann. Zusätzlich gibt es eine Webseite mit automatisch erstellten Benchmarkergebnissen, die Ihre Implementierung fortlaufend anonym gegen die Ihrer Kommilitonen antreten lässt. (Nicht maßgebend für die anschließende Bewertung Ihrer Übungsleistung.)
Falls Sie sich für die Programmieraufgabe entscheiden, folgen Sie bitte den Anweisungen in der README.md des C++ Frameworks und melden sich nach erstmaligem Einloggen im KIT Gitlab per kurzer E-Mail an.
Ziel der Programmieraufgabe ist es, eine SlickHash Tabelle mit mindestens den Operationen insert(), at() und contains() zu implementieren.
Das entsprechende Interface wird in der Datei slickhash.h im Framework bereits definiert; wer die Aufgabe in Rust bearbeiten will, darf sein eigenes Interface definieren.
Allgemein geht es bei der Programmieraufgabe aber nicht nur um eine korrekte Implementierung des Hashtabelle, sondern auch um die Anwendung von Techniken und Optimierungsverfahren, die in der Vorlesung vorgestellt werden, sowie der experimentellen Evaluation.
Um die Implementierungen etwas diverser zu gestalten, dürfen Sie sich für einen Aspekt entscheiden, auf den Sie Ihre Implementierung optimieren:
build() effizienter als durch wiederholtes Aufrufen von insert().at() bzw. contains() Operationen dominiert wird.erase() Funktion inklusive backyard cleaning.Je nach Wahl kann eine andere im Preprint beschriebene SlickHash Variante die vielversprechendste Wahl sein.
Zusätzlich zur Implementierung soll ein kurzes Dokument verfasst werden, das den verfolgten Ansatz erläutert und anhand von Messungen evaluiert. An das Dokument stellen wir folgende Anforderungen:
Abgabe (ergänzt am 28.02.2024): Sie können das Dokument zur Abgabe in Ihr Implementierungs-Repository legen oder per E-Mail einreichen.
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 eine Liste mit Themen aus der Vorlesung, zu denen die jeweiligen 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.
Bevor man mit dem Editieren auf Wikipedia beginnt, ist es ratsam, sich vorher einmal in die herrschenden Gepflogenheiten einzulesen. Insbesondere raten wir zu folgenden Hinweisen:
Relevante Artikel:
Relevante Literatur:
Relevante Artikel:
Relevante Literatur:
Zu jedem Thema soll ein 20 minütiger Vortrag gehalten werden mit anschließender 5-minütiger Diskussion. Eine schriftliche Ausarbeitung ist explizit nicht vorgesehen.
| Paper | Autoren | Reserviert |
|---|---|---|
| RecSplit: Minimal Perfect Hashing via Recursive Splitting | E. Esposito, T. M. Graf, S. Vigna | LB |
| Binary Fuse Filters: Fast and Smaller Than Xor Filters | T. M. Graf, D. Lemire | |
| Simulating Population Protocols in Sub-Constant Time per Interaction | P. Berenbrink, D. Hammer, D. Kaaser, U. Meyer, M. Penschuck, H. Tran | |
| A 'Learned' Approach to Quicken and Compress Rank/Selection Dictionaries | A. Boffa, P. Ferragina, G. Vinciguerra | JB |
| Space-Efficient, High-Performance Rank and Select Structures on Uncompressed Bit Sequences | D. Zhou, D. G. Andersen | |
| An Efficient Approach to Merging Paired-End Reads and the Incorporation of Uncertainties | T. Flouri, J. Zhang, L. Czech, K. Kobert, A. Stamatakis | |
| A Back-to-Basics Empirical Study of Priority Queues | D. Larkin, S. Sen, R. E. Tarjan | |
| Engineering Predecessor Data Structures for Dynamic Integer Sets | P. Dinklage, J. Fischer, A. Herlez | |
| Multilevel Algorithms for Acyclic Partitioning of Directed Acyclic Graphs | J. Herrmann, M. Y. Özkaya, B. Ucar, K. Kaya, Ü. V. Catalyürek | |
| Compressing Graphs and Indexes with Recursive Graph Bisection | L. Dhulipala, I. Kabiljo, B. Karrer, G. Ottaviano, S. Pupyrev, A. Shalita | CK |
| Graph Partitioning using Quantum Annealing on the D-Wave System | H. Ushijima-Mwesigwa, C. F. A. Negre, S. M. Mniszewski | |
| Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time | L. Dhulipala, D. Eisenstat, J. Lacki, V. Mirrokni, J. Shi | |
| Incremental DFS Algorithms: A Theoretical and Experimental Study | S. Baswana, A. Goel, S. Khan | |
| Efficient and Robust Approximate Nearest Neighbor Search using Hierarchical Navigable Small World Graphs | Y. A. Malkov, D. A. Yashunin | JH |
| SAT-and-Reduce for Vertex Cover: Accelerating Branch-and-Reduce by SAT Solving | R. Plachetta, A. van der Grinten | |
| Approximation Multiobjective Shortest Path in Practice | F. Bökler, M. Chimani | |
| Shortest-path Feasibility Algorithms | B. V. Cherkassky, L. Georgiadis, A. V. Goldberg, R. E. Tarjan, R. F. Werneck | |
| Distance Closures: Unifying Search- and Lookup-based Shortest Path Speedup Techniques | D. Bahrdt, S. Funke, S. Makolli, C. Proissl | PS |
| Practical Fully Dynamic Minimum Cut Algorithms | M. Henzinger, A. Noe, C. Schulz |