This course is about fundamental algorithm design paradigms, classic algorithmic problems, and data structures. The connection between algorithms and data structures is explained for geometric and graph problems. For this purpose, fundamental graph theoretic concepts are introduced.
Objective
An understanding of the design and analysis of fundamental algorithms and data structures.
Content
Es werden grundlegende Algorithmen und Datenstrukturen vorgestellt und analysiert. Dazu gehören auf der einen Seite Entwurfsmuster für Algorithmen, wie Induktion, divide-and-conquer, backtracking und dynamische Optimierung, ebenso wie klassische algorithmische Probleme, wie Suchen und Sortieren. Auf der anderen Seite werden Datenstrukturen für verschiedene Zwecke behandelt, darunter verkettete Listen, Hashtabellen, balancierte Suchbäume, verschiedene heaps und union-find-Strukturen. Weiterhin wird Adaptivität bei Datenstrukturen (wie etwa Splay-Bäume) und bei Algorithmen (wie etwa online-Algorithmen) beleuchtet. Das Zusammenspiel von Algorithmen und Datenstrukturen wird anhand von Geometrie- und Graphenproblemen illustriert. Hierfür werden grundlegende Konzepte der Graphentheorie eingeführt.
The performance assessment is offered every session. Repetition possible without re-enrolling for the course unit.
Mode of examination
written 240 minutes
Additional information on mode of examination
Während des Semesters können durch aktive Mitarbeit Bonuspunkte erarbeitet werden. Die Veranstaltung bietet als "Leistungselement" (im Sinne der WEISUNG: Anwendung von Leistungselementen in der Lehre vom 22.12.2017) zwei Arten von Lernelementen an. Die einen Lernelemente sind Bonusaufgaben und klar markierter Teil der wöchentlichen Aufgabensammlung. In maximal 13 Wochen wird es Bonusaufgaben geben. Das andere Lernelement ist Peer Feedback, d.h., die Korrektur der Bonusaufgaben von Kommilitonen in den wöchentlichen Übungen. Die durch die Lernelemente erworbenen Punkte verbessern das Ergebnis der schriftlichen Prüfung um maximal 0.25 Notenpunkte, wobei für dieses Maximum nicht die Maximalpunktzahl erforderlich ist.
Unehrliches Verhalten bei der Bearbeitung der Lernelemente (z.B., Kopieren der Lösungen von Kommilitonen oder anderen Quellen, zur Verfügung stellen der eigenen Lösungen zum Kopieren) haben ernste Konsequenzen inklusive der Aberkennung aller Bonuspunkte dieser Veranstaltung.
Written aids
None
Online examination
The examination may take place on the computer.
If the course unit is part of an examination block, the credits are allocated for the successful completion of the whole block. This information can be updated until the beginning of the semester; information on the examination timetable is binding.
Performance assessment as a semester course