Efficient Algorithms and Data Structures

Module IN2003

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

IN2003 is a semester module in English language at Bachelor’s level und Master’s level which is offered in winter semester.

This Module is included in the following catalogues within the study programs in physics.

  • Catalogue of non-physics elective courses
Total workloadContact hoursCredits (ECTS)
240 h 90 h 8 CP

Content, Learning Outcome and Preconditions

Content

Das Modul behandelt zunächst die Grundlagen der Algorithmenanalyse. Anschließend werden fundamentale Datenstrukturen und grundlegende algorithmische Probleme behandelt. Im Bereich der Grundlagen der Algorithmenanalyse studiert das Modul verschiedene Maschinenmodelle, Komplexitätsmaße sowie das Lösen von Rekursionsgleichungen. Auf dem Gebiet der fundamentalen Datenstrukturen stellt das Modul verschiedene Suchbäume, Hash-Verfahren, Prioritätswarteschlangen und Union-Find-Datenstrukturen vor. Im Bereich der grundlegenden Algorithmen konzentriert sich das Modul auf die Entwicklung von zahlreichen Maxflow- und Mincutalgorithmen sowie auf Algorithmen für das Matching-Problem.

Learning Outcome

Nach der Absolvierung des Moduls sind Studenten in der Lage, die Laufzeit und den Speicherplatzbedarf von Algorithmen zu analysieren und zu bewerten. Darüber hinaus verfügen sie über ein grundlegendes Verständnis für die Arbeitsweise zahlreicher fundamentaler Algorithmen und Datenstrukturen. Dieses Verständnis versetzt sie in die Lage, für neue Probleme selbständig Algorithmen und Datenstrukturen zu entwickeln.

Preconditions

IN0015 Diskrete Strukturen, IN0007 Grundlagen: Algorithmen und Datenstrukturen, IN0018 Diskrete Wahrscheinlichkeitstheorie

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

ArtSWSTitelDozent(en)Termine
VO 4 Efficient Algorithms and Data Structures (IN2003) Freitag, 10:00–12:00
Montag, 10:00–12:00

Learning and Teaching Methods

Das Modul besteht aus einer Vorlesung und einer begleitenden Übung. Die Inhalte der Vorlesung werden im Vortrag und durch Präsentation vermittelt. Studierende werden insbesondere durch die Lösung von Übungsblättern zur inhaltlichen Auseinandersetzung mit den Themen angeregt. Die Lösung der Übungsaufgaben wird in der Übungsveranstaltung besprochen. Zusätzlich erhalten die Studenten durch die Korrektur der Übungsblätter eine individuelle Rückmeldung über ihren Lernerfolg.

Media

Folien, Tafelarbeit, Übungsblätter

Literature

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.

Module Exam

Description of exams and course work

Die Prüfungsleistung wird in Form einer Klausur erbracht. In dieser weisen Studierende anhand der gestellten Aufgaben nach, dass sie die begrifflichen und mathematischen Grundlagen der Algorithmenanalyse beherrschen. Ferner zeigen die Studierenden, dass sie über fundamentale und weitergehende Kenntnisse im Bereich der effizienten Datenstrukturen und Algorithmen verfügen. Sie weisen nach, dass sie in begrenzter Zeit typische algorithmische Probleme erkennen und analysieren können sowie Wege zu einer Lösung finden.

Exam Repetition

There is a possibility to take the exam at the end of the semester.

Condensed Matter

When atoms interact things can get interesting. Fundamental research on the underlying properties of materials and nanostructures and exploration of the potential they provide for applications.

Nuclei, Particles, Astrophysics

A journey of discovery to understanding our world at the subatomic scale, from the nuclei inside atoms down to the most elementary building blocks of matter. Are you ready for the adventure?

Biophysics

Biological systems, from proteins to living cells and organisms, obey physical principles. Our research groups in biophysics shape one of Germany's largest scientific clusters in this area.