Algorithm Engineering

Course outline

• Motivation, peculiarities and importance of algorithm engineering. The algorithm engineering life cycle.
• Development of software platforms and libraries that ease the efficient implementation and experimental evaluation of algorithms and data structures.
• Methodological issues regarding the empirical research of algorithms and data structures. Application of the scientific experimental method. Reproduction of experiments. Creating and searching for proper data sets.
• Program correctness checking. Certifying algorithms and programs.
• Efficient implementation and experimental evaluation of classic and advanced algorithms and data structures. Case studies: graph algorithms, shortest path algorithms, maximum flow algorithms.
• Heuristic methods for enhancing implementations and boosting their performance.
• Arithmetic precision errors and methods for their handling.
• Methodological issues in the process of converting user requirements to efficient and useful algorithmic software.
• Implementation environment: C++ along with the algorithmic software platforms/libraries LEDA, STL and BOOST.
• Special topics: algorithm animation, generative programming, template metaprogramming, policy-based class design.