052120 VU Advanced Topics in Algorithms (2019W)

In this lecture, the students obtain a systematic understanding of algorithmic questions and solution approaches in the area of algorithm engineering. The students will be able to transfer the learned techniques onto similar problems and be able to interpret and understand current research topic in the area of algorithm engineering.

Content:
What is algorithm engineering?
Realistic machine models and applications
Algorithm design
Implementation techniques
Experimental methodology
Interpretation of measurements

The listed abilities will be learned by concrete examples. As example we will use topics from the following areas:
FPT/Kernelization in Practice
- Independent set / vertex cover
- Minimum cuts (NOI algorithm, ...)
- Clique cover
- Node ordering
- Exact branch-and-reduce
- ...
Graph partitioning / graph clustering
- NP-completeness
- Modularity clustering (internal, external memory)
- Dynamic clustering
- Multi-level approaches for partitioning
- Spectral techniques
- Exact approaches
- Hypergraph partitioning
- ...
Routen planning
- State-of-the-Art in route planning
- Energy-efficient routing
Graphen drawing
Parallel processing
- Parallel sampling
- Communication-free graph generation
- Process mapping
- ...

In particular, we will almost always cover the best practical and theoretical methods. This methods often deviate a lot by the algorithms learned in the basic courses. We will probably have a small coding competition in which the students develop an algorithm and can compete with each other about the fastest or best solution.