Algorithm Engineering: Materialien zur Vorlesung

1. Skript zusammengestellt von Felix Putze.
2. Vorlesung
3. Präsentation: inplace super scalar sample sort
4. Präsentation: dynamic space efficient hash tables
5. Präsentation: FilterKruskal

Themenwünsche für die Übung bitte an Yaroslav Akhremtsev und Demian Hespe (yaroslav.akhremtsev∂kit edu, hespe∂kit edu).

Prüfungstermine:

Miniseminar Vortragsthemen

Termine: 18. Juli und 25. Juli 14:00-17:15

Ort: -118 (14:00-15:30) und 236 (15:45-17:15)

1. Simple and Space-Efficient Minimal Perfect Hash Functions Botelho, F. C., Pagh, R. & Ziviani, N. In: WADS 2007 proceedings.
   bearbeitet von Lasse Wulf
2. Shortest-path feasibility algorithms. Cherkassky, B. V., Georgiadis, L., Goldberg, A. V., Tarjan, R. E., & Werneck, R. F. (2009). Journal of Experimental Algorithmics, 14, 2.7.
   bearbeitet von Matthias Graeser
3. An improved data stream summary: the count-min sketch and its applications. Cormode, G., & Muthukrishnan, S. (2005). Journal of Algorithms, 55(1), 58–75.
   bearbeitet von David Schneider
4. Lightweight Approximate Selection. Dean, B. C., Jalasutram, R., & Waters, C. (2014). In ESA'14 proceedings.
   bearbeitet von N.N.
5. 2-Connectivity in Directed Graphs: An Experimental Study. Di Luigi, W., Georgiadis, L., Italiano, G. F., Laura, L., & Parotsidis, N. (2015). In ALENEX 2015 proceedings
   bearbeitet von Steven Grothnes
6. Balanced allocation and dictionaries with tightly packed constant size bins. Dietzfelbinger, M., & Weidling, C. (2007). Journal of Theoretical Computer Science, 380(1-2), 47–68.
   bearbeitet von Kolja Esders
7. Graph Partitioning using Quantum Annealing on the D-Wave System Hayato Ushijima-Mwesigwa, Christian F. A. Negre, Susan M. Mniszewski. arxiv May 2017
   bearbeitet von N.N.
8. Cache Replacement with Memory Allocation. Ghandeharizadeh, S., Irani, S., & Lam, J. (2015). In ALENEX 2015 proceedings.
   bearbeitet von Simon Sudrich
9. A Back-to-Basics Empirical Study of Priority Queues Larkin, D., Sen, S., & Tarjan, R. E. In: ALENEX 2014 proceedings. Technical report available here
   bearbeitet von Anne Borcherding
10. An Even Simpler Linear-Time Algorithm for Verifying Minimum Spanning Trees. Hagerup, T. (2010). In LNCS vol. 5911, pp. 178-189
    bearbeitet von Matthias Schimek
11. A new algorithm for the minimum spanning tree verification problem. Williamson, M., Subramani, K. (2014). In Comput Optim Appl vol. 61, pp. 189-204
    bearbeitet von Holger Ebhart
12. Chaff: engineering an efficient SAT solver. Matthew W. Moskewicz, Conor F. Madigan, Ying Zhao, Lintao Zhang, Sharad Malik. In 38th Design Automation Conference (DAC 2001). pp. 530-535.
    bearbeitet von Dominik Schreiber
13. Type less, find more: fast autocompletion search with a succinct index. Holger Bast, Ingmar Weber. In 29th ACM SIGIR conference on Research and development in information retrieval (2006). pp. 364-371
    bearbeitet von N.N.
14. 2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection. David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, Manuel R. Torres. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017). pp. 247-260.
    bearbeitet von Victor Pfautz

Programmieraufgaben

• Taken Parallel evolutionary framework: Define an interface that can do the following things when provided with the respective implementations: Find an upper bound on the number of colors required, generate an initial population in parallel, apply crossover operations in parallel, apply local search for mutation in parallel. Just for orientation of what to expect: Hybrid Evolutionary Algorithms for Graph Coloring

• Taken Greedy initialization: DSATUR, ordering by degree. Read up here: Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning
• Taken XRLF. Read up here: Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning
• Taken Tabu search with 1-exchange neighbourhood (TS 1-ex). Read up here: A survey of local search methods for graph colouring
• Taken Iterated local search (ILS). Read up here: Stochastic Local Search Algorithms for the Graph Colouring Problem, Stochastic Local Search Methods for Highly Constrained Combinatorial Optimisation Problems (PhD thesis)
• Taken Simulated annealing with Kempe chain neighbourhood (SA Kempe). Read up here: Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning
• Taken K-fixed partial legal Tabucol + dynamic tenure strategy. Read up here: A Reactive Tabu Search Using Partial Solutions for the Graph Coloring Problem, A survey of local search methods for graph colouring
• Taken Greedy crossover. Read up here: Hybrid Evolutionary Algorithms for Graph Coloring
• Taken Partitioning based crossover. Read up here: Evolutionary Graph Coloring (Bachelor Thesis)
• Taken Preprocessing rules. Read up here: Stochastic Local Search Algorithms for the Graph Colouring Problem
• Taken Simulated annealing with penalty strategy (1-exchange). Read up here: Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning
• Taken Simulated annealing with k-fixed penalty. Read up here: Optimization by simulated annealing: an experimental evaluation; part ii, graph coloring and number partitioning
• Taken Tabu search with min-conflicts heuristics. Read up here: Stochastic Local Search Algorithms for the Graph Colouring Problem; Local Search Algorithms for Combinatorial Problems (PhD thesis)
• Taken Guided local search. Read up here: Stochastic Local Search Algorithms for the Graph Colouring Problem
• Taken Overlap Crossover. Read up here: Evolutionary Graph Coloring (Bachelor Thesis)
• Taken Initialization algorithm from A GRASP for Coloring Sparse Graphs