Fundamentals of Algorithms and Data Structures

First, the module studies the basics of efficiency and complexity analyses. Basic terminology, complexity measures, the Landau symbols and different machine models are introduced. Then, fundamental data structures and algorithmic problems are studied.
- Data structures for sequences: Dynamic arrays, lists, stacks and queues are investigated. The complexity of each operation is analyzed.
- Hashing: Hashing with chaining, universal hashing as well as various probing methods are examined. Perfect hashing and hash-based algorithms, e.g. for set intersection problems, may also be explored.
- Sorting: First, simple algorithms such as InsertionSort, SelectionSort and BubbleSort are reviewed. Then, advanced algorithms such as MergeSort, HeapSort and QuickSort are investigated. Furthermore, sorting-based algorithms, the lower bound for comparison-based sorting, selection, RadixSort and external sorting may be covered.
- Priority queues: Binary heaps and binomial heaps are presented in the module.
- Search trees: Binary search trees, AVL trees and (a,b)-trees are investigated.
- Graph algorithms: Various graph representations, traversal techniques using DFS/BFS, the computation of 2-connected components and strongly connected components, topological sorting, the computation of the shortest paths and minimum spanning trees are covered. Approaches for solving the Traveling Salesman Problem (TSP) may be studied.
The module may also cover data compression schemes (Huffman, Lempel-Ziv) and simple pattern matching algorithms.

The participants master the basic algorithms and data structures mentioned above. They are able to independently analyze their complexity and apply the corresponding analysis concepts to related algorithmic problems. Furthermore, the participants are able to use the algorithms and data structures handled, if necessary to modify them and to compare different solutions in their quality.

IN0001 Introduction to Informatics 1, IN0015 Discrete Structures

The module consists of lectures and exercises. The content of the lectures is conveyed in 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 exercises. The homework assignments are graded so that students get an individual feedback on their learning success.

Slides, whiteboard, homework assignments

Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures - The Basic Toolbox. Springer, 2008.
Complementing material for the module is contained in the following books.
- Volker Heun: Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2. Edition, Vieweg, 2003.
- Michael T. Goodrich, Roberto Tamassia. Algorithm Design - Foundations, Analysis, and Internet Examples. John Wiley & Sons, 2002.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 3rd edition, MIT Press, 2009. German translation: Algorithmen - Eine Einführung. 3. Auflage, Oldenbourg Verlag, 2010.
- Jon Kleinberg, Eva Tardos. Algorithm Design. Pearson Education, 2005.
- Uwe Schöning. Algorithmik. Spektrum Akademischer Verlag, 2001.
- Robert Sedgewick, Kevin Wayne: Algorithms. 4th edition, Addison-Wesley, 2011.
- Robert Sedgewick. Algorithms in Java, Parts 1-4. 3rd edition, Addison-Wesley, 2002. German translation: Algorithmen in Java, Teil 1-4. 3. Auflage, Pearson Education, 2003.

The exam takes the form of a 90 minutes written test. In the written exam, based on the questions posed, the students are intended to demonstrate that they have fundamental knowledge in the area of algorithms and data structures. They are able to apply their knowledge successfully in order to solve given problems. In addition, by answering the questions, the students are expected to show that they have profound knowledge of the fundamental algorithmic methods and data structures covered in the module. The students prove that they are able to recognize and analyze basic algorithmic problems and to find efficient solutions within a limited scope of time.