Fundamentals of Algorithms and Data Structures
This module handbook serves to describe contents, learning outcome, methods and examination type as well as linking to current dates for courses and module examination in the respective sections.
IN0007 is a semester module in German language at Bachelor’s level which is offered in summer semester.
|Total workload||Contact hours||Credits (ECTS)|
|180 h||75 h||6 CP|
Content, Learning Outcome and Preconditions
- 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.
Courses, Learning and Teaching Methods and Literature
Courses and Schedule
|VO||3||Fundamentals of Algorithms and Data Structures (IN0007)||
Tue, 13:45–16:15, MW 0001
|UE||2||Fundamentals of Algorithms and Data Structures, Exercise Session (IN0007)||dates in groups|
Learning and Teaching Methods
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.
Description of exams and course work
The exam may be repeated at the end of the semester.