Efficient Algorithms and Data Structures

First, the basics of algorithm analysis are covered. Then fundamental data structures and basic algorithmic problems are presented.
As for the basics of algorithm analysis, various machine models, complexity measures and the solving of recurrence relations are studied.
Regarding fundamental data structures, various search trees, hashing schemes, priority queues and union-find data structures are investigated.
As for basic algorithms, the focus is on the development of numerous max-flow and min-cut algorithms as well as algorithms for matching problems.

After completing the module, the students are able to analyze and to assess the runtime and the memory requirements of algorithms. Furthermore, they have a good understanding of numerous fundamental algorithms and data structures. This understanding enables them to design algorithms and data structures for new algorithmic problems.

IN0015 Discrete Structures, IN0007 Fundamentals of Algorithms and Data Structures, IN0018 Discrete Probability Theory

The module consists of lectures and tutorials. The content of the lectures is conveyed by presentations of the scientific material. By solving homework assignments, the students are encouraged to work intensively on the respective topics. The solutions of the assignments are discussed in the tutorials. The homework assignments are graded so that students get an individual feedback on their learning success.

Slides, whiteboard, homework assignments

Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman: The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974.
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein: Introduction to Algorithms. McGraw-Hill, 1990.
Michael T. Goodrich, Roberto Tamassia: Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, 2002.
Volker Heun: Grundlegende Algorithmen: Einführung in den Entwurf und die Analyse effizienter Algorithmen, 2. Auflage, Vieweg, 2003.
Jon Kleinberg, Eva Tardos: Algorithm Design. Addison-Wesley, 2005.
Donald E. Knuth: The Art of Computer Programming. Vol. 1: Fundamental Algorithms. 3. Auflage, Addison-Wesley, 1997.
Donald E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching. 3. Auflage, Addison-Wesley, 1997.
Christos H. Papadimitriou, Kenneth Steiglitz: Combinatorial Optimization: Algorithms and Complexity. Prentice Hall, 1982.
Uwe Schöning: Algorithmik. Spektrum Akademischer Verlag, 2001.
Steven S. Skiena: The Algorithm Design Manual. Springer, 1998.

The exam takes the form of a 150 minutes written test. In the written exam, based on the questions posed, the students are intended to prove that they know the conceptual and mathematical basics of algorithm analysis. Moreover, the students are expected to demonstrate that they have profound and advanced knowledge in the area of efficient data structures and algorithms. They show that they are able to recognize and analyze typical algorithmic problems and to find efficient solutions within a limited scope of time.