Section: Vorlesungsfolien | WS24: Algorithmen und Datenstrukturen

Section outline

Für die meisten (aber nicht alle!) Vorlesungen wird es Videos geben, die man sich spätestens zum jeweiligen Vorlesungstermin anschauen kann.
In der Tabelle unten liefert ein Klick aufs jeweilige Datum die Kurz-/Druckversion der Folien; ein Klick aufs Thema die Langversion.

Datum	Thema	Videos (alt!)	Literatur
15.10.2024	Organisation und Einführung
15.10.2024	Inkrementell sortieren (InsertionSort)	Inkrementeller Algorithmus (24') – Fakultät (11')
17.10.2024	Teilen und herrschen (MergeSort)	Pseudocode + Beispiel (18') – Korrektheit (16')
22.10.2024	Laufzeitanalyse, Groß-Oh-Notation	Vergleich InsertionSort und MergeSort (18') – Klassifikationsschema für Funktionen (12')
24.10.2024	Laufzeitanalyse am Beispiel "Maximales Teilfeld"	Kubischer Algorithmus für MaxSum (15') – Schnellere Algorithmen für MaxSum (22')
29.10.2024	Rekursionsgleichungen lösen	Substitutionsmethode (10') – Rekursionsbaummethode (10') – Meistermethode (10')
31.10.2024	Prioritätsschlangen, Heaps, HeapSort	Prioritätsschlange, MaxHeapify, BuildMaxHeap (23') – HeapSort (12')
05.11.2024	Zufallsexperimente	Gedankenexperiment (17') – Average-Case-Analyse von InsertionSort (11') – Geburtstagsparadoxon & Bonustrack (7')
07.11.2024	QuickSort und RandomizedQuickSort	(Deterministisches) QuickSort (16') – Erwartete Laufzeit von Randomized QuickSort (19')
12.11.2024	Sortieren in Linearzeit	Untere Schranke (13') – CountingSort (10') – RadixSort (7') – BucketSort (14')
14.11.2024	1. Zwischentest
19.11.2024	Das Auswahlproblem	Randomisiertes Select (23') – Deterministisches Select (15')
21.11.2024	Abstrakter Datentyp: Dynamische Menge (8') – Stapel, Schlange, Liste (10') – Von Pseudocode zu Javacode (8')
26.11.2024	Hashing	direkte Adressierung und Hashing mit Verkettung (22') – gute Hashfunktionen und Hashing mit offener Adressierung (23')
28.11.2024	Binäre Suchbäume	Vorarbeiten und Traversierung (21') – Methoden (15')
03.12.2024	Rot-Schwarz-Bäume	Logarithmische Höhe (16') – Einfüge-Operation (16')
05.12.2024	fällt aus!	–
10.12.2024	Datenstrukturen augmentieren	Augmentieren – komplett (28')
12.12.2024	2. Zwischentest	Anmelden nicht vergessen!
17.12.2024	Amortisierte Analyse	Aggregationsmethode (9') – Buchhaltermethode (6') – Potentialmethode (9')
19.12.2024	Nächstes Paar	–
07.01.2025	Graphen: Repräsentation und Breitensuche	Beispiele und Repräsentation (16') – Breitensuche (23')
09.01.2025	Kürzeste Wege und Dijkstras Algorithmus	Dijkstras Algorithmus (22') – Kürzeste Wege und T9 (7')	Dijkstras Originalartikel (3 Seiten, Num. Math., 1959) Das Geheimnis des kürzesten Weges (Gritzmann & Brandenberg, 2005)
14.01.2025	Tiefensuche und topologische Sortierung	Tiefensuche (Beispiel, Pseudocode, Eigenschaften) (22') – Topologische Sortierung (Anwendung, Korrektheit) (12')
16.01.2025	3. Zwischentest	Anmelden nicht vergessen!
21.01.2025	Minimale Spannbäume	Generischer Algorithmus und Korrektheit (13') – Algorithmen von Jarník–Prim und von Kruskal (18')
23.01.2025	Dynamisches Programmieren	Stabzerlegung (22') – Längste Wege (8')
28.01.2025	Greedy-Algorithmen	Ein einfaches Problem der Ablaufplanung (15') – Ein gewichtetes Problem der Ablaufplanung (14')
30.01.2025	Problem des Handlungsreisenden	Vorlesungsmitschnitt vom WS 2021, leider ohne die ersten 5' (59')	In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Cook, 2012)
04.02.2025	Keine Vorlesung! (wegen GADS-Klausur)
06.02.2025	Leichte Kreise per Dynamischer Programmierung [Folie 2 am 6.2., 15 Uhr aktualisiert.]	Kein Video :-(	Karps Originalartikel (3 Seiten, Discrete Math., 1978)
12.02.2025	1. Klausur	Bitte stimmen Sie bei der Umfrage* hier im Kursraum mit "ja" ab, wenn Sie teilnehmen wollen.*
14.04.2025	2. Klausur	Anmelden auf WueStudy (ab 15.03. oder 01.04.2024) nicht vergessen!