Aufgaben zur Vorlesung Algorithm Engineering SS2019

Wahlmöglichkeiten

Wir bieten folgende Wahlmöglichkeiten für die Zusatzaufgabe (1 ECTS) zur Vorlesung Algorithm Engineering an:

• Wikipedia-Artikel schreiben und verteidigen
  • Algorithm Engineering
  • External Memory Algorithms
  • Sorting and Permutations
  • Graph Algorithms
  • Cache-oblivious Algorithms
  • Energy-efficient Algorithms
  • Route Planning
  • Diverses
• Miniseminar

Wikipedia-Artikel

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 auch durch mehrere Personen bearbeitet werden, wovon eine/r den englischen Wikipedia-Artikel schreibt und die/der andere die deutsche Version. Die Liste der Aufgaben ist nicht vollständig und kann um 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.

Ein Beispiel für den vorgesehen Umfang eines guten Artikels ist https://de.wikipedia.org/w/index.php?title=Präfixsumme&oldid=165432173, mindestens jedoch 1000 Wörter. Zur Aufgabe gehört auch die Recherche von Sekundärquellen und weiteren Zitaten, da diese für einen enzyklopädischen Artikel unerlässlich sind. Die Wikipedia-Richtlinen (https://de.wikipedia.org/wiki/Wikipedia:Richtlinien) fordern explizit die Verwendung von Sekundärquellen, Primärquellen allein reichen nicht.

Die Artikel müssen bis 31.7.2019 fertig in der Wikipedia stehen und einen Monat (danach) “verteidigt” werden, also auf die Hinweise und Vorschläge der Editoren reagiert werden.

Zur Anmeldung schreibt mir bitte eine kurze E-Mail: lamm AT kit.edu.

Algorithm Engineering

Aufgabe 1: Übersichtsartikel Algorithm Engineering [1 Teilnehmer: Deu (bearbeitet FL)]

Relevante Artikel

• https://en.wikipedia.org/wiki/Algorithm_engineering

Anmerkungen: Englischer Artikel existiert bereits

Quellen

• “Algorithm Engineering – An Attempt at a Definition”, Peter Sanders
• “Algorithm Engineering for Parallel Computation”, David A Bader, Bernard M.E. Moret and Peter Sanders
• “Algorithm Engineering”, Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano
• “Towards a Discipline of Experimental Algorithmics”, Bernard M. E. Moret

External Memory Algorithms

Aufgabe 1: Übersichtsartikel Exernal Memory Model [2 Teilnehmer: Deu/Eng (bearbeitet RvdG)]

Relevante Artikel

• https://en.wikipedia.org/wiki/External_memory_algorithm
• https://de.wikipedia.org/wiki/Out-of-Core-Algorithmus

Anmerkungen: Englischer Artikel existiert bereits, sollte jedoch stark überarbeitet werden

Aufgabe 2: Exernal Memory Priority Queues [2 Teilnehmer: Deu/Eng (bearbeitet SG)]

Relevante Artikel

• https://en.wikipedia.org/wiki/External_memory_algorithm
• https://de.wikipedia.org/wiki/Vorrangwarteschlange
• https://en.wikipedia.org/wiki/Heap_(data_structure)
• https://de.wikipedia.org/wiki/Heap_(Datenstruktur)

Anmerkungen: Entweder neue Artikel schreiben oder vorhandene erweitern. Unterschiedliche Varianten, etc.

Aufgabe 3: External Memory (Merge-)Sort [1-2 Teilnehmer: Deu (bearbeitet JH)]

Relevante Artikel

• https://en.wikipedia.org/wiki/External_sorting
• https://en.wikipedia.org/wiki/Merge_sort
• https://de.wikipedia.org/wiki/Mergesort

Anmerkungen: Englischer Artikel existiert bereits, sollte jedoch stark überarbeitet werden

Quellen

• “Algorithms and Data Structures for External Memory”, Jeffrey Vitter
• “External Memory Algorithms and Data Structures: Dealing with Massive Data”, Jeffrey Vitter
• “The Input/Output Complexity of Sorting and Related Problems”, Alok Aggarwal and Jeffrey Vitter
• “Algorithms for Parallel Memory I/II”, E.A.M. Shriver and Jeffrey Vitter
• “Cache-Oblivious Algorithms and Data Structures”, Erik Demaine

Sorting and Permutations

Aufgabe 1: Adaptive Sorting [2 Teilnehmer: Deu (bearbeitet BUE)/Eng]

Relevante Artikel

• https://de.wikipedia.org/wiki/Sortierverfahren
• https://en.wikipedia.org/wiki/Adaptive_sort
• https://en.wikipedia.org/wiki/Adaptive_heap_sort
• https://en.wikipedia.org/wiki/Sorting_algorithm#Classification

Anmerkungen: Englischer Artikel existiert bereits, sollte jedoch stark überarbeitet werden

Aufgabe 2: Random Permutations [2 Teilnehmer: Deu/Eng]

Relevante Artikel

• https://de.wikipedia.org/wiki/Zuf%C3%A4llige_Permutation
• https://de.wikipedia.org/wiki/Permutation
• https://de.wikipedia.org/wiki/Mischen_(Spielkarten)#Computergemischte_Karten
• https://en.wikipedia.org/wiki/Random_permutation
• https://en.wikipedia.org/wiki/Permutation#Permutations_in_computing
• https://en.wikipedia.org/wiki/Shuffling#Shuffling_algorithms

Anmerkungen: Artikel existieren bereits, können jedoch stark überarbeitet/ergaenzt werden

Quellen

• “A Survey of Adaptive Sorting Algorithms”, Vladmir Estivill-Castro and Derick Wood
• “A Framework for Adaptive Sorting”, Ola Petersson and Alistair Moffat
• “Cache-aware and Cache-oblivious Adaptive Sorting”, Gerth Stolting Brodal and Rolf Fagerberg and Gabriel Moruz
• “Random Permutations on Distributed, External and Hierarchical Memory”, Peter Sanders
• “Fast Parallel Generation of Random Permutations”, Torben Hagerup
• “Engineering Parallel In-place Random Generation of Integer Permutations”, Jens Gustedt

Graph Algorithms

Aufgabe 1: External Memory Traversierung [1-2 Teilnehmer: Deu/Eng (bearbeitet TG)]

Relevante Artikel

• https://en.wikipedia.org/wiki/Graph_traversal
• https://de.wikipedia.org/wiki/Suchverfahren#Suche_in_Graphen
• https://en.wikipedia.org/wiki/Breadth-first_search
• https://de.wikipedia.org/wiki/Breitensuche
• https://de.wikipedia.org/wiki/Tiefensuche

Anmerkungen: Artikel existieren bereits, können jedoch erweitert werden

Aufgabe 2: External Memory MSTs [2-3 Teilnehmer: Deu/Eng (bearbeitet FK)]

Relevante Artikel

• https://en.wikipedia.org/wiki/Spanning_tree
• https://de.wikipedia.org/wiki/Spannbaum
• https://en.wikipedia.org/wiki/Minimum_spanning_tree
• https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm
• https://de.wikipedia.org/wiki/Algorithmus_von_Bor%C5%AFvka
• https://en.wikipedia.org/wiki/Prim%27s_algorithm
• https://de.wikipedia.org/wiki/Algorithmus_von_Prim
• https://en.wikipedia.org/wiki/Kruskal%27s_algorithm
• https://de.wikipedia.org/wiki/Algorithmus_von_Kruskal

Anmerkungen: Artikel existieren teilweise bereits, können jedoch erweitert werden

Aufgabe 3: External Memory SSSP [1 Teilnehmer: Deu/Eng]

Relevante Artikel

• https://de.wikipedia.org/wiki/K%C3%BCrzester_Pfad
• https://en.wikipedia.org/wiki/Shortest_path_problem
• https://de.wikipedia.org/wiki/Dijkstra-Algorithmus
• https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Aufgabe 4: Graph Generierung [2-4 Teilnehmer: Deu/Eng (bearbeitet MK/MG)]

Relevante Artikel

• https://de.wikipedia.org/wiki/Zufallsgraph
• https://en.wikipedia.org/wiki/Random_graph
• https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model
• https://en.wikipedia.org/wiki/Random_geometric_graph
• https://en.wikipedia.org/wiki/Hyperbolic_geometric_graph
• https://en.wikipedia.org/wiki/Barab%C3%A1si%E2%80%93Albert_model

Anmerkungen: Artikel können um Generierungsmethoden erweitert werden. Wer möchte daruf auch deutsche Artikel zu den Modellen schreiben

Aufgabe 5: Maximum Weight Matching [2 Teilnehmer: Deu/Eng (bearbeitet RA)]

Relevante Artikel

• https://de.wikipedia.org/wiki/Matching_(Graphentheorie)
• https://en.wikipedia.org/wiki/Maximum_weight_matching
• https://en.wikipedia.org/wiki/Matching_(graph_theory)

Anmerkungen: Artikel existieren teilweise bereits, können jedoch erweitert werden

Quellen

• “Elementary Graph Algorithms in External Memory”, Irit Katriel and Ulrich Meyer
• “Improved External Memory BFS Implementations”, Deepak Ajwani, Ulrich Meyer and Vitaly Osipov
• “External-memory Graph Algorithms” Y.-J. Chiang, M. T. Goodrich, E. F. Grove, R. Tamassia, D. E. Vengroff, and J. S. Vitter
• “A Computational Study of External-Memory BFS Algorithms”, D. Ajwani, R. Dementiev, and U. Meyer
• “On External-Memory MST, SSSP and Multiway Planar Graph Separation”, L. A. Arge, G. S. Brodal, and L. Toma
• “Communication-free massively distributed graph generation”, Funke D, Lamm S, Sanders P, Schulz C, Strash D, von Looz M
• “Linear-time Approximation for Maximum Weight Matching”, Duan, Ran and Pettie, Seth
• “A Simpler Linear Time 2/3- ε Approximation for Maximum Weight Matching”, Pettie, Seth and Sanders, Peter
• “A Simple Approximation Algorithm for the Weighted Matching Problem”, Drake, Doratha E and Hougardy, Stefan

Cache-oblivous Algorithms

Aufgabe 1: Cache-oblivious Übersichtsartikel [1 Teilnehmer: Deu (bearbeitet PJ)]

Relevante Artikel

• https://en.wikipedia.org/wiki/Cache-oblivious_algorithm

Aufgabe 2: Funnel/Distribution Sort [1 Teilnehmer: Deu]

Relevante Artikel

• https://en.wikipedia.org/wiki/Cache-oblivious_algorithm
• https://en.wikipedia.org/wiki/Funnelsort
• https://en.wikipedia.org/wiki/Cache-oblivious_distribution_sort

Anmerkungen: Artikel existieren teilweise bereits, können jedoch erweitert werden

Quellen

• “Cache-Oblivious Algorithms and Data Structures”, Erik Demaine
• “Algorithms and Data Structures for External Memory” Jeffrey Vitter

Energy-efficient Algorithms

Aufgabe 1: Übersichtsartikel Energy-efficient Algorithms [2 Teilnehmer: Deu/Eng (bearbeitet PS)]

Anmerkungen: Es existieren kaum Artikel zu diesem Thema

Aufgabe 2: Energy-efficient Sorting [2 Teilnehmer: Deu/Eng]

Anmerkungen: Es existieren kaum Artikel zu diesem Thema

Quellen

• “Energy-Efficient Algorithms”, Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi
• “Algorithms for Energy Saving”, Susanne Albers
• “JouleSort: A Balanced Energy-Efficiency Benchmark” Suzanne Rivoire, Mehul A. Shah, Parthasarathy Ranganathan and Christos Kozyrakis

Route Planning

Aufgabe 1: Contraction Hierarchies [2 Teilnehmer: Deu (bearbeitet LH)/Eng]

Relevante Artikel

• https://en.wikipedia.org/wiki/Contraction_hierarchies

Anmerkungen: Englischer Artikel existiert bereits, kann aber komplett überarbeitet werden

Aufgabe 2: Transit Node Routing [2 Teilnehmer: Deu/Eng (bearbeitet MW)]

Anmerkungen: Es existieren kaum Artikel zu diesem Thema

Aufgabe 3: Multiobjective Shortest Paths [2 Teilnehmer: Deu/Eng]

Relevante Artikel

• https://de.wikipedia.org/wiki/K%C3%BCrzester_Pfad
• https://de.wikipedia.org/wiki/Pathfinding
• https://en.wikipedia.org/wiki/Shortest_path_problem
• https://en.wikipedia.org/wiki/Pathfinding

Anmerkungen: Artikel existieren bereits, können aber deutlich erweitert werden

Quellen

• “Contraction hierarchies: Faster and simpler hierarchical routing in road networks”, Geisberger R, Sanders P, Schultes D, Delling D
• “Exact routing in large road networks using contraction hierarchies”, Geisberger R, Sanders P, Schultes D, Vetter C
• “Time-dependent contraction hierarchies”, Batz G.V, Delling D, Sanders P, Vetter C
• “Fast routing in road networks with transit nodes”, Bast H, Funke S, Sanders P, Schultes D
• “Transit node routing reconsidered”, Arz J, Luxen D, Sanders P

Diverses

Aufgabe 1: Quotient Filters [1 Teilnehmer: Deu]

Relevante Artikel

• https://en.wikipedia.org/wiki/Quotient_filter

Aufgabe 2: Count-min Sketch [1 Teilnehmer: Deu]

Relevante Artikel

• https://en.wikipedia.org/wiki/Count%E2%80%93min_sketch

Aufgabe 3: Sampling Algorithms [2 Teilnehmer: Deu/Eng]

Relevante Artikel

• https://de.wikipedia.org/wiki/Zufallsstichprobe
• https://en.wikipedia.org/wiki/Sampling_(statistics)
• https://en.wikipedia.org/wiki/Reservoir_sampling

Anmerkungen: Mögliche weitere Themen auf Nachfrage

Aufgabe 4: Multilevel Algorithms [2 Teilnehmer: Deu/Eng]

Relevante Artikel

• https://de.wikipedia.org/wiki/Graphpartitionierung#Multilevel-Partitionierung
• https://en.wikipedia.org/wiki/Multi-level_technique
• https://en.wikipedia.org/wiki/Graph_partition

Quellen

• “Parallel Weighted Random Sampling”, Hübschle-Schneider L, Sanders P
• “Efficient Parallel Random Sampling—Vectorized, Cache-Efficient, and Online”, Sanders P, Lamm S, Hübschle-Schneider L, Schrade E, Dachsbacher C
• “A Parallel Bottom-Up Clustering Algorithm with Applications to Circuit Partitioning in VLSI Design”, Jason Cong and M’Lissa Smith
• “A Multi-Level Algorithm For Partitioning Graphs”, Bruce Hendrickson and Robert W. Leland

Miniseminar

Das Miniseminar wird ab Ende der Vorlesungszeit statt finden.

Zu jedem Thema sollen ein 20 minütiger Vortag gehalten werden mit anschließend 5 min Diskussion. Die Vorträge finden an ein oder zwei Blockterminen in den letzten zwei Wochen der Vorlesungszeit statt. Genaue Termine werden noch angekündigt. Die unten aufgelisteten Themen sind nur Vorschläge. Weitere Themen zu einem bestimmten Bereich können auf Nachfrage besprochen werden.

Aufgaben:

• (bearbeitet MG) “BlockQuicksort: Avoiding Branch Mispredictions in Quicksort”, Stefan Edelkamp and Armin Weiss

• “How Good Is Multi-Pivot Quicksort?”, Martin Aumüller, Martin Dietzfelbinger and Pascal Klaue

• (bearbeitet SK) “Predicting Learnt Clauses Quality in Modern SAT Solvers”, Matthias Poloczek and David P. Williamson
  

• “Implementing Efficient All Solutions SAT Solvers”, Takahisa Toda and Takehide Soh

• “An Experimental Evaluation of Fast Approximation Algorithms for the Maximum Satisfiability Problem”, Matthias Poloczek and David P. Williamson

• (bearbeitet PB) “Practical Minimum Cut Algorithms”, Monika Henzinger, Alexander Noe, Christian Schulz and Darren Strash

• (bearbeitet COE) “Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Cover”, Akiba Takuya and Yoichi Iwata

• (bearbeitet DS) “Graph Bisection with Pareto Optimization”, Michael Hamann and Ben Strasser

• (bearbeitet CM) “Customizable Contraction Hierarchies”, Julian Dibbelt, Ben Strasser and Dorothea Wagner

• “Better External Memory LCP Array Construction”, Juha Kärkkäinen and Dominik Kempa

• “LCP Array Construction in External Memory”, Juha Kärkkäinen and Dominik Kempa

• “Inducing Suffix and LCP Arrays in External Memory”, Timo Bingmann, Johannes Fischer and Vitaly Osipov

• (bearbeitet UB) “Simple, Fast and Lightweight Parallel Wavelet Tree Construction”, Johannes Fischer, Florian Kurpicz, Marvin Löbel

• (bearbeitet NU) “Triangle listing algorithms: Back from the diversion”, Ortmann, Mark and Brandes, Ulrik

• (bearbeitet KF) “Scalable and Robust Set Similarity Join”, Tobias Christiani, Rasmus Pagh, Johan Sivertsen