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   ThemaReferenzenHausaufgabeSonstiges
27 OktEinführung

Folien, 2.1-2.5 in [DMS]

Übung 0, Übung 1

Lösung 0, Lösung 1

03 NovMastertheorem

Folien, 2.3-2.6 in [DMS]

Übung 2
Lösung 2
10 NovMastertheorem(ct.) und Analyse des mittleren Falls

Folien, 2.6-2.7 in [DMS]

Übung 3Lösung 3
17 NovArrays, Listen, amortisierte Laufzeitanalyse

Folien, 3.1-3.3 in [DMS]

Übung 4Lösung 4
24 Novamortisierte Laufzeitanalyse, Hashing

Folien, 3.3-4.1 in [DMS]

Übung 5
Lösung 5
01 DezKollisionen (Hashing), universelles Hashing

Folien, 4.1-4.4 in [DMS]

Übung 6
Lösung 6
08 DezSortierenFolien, 5.1-5.4 in [DMS]Übung 7Lösung 7
15 DezuniformSort, untere Schranken, binäre HeapsFolien, 5.3, 5.6, 6-6.1 in [DMS]Übung 8Lösung 8
05 JanFibonacci-HeapsFolien, 6.2 in [DMS]Übung 9Lösung 9
12 JanBinäre Suchbäume, (a,b)-BäumeFolien, 7-7.2 in [DMS]Übung 10Lösung 10
19 JanGraphen, Euler-TourFolien, 8 in [DMS]Übung 11Lösung 11
26 JanDFS und BFSFolien, 9.1-9.2 in [DMS]Übung 12Lösung 12
02 FebKürzeste WegeFolien, 10.1-10.6 in [DMS]
09 FebMinimale Spannbäume, Union-FindFolien, 11.1-11.4 in [DMS]
16 FebHauptklausur
30 MärNachklausur

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    RaumGebäudeTutor
Gruppe 1Mo. 10-12024E1.4Jannik Kulesha
Gruppe 2Mo. 12-14023E1.4Julian Dörfler
Gruppe 3Di. 14-16023E1.4Julian Baldus
Gruppe 4Mi. 10-12024E1.4Nick Fischer
Gruppe 5Mi. 12-14024E1.4Sören Bund-Becker
Gruppe 6Do. 8-10

024

E1.4Robin Daumann
Gruppe 7Fr. 10-12029E1.5Philip Wellnitz
Gruppe 8Fr. 12-14029E1.5Dominik 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]