de | en

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

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.

Learning Outcome

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.

Preconditions

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

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

TypeSWSTitleLecturer(s)Dates
VO 4 Efficient Algorithms and Data Structures (IN2003) Fri, 10:00–12:00, Interims I 102
Mon, 10:00–12:00, Interims I 102
TT 2 Efficient Algorithms and Data Structures, Exercise Session (IN2003) dates in groups

Learning and Teaching Methods

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.

Media

Slides, whiteboard, homework assignments

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

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.

Exam Repetition

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

Top of page