Aktuelle Themen im Algorithm Engineering (WS 2019/2020)

Seminarbetreuung

Prof. Dr. Ulrich Meyer
Manuel Penschuck
Alex Schickedanz
Hung Tran

Sprechzeiten nach Vereinbarung.
Organisatorische Fragen bitte an Alex Schickedanz.

Inhalt

Gegenstand dieses Seminars sind parallele Modelle, Entwurfsmethoden und Algorithmen sowie deren Analyse.

Termine

Die Vorbesprechung fand am 18.10.2019 um 14:15 Uhr in H14 statt.

Organisation

Die Themen werden während der Vorbesprechung vergeben. Bis zur Abgabe der Ausarbeitungs sind zwei Treffen mit dem jeweiligen Betreuer vorgesehen und eines danach zur Besprechung der Folien. Das Blockseminar findet dann gegen Ende des Semesters statt. Die genauen Termine werden während der Vorbesprechung oder einzeln festgelegt.

Das Seminar gilt als bestanden, wenn sowohl der Vortrag als auch die Ausarbeitung bestanden wurde.

Vergebene Themen

Basis-Algorithmen

• B1: Stefan Edelkamp, Armin Weiß: Worst-Case Efficient Sorting with QuickMergesort. ALENEX 2019: 1-14 Quelle
• B3: Nicolas Auger, Vincent Jugé, Cyril Nicaud, Carine Pivoteau: On the Worst-Case Complexity of TimSort. ESA 2018: 4:1-4:13, Quelle

Graphen und Netzwerke

• G1: Für 2er Team: Albert-László Barabási, Network Science. Kapitel 1,3,4,7,9 Quelle
• G2: Erzeugen von Erdos-Renyi Graphen
  • Kapitel 1 und 2A aus Efficient generation of large random networks Batagelj, U Brandes - Physical Review E, 2005 - APS, Quelle
  • Erdos, P.; Rényi, A. (1959). “On Random Graphs. I”. Publicationes Mathematicae. 6: 290–297. Quelle
• G5: Thomas Bläsius, Cedric Freiberger, Tobias Friedrich, Maximilian Katzmann, Felix Montenegro-Retana, Marianne Thieffry, Efficient Shortest Paths in Scale-Free Networks with Underlying Hyperbolic Geometry. ICALP 2018: 20:1-20:14, Quelle
• G6: k Shortest Path.
  • Jin Y. Yen, Finding the K Shortest Loopless Paths in a Network Quelle
  • Gang Feng, Finding k Shortest Simple Paths in Directed Graphs: A Node Classification Algorithm Quelle
• G7: N. Katoh, T. Ibaraki, H. Mine, An efficient algorithm for K shortest simple paths (optimized for undirected graphs) Quelle

Verschiedene Themen

• V1: The EM model. Einführung in das Modell, untere und obere Schranken für Sortieren: Ulrich Meyer, Peter Sanders, Jop F. Sibeyn: Algorithms for Memory Hierarchies, Advanced Lectures [Dagstuhl Research Seminar, March 10-14, 2002]. Kapitel 1 ohne Parallelism, Kapitel 3.1, 3.2, 3.3 Quelle
• V2: Ulrich Meyer: On Dynamic Breadth-First Search in External-Memory. STACS 2008: 551-560 Quelle
• V3: Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck, Nodari Sitchinava: Fragile Complexity of Comparison-Based Algorithms. ESA 2019: 2:1-2:19. Kapitel 1, 2.1, 2.2 ohne Beweise, 4 Quelle
• V4: Timo Bingmann, Phelim Bradley, Florian Gauger, Zamin Iqbal, COBS: a Compact Bit-Sliced Signature Index. Quelle