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

Das Modul behandelt zunächst die Grundlagen der Analyse von Effizienz bzw. Komplexität. Es werden grundlegende Begriffe, Komplexitätsmaße, die Landau-Symbole sowie verschiedene Maschinenmodelle eingeführt. Danach studiert das Modul grundlegende Datenstrukturen und algorithmische Probleme. - Datenstrukturen für Sequenzen: Untersucht werden dynamische Arrays, Listen, Stapel und Warteschlangen. Dabei wird jeweils die Komplexität der einzelnen Operationen hergeleitet. - Hashing: Im Kern werden Hashing mit Verkettung, universelles Hashing sowie verschiedenen Sondierverfahren vorgestellt. Das Modul behandelt optional perfektes Hashing und hash-basierte Algorithmen, zum Beispiel für das Problem des Mengendurchschnitts. - Sortieren: Das Modul wiederholt zunächst einfache Verfahren wie InsertionSort, SelectionSort und BubbleSort. Anschließend werden fortgeschrittene Verfahren wie MergeSort, HeapSort und QuickSort analysiert. Optional werden sortierbasierte Algorithmen, die untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort sowie externes Sortieren vorgestellt. - Prioritätswarteschlangen: Das Modul untersucht binäre Heaps und Binomialheaps. - Suchbäume: Das Modul behandelt binäre Suchbäume, AVL-Bäume und (a,b)-Bäume. - Graphalgorithmen: Das Modul studiert verschiedene Graphrepräsentation, Traversierungstechniken per DFS/BFS, die Berechnung von Zweifachzusammenhangskomponenten und starken Zusammenhangskomponenten, topologische Sortierung, die Berechnung von kürzesten Wegen und minimalen Spannbäumen. Optional werden Lösungsverfahren für das Traveling Salesman Problem (TSP) vorgestellt. Im Stoffspektrum des Moduls sind optional Datenkompressionverfahren (Huffman, Lempel-Ziv) und einfache Algorithmen für das Problem des Pattern Matchings vorgesehen.

Learning Outcome

Die Teilnehmer beherrschen grundlegende Das Modul behandelt zunächst die Grundlagen der Analyse von Effizienz bzw. Komplexität. Es werden grundlegende Begriffe, Komplexitätsmaße, die Landau-Symbole sowie verschiedene Maschinenmodelle eingeführt. Danach studiert das Modul grundlegende Datenstrukturen und algorithmische Probleme. - Datenstrukturen für Sequenzen: Untersucht werden dynamische Arrays, Listen, Stapel und Warteschlangen. Dabei wird jeweils die Komplexität der einzelnen Operationen hergeleitet. - Hashing: Im Kern werden Hashing mit Verkettung, universelles Hashing sowie verschiedenen Sondierverfahren vorgestellt. Das Modul behandelt optional perfektes Hashing und hash-basierte Algorithmen, zum Beispiel für das Problem des Mengendurchschnitts. - Sortieren: Das Modul wiederholt zunächst einfache Verfahren wie InsertionSort, SelectionSort und BubbleSort. Anschließend werden fortgeschrittene Verfahren wie MergeSort, HeapSort und QuickSort analysiert. Optional werden sortierbasierte Algorithmen, die untere Schranke für vergleichsbasiertes Sortieren, Rang-Selektion, RadixSort sowie externes Sortieren vorgestellt. - Prioritätswarteschlangen: Das Modul untersucht binäre Heaps und Binomialheaps. - Suchbäume: Das Modul behandelt binäre Suchbäume, AVL-Bäume und (a,b)-Bäume. - Graphalgorithmen: Das Modul studiert verschiedene Graphrepräsentation, Traversierungstechniken per DFS/BFS, die Berechnung von Zweifachzusammenhangskomponenten und starken Zusammenhangskomponenten, topologische Sortierung, die Berechnung von kürzesten Wegen und minimalen Spannbäumen. Optional werden Lösungsverfahren für das Traveling Salesman Problem (TSP) vorgestellt. Im Stoffspektrum des Moduls sind optional Datenkompressionverfahren (Huffman, Lempel-Ziv) und einfache Algorithmen für das Problem des Pattern Matchings vorgesehen.

Preconditions

IN0001 Einführung in die Informatik 1, IN0015 Diskrete Strukturen

Courses, Learning and Teaching Methods and Literature

Courses and Schedule

ArtSWSTitelDozent(en)Termine
VO 3 Grundlagen: Algorithmen und Datenstrukturen (IN0007) Dienstag, 14:00–16:00
Mittwoch, 13:15–14:15
UE 2 Tutorübungen zu Grundlagen: Algorithmen und Datenstrukturen (IN0007) Termine in Gruppen

Learning and Teaching Methods

Das Modul besteht aus einer Vorlesung und einer begleitenden Übungsveranstaltung. 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

Kurt Mehlhorn, Peter Sanders: Algorithms and Data Structures - The Basic Toolbox. Springer, 2008. Vertiefendes und ergänzendes Material zur Vorlesung findet sich in folgenden Büchern: - Volker Heun: Grundlegende Algorithmen - Einführung in den Entwurf und die Analyse effizienter Algorithmen. 2. Auflage, 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. Deutsche Übersetzung: 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. Deutsche Übersetzung: Algorithmen in Java, Teil 1-4. 3. Auflage, Pearson Education, 2003.

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 über fundamentale Kenntnisse im Bereich der Algorithmen und Datenstrukturen verfügen und diese erfolgreich bei der Lösung von Problemen anwenden können. Ferner demonstrieren Studierende beim Lösen der gestellten Aufgaben, dass sie die im Modul behandelten Datenstrukturen und grundlegenden algorithmischen Methoden beherrschen. Die Studierenden weisen nach, dass sie in begrenzter Zeit grundlegende algorithmische Probleme erkennen und analysieren können sowie Wege zu einer effizienten Lösung finden können.

Exam Repetition

There is a possibility to take the exam 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, 26.9.2016, 10:30 bis 13:00 MW: 0001
101
MW: 2001
bis 19.9.2016

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.