Grundzüge von Algorithmen und Datenstrukturen

Grundvorlesung, 2+2

Allgemeine Informationen

Dozent:	Andreas Karrenbauer
Assistent:	Maximilian John
Zeit und Raum:	Donnerstag, 12-14 Uhr, E2.2 HS 0.01 (Günther Hotz-Hörsaal)
Arbeitsaufwand:	2 SWS Vorlesungen, 2 SWS Übungen 6 Leistungspunkte 30 Stunden Kontaktzeit für die Vorlesungen. 30 Stunden Kontaktzeit für die Übungen 120 Stunden Selbststudium.

Neuigkeiten

Die Gruppeneinteilung ist veröffentlicht (s. Abschnitt Übungsgruppen). Die Anmeldung zur Vorlesung ist geschlossen. Ab sofort sind Anmeldungen nur noch per Mail an Maximilian John möglich.
Den Link zum Feedback-System der Vorlesung finden Sie in den Folien zur ersten Vorlesung.
Um sich für den Kurs anzumelden, müssen Sie sich sowohl im LSF als auch auf unserer Mailingliste registrieren. Den Link zur Mailingliste finden Sie hier. Alle relevanten Informationen zur Vorlesung werden über diese Mailingliste angekündigt.
Am 31.10. wird Übungsgruppe 1 im Raum 023 in E1.4 stattfinden.
Die erste Übung findet am 28.10. statt, es werden Präsenzübungen bearbeitet. Da die Gruppeneinteilung erst später fertiggestellt wird, kann jeder Student eine beliebige Gruppe aufsuchen.

Inhalte

Die Vorlesung umfasst folgende Themengebiete aus dem Bereich Algorithmen und Datenstrukturen:

Laufzeit(-analyse)
Listen, Stacks, Heaps, Bäume, etc.
Suchen, Sortieren
Dynamische Programmierung
Greedy Algorithmen
Graphalgorithmen

und vieles mehr.

Kursmaterial

Datum	Thema	Referenzen	Hausaufgabe	Sonstiges
27 Okt	Einführung	Folien, 2.1-2.5 in [DMS]	Übung 0, Übung 1	Lösung 0, Lösung 1
03 Nov	Mastertheorem	Folien, 2.3-2.6 in [DMS]	Übung 2	Lösung 2
10 Nov	Mastertheorem(ct.) und Analyse des mittleren Falls	Folien, 2.6-2.7 in [DMS]	Übung 3	Lösung 3
17 Nov	Arrays, Listen, amortisierte Laufzeitanalyse	Folien, 3.1-3.3 in [DMS]	Übung 4	Lösung 4
24 Nov	amortisierte Laufzeitanalyse, Hashing	Folien, 3.3-4.1 in [DMS]	Übung 5	Lösung 5
01 Dez	Kollisionen (Hashing), universelles Hashing	Folien, 4.1-4.4 in [DMS]	Übung 6	Lösung 6
08 Dez	Sortieren	Folien, 5.1-5.4 in [DMS]	Übung 7	Lösung 7
15 Dez	uniformSort, untere Schranken, binäre Heaps	Folien, 5.3, 5.6, 6-6.1 in [DMS]	Übung 8	Lösung 8
05 Jan	Fibonacci-Heaps	Folien, 6.2 in [DMS]	Übung 9	Lösung 9
12 Jan	Binäre Suchbäume, (a,b)-Bäume	Folien, 7-7.2 in [DMS]	Übung 10	Lösung 10
19 Jan	Graphen, Euler-Tour	Folien, 8 in [DMS]	Übung 11	Lösung 11
26 Jan	DFS und BFS	Folien, 9.1-9.2 in [DMS]	Übung 12	Lösung 12
02 Feb	Kürzeste Wege	Folien, 10.1-10.6 in [DMS]
09 Feb	Minimale Spannbäume, Union-Find	Folien, 11.1-11.4 in [DMS]
16 Feb	Hauptklausur
30 Mär	Nachklausur

Klausur

Alle notwendigen Informationen zur Klausur werden auf der Mailingliste bekannt gegeben.

Übungsblätter

Um zur Klausur zugelassen zu werden, müssen Sie mindestens 50% der möglichen Punkte auf den Übungsblättern erlangen. Es darf in festen Zweierteams abgegeben werden.

Übungsgruppen

Die Übungsgruppeneinteilung finden Sie hier.

Gruppe	Termin	Raum	Gebäude	Tutor
Gruppe 1	Mo. 10-12	024	E1.4	Jannik Kulesha
Gruppe 2	Mo. 12-14	023	E1.4	Julian Dörfler
Gruppe 3	Di. 14-16	023	E1.4	Julian Baldus
Gruppe 4	Mi. 10-12	024	E1.4	Nick Fischer
Gruppe 5	Mi. 12-14	024	E1.4	Sören Bund-Becker
Gruppe 6	Do. 8-10	024	E1.4	Robin Daumann
Gruppe 7	Fr. 10-12	029	E1.5	Philip Wellnitz
Gruppe 8	Fr. 12-14	029	E1.5	Dominik Wagner

Literatur

Hier finden Sie Literatur zu den ausgewählten Themengebieten. Das Handout zur Vorlesung wird wöchentlich erweitert. Skripts aus vergangen Semstern finden Sie hier und hier. Die folgenden Titel sind alle im Semesterapparat erhältlich.

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald and Stein, Clifford: Algorithmen - Eine Einführung, Oldenbourg 2010 [CLRS]
Dietzfelbinger, Martin; Mehlhorn, Kurt and Sanders, Peter: Algorithmen und Datenstrukturen - Die Grundwerkzeuge,Springer 2014 [DMS]
Mehlhorn, Kurt and Sanders, Peter: Algorithms and data structures - The basic toolbox, Springer 2008 [MS]