Algorithms and Data Structures 2 - Interactive curriculae of TU Ilmenau

The interactive curriculae provide information on the degree programmes offered by the TU Ilmenau.

Please refer to the respective study and examination rules and regulations for the legally binding curricula (Annex Curriculum).

You can find all details on planned lectures and classes in the course catalogue.

Please note that this page is no longer updated. All modules and study plans from PO version 2021 onwards (Bachelor and Master study programs) are now available on the Campus Portal.

module properties Algorithms and Data Structures 2 in degree program Master Wirtschaftsinformatik 2021
module number	200064
examination number	2200713
department	Department of Computer Science and Automation
ID of group	2242 (Algorithms)
module leader	Prof. Dr. Christoph Berkholz
term	winter term only
language	Deutsch
credit points	5
on-campus program (h)	45
self-study (h)	105
obligation	elective module
exam	written examination performance, 90 minutes
details of the certificate
link to Moodle course	https://moodle.tu-ilmenau.de/course/view.php?id=3557
teacher
signup details for alternative examinations
maximum number of participants
previous knowledge and experience	Algorithmen und Datenstrukturen 1 Mathematik 1 und 2
learning outcome	Fachkompetenz: Die Studierenden kennen Entwurfsprinzipien für Algorithmen (Divide-and-Conquer, Greedy, Dynamische Programmierung) und die zugehörigen Analyseverfahren und können sie in einfachen Fällen zum Algorithmenentwurf einsetzen. Sie kennen spezielle Divide-and -Conquer-Algorithmen und können das "Master-Theorem" zur Analyse einsetzen. Sie kennen die Verfahren "Breitensuche" und "Tiefensuche", und können die Situationen identifizieren, in denen diese Verfahren benutzt werden müssen. Sie kennen weitere Anwendungen der Tiefensuche (Kantenklassifizierung, Kreisfreiheit, topologische Sortierung, starke Zusammenhangskomponenten) mit Korrektheitsbeweisen. Die Studierenden kennen Algorithmen für die Berechnung kürzester Wege (Dijkstra, Bellman/Ford) mit ihren Anwendbarkeitsbereichen und den Korrektheitsbeweisen. Sie kennen die Datenstruktur "adressierbare Priority Queue" mit Implementierungs- und Anwendungsmöglichkeiten. Sie kennen weitere Algorithmen für die Berechnung eines minimalen Spannbaums (mit Korrektheitsbeweisen) und der dafür nötigen Union-Find-Datenstruktur. Sie kennen Algorithmen für das "All-pairs-Shortest-Paths"-Problem auf der Basis des Prinzips "Dynamische Programmierung", sowie weitere Beispiele für die Anwendung dieses Prinzips. Methodenkompetenz: Die Studierenden kennen und verstehen fortgeschrittenere Korrektheitsbeweise und beherrschen wesentliche Techniken für solche Beweise. Sie überblicken die Zusammenhänge zwischen der Bereitstellung von (grundlegenden und fortgeschrittenen) Datenstrukturen und effizienten Algorithmen. Sie kennen Rechenzeitaussagen und ihre Herleitung. Auf dieser Basis können sie in verschiedenen Anwendungsfeldern die für kkonkrete Aufgaben geeigneten Algorithmen auswählen und diese Auswahl sachgerecht begründen. Sozialkompetenz: Die Studierenden haben die Erfahrung gemacht, dass zur Erreichung des Ziels der Vorlesung die Herstellung einer gemeinsamen konzentrierten Arbeitsatmosphäre wesentlich ist. Diskussionsbeiträge und Fragen werden von den Lehrenden und den Studierenden immer begrüßt. Die Studierenden können sich aktiv und interagierend an der Diskussion der Lösung der Übungsaufgaben in der Übung beteiligen. Sie erkennen, dass unterschiedliche Herangehensweisen zum Ziel führen können, im Rahmen der mathematischen Regeln und des Standes der Kunst.
content	Die Vorlesung gliedert sich entlang verschiedener Strategien des Algorithmenentwurfs. I Divide-and-Conquer Mergesort, Quicksort Multipliktion ganzer Zahlen schnelle Matrixmultiplikation Polynommultiplikation und schnelle Fouriertransformation Selektion in Linearzeit II Dynamische Programmierung Textsegmentierung Longest Increasing Subsequence Editierdistanz Matrixkettenmultiplikation Maximum Independent Set auf Bäumen All-Pairs-Shortest Path, Algorithmus von Floyd-Warshall III Greedy-Verfahren Scheduling Huffman Codes IV Algorithmendesign für schwere Probleme Exponentialzeitalgorithmen mit dynamischer Programmierung: TSP, ganzzahliges Rucksackproblem, 0/1-Rucksackproblem Backtracking für Suchprobleme: Pre- und Inprocessing, 3-SAT Backtracking für Optimierungsprobleme: Maximum Independent Set; Branch-and-Bound: Max-SAT, TSP Parametriesierte Algorithmen: FPT-Algorithmen, Methode der beschränkten Suchbäume, Kernelisierung Approximationsalgorithmen: Vertex Cover, TSP, Max-SAT, Max-Cut, Set-Cover, Subset-Sum (PTAS)
media of instruction and technical requirements for education and examination in case of online participation	Folien, Skript, Tafelvortrag
literature / references	Das Standardwerk (für AuD1, AuD2 und darüber hinaus): T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009 (auch auf deutsch bei Oldenbourg) Weitere Lehrbücher: J. Erickson: Algorithms, online, 2019 T. Ottmann, P. Widmayer, Algorithmen und Datenstrukturen, Spektrum Akademischer Verlag, 2002 R. Sedgewick, Algorithms, Addison-Wesley, 2002 (auch C-, C++, Java-Versionen, auch auf deutsch bei Pearson) R. Sedgewick, Algorithms, Part 5: Graph Algorithms, Addison-Wesley, 2003 K. Mehlhorn, P. Sanders, Algorithms and Data Structures - The Basic Toolbox, Springer, 2008 R. H. Güting, S. Dieker: Datenstrukturen und Algorithmen, B.G. Teubner Verlag, 2004
evaluation of teaching