Institut für Theoretische Informatik, Algorithmik

Algorithm Engineering for the Engineering Sciences

Overview

  • Lecturer: Guest Professor Dr. , University of Patras
  • Dates: Tuesdays, 17:30-19:00. Starts 18.10.2011.
  • Room: SR 236, Informatik-Hauptgebäude (50.34), 2nd floor. Campus map, Bing Maps
  • Audience: PhD and master students of non-CS departments, e.g. Engineering Sciences, Business Engineering and Mathematics. Also for interested CS students.

Description

Algorithm engineering aims at establishing a systematic framework – in the spirit of Popper’s scientific method – to deal with the (time-consuming and error-prone) process of converting theoretically efficient algorithms and data structures into useful software, rendering implementations and experimentation valuable tools for improved design and precise analysis of algorithms and data structures.
The Algorithm Engineering course discusses methodological and practical issues of this process and in particular it is concerned with:

  • The design, effective implementation (as well as its enhancement with speed-up heuristics), fine tuning, debugging, and extensive experimental evaluation of algorithms to the point that they can be of real practical value.
  • The development of correct implementations.
  • The development of software repositories and platforms that allow for the easy implementation and experimental evaluation of algorithms.
  • Methodological issues regarding experimental research on algorithms and data structures.
  • Methodological issues involved in the process of converting user requirements into efficient algorithmic solutions and implementations.

The course focuses on fundamental and advanced combinatorial algorithms and data structures. The underlying implementation environment will be C++ along with the STL, LEDA, and BOOST libraries.

Material

LEDA, STL, and BOOST

Main References

Algorithm Engineering

  • M. Mueller-Hannemann and S. Schirra, Algorithm Engineering, LNCS Vol. 5971, Springer, 2010.

Implementation of Algorithms and Data Structures

  • A. Alexandrescu, Modern C++ design: Programming and Design Patterns Applied, Addison-Wesley, 2001.
  • K. Mehlhorn and S. Naeher, LEDA: A platform for combinatorial and geometric computing, Cambridge University Press, 1999. Link
  • M.A. Weiss, Data structures and problem solving with C++, 2nd Edition, Addison-Wesley, 2000.

C++

  • A. Koenig and B. Moo, Accelerated C++, Addison-Wesley, 2000.
  • S.B. Lippman and J. Lajoie, C++ Primer, 3rd Edition, Addison-Wesley, 1998.

Further References

Implementation of Algorithms and Data Structures

  • T. Budd, Data structures in C++ using the standard template library, Addison-Wesley, 1998.
  • F. Carrano, P. Helman, and R. Veroff, Data abstraction and problem solving with C++, 2nd Edition, Addison-Wesley, 1998.
  • N. Jossutis, The C++ standard library: a tutorial and a reference, Addison Wesley Longman, 1999.
  • E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of data structures in C++, Computer Science Press, 1995.
  • S. Sahni, Data structures, algorithms and applications in C++, WCB/McGraw-Hill, 1998.
  • J.Siek, A.Lumsdaine, and L.Lee, The Boost Graph Library: User Guide and Reference Manual, Addison Wesley, 2002.

C++ and Object-Oriented Programming

  • T. Budd, An Introduction to Object-Oriented Programming, 2nd Edition, Addison-Wesley, 1997.
  • H.M. Deitel and P.J. Deitel, C++ : How to Program, 2nd Edition, Prentice-Hall, 1998.
  • E. Gamma, R. Helms, R. Johnson, and J. Vlissides, Design Patterns: Elements of Reusable Object-Oriented Software, Addison-Wesley, 1995.
  • S. Meyers, Effective C++, 2nd Edition, Addison-Wesley, 1997.
  • B. Stroustrup, The C++ Programming Language, 3rd Edition, Addison-Wesley, 1997.