de | en

Fundamentals of Algorithms and Data Structures

Module IN0007

This Module is offered by TUM Department of Informatics.

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.

Basic Information

IN0007 is a semester module in German language at Bachelor’s level which is offered in summer semester.

Total workloadContact hoursCredits (ECTS)
180 h 75 h 6 CP

Content, Learning Outcome and Preconditions

Content

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.

Learning Outcome

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.

Preconditions

IN0001 Introduction to Informatics 1, IN0015 Discrete Structures

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

Learning and Teaching Methods

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

Media

Slides, whiteboard, homework assignments

Literature

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.

Module Exam

Description of exams and course work

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 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.

Exam Repetition

The exam may be repeated at the end of the semester.

Current exam dates

Currently TUMonline lists the following exam dates. In addition to the general information above please refer to the current information given during the course.

Title
TimeLocationInfoRegistration
Grundlagen: Algorithmen und Datenstrukturen
Mo, 5.8.2019, 16:00 bis 18:30 MW: 0350
PH: 2501
PH: 2502
CH: 21010
00.02.001
MI: 00.02.001
Interims II: 003
Interims II: 004
MW: 2050
Interims I: 101
Interims I: 102
MW: 0001
MW: 1050
MW: 1350
MW: 1450
MW: 1550
MW: 1801
MW: 2001
Import bis 30.6.2019 (Abmeldung bis 29.7.2019)
Top of page