Week Name Description
Vorlesung Algorithmen und Datenstrukturen File Kenntnisnahme und Einhaltung der Covid-19 Infektionsschutzmaßnahmen zur Teilnahme an einer schriftlichen oder mündlichen Prüfung in Präsenz
Allgemeine Informationen File Allgemeine Informationen WS 2019/20 (Letztes Update: 10.02.2020, Bonus Nachklausur)
Vorlesungsfolien URL Wer nicht kommt, verliert! (Die ZEIT, 26.11.2015)

Wer nicht kommt, verliert! (Die ZEIT, 26.11.2015)
File 01. Vorlesung (15.10.2019): Organisatorisches
File 01. Vorlesung (15.10.2019): Druckversion
File 01. Vorlesung (15.10.2019): Sortieren I (InsertionSort) – 17.10.: kleiner Zusatz bei Factorial(k)
File 01. Vorlesung (15.10.2019): Druckversion (Sortieren I)
File 02. Vorlesung (17.10.2019): Sortieren II (MergeSort)

File 02. Vorlesung (17.10.2019): Druckversion

File 03. Vorlesung (22.10.2019): Groß-Oh-Notation

File 03. Vorlesung (22.10.2019): Druckversion

File 04. Vorlesung (24.10.2019): Laufzeitanalyse [8.11.: Folie 8: Zeilenumbruch verbessert]

File 04. Vorlesung (24.10.2019): Druckversion

File 05. Vorlesung (29.10.2019): Lösen von Rekursionsgleichungen

File 05. Vorlesung (29.10.2019): Druckversion

File 06. Vorlesung (31.10.2019): Prioritätsschlangen und HeapSort [05.11.19: ein paar ganz kleine Korrekturen]

File 06. Vorlesung (31.10.2019): Druckversion

File 07. Vorlesung (05.11.2019): Zufallsexperiment, erwartete Laufzeit von InsertionSort, Geburtstagsparadoxon [14.11.: Umfang 1. Zwischentest korrigiert]]

File 07. Vorlesung (05.11.2019): Druckversion

File 08. Vorlesung (07.11.2019): (Randomized) QuickSort

File 08. Vorlesung (07.11.2019): Druckversion

File 09. Vorlesung (12.11.2019): Untere Schranke für vergleichsbasierte Sortierverfahren, Linearzeit-Sortieralgorithmen

File 09. Vorlesung (12.11.2019): Druckversion

File 10. Vorlesung (14.11.2019): Auswahlproblem (Median)

File 10. Vorlesung (14.11.2019): Druckversion

File 11. Vorlesung (19.11.2019): Elementare Datenstrukturen (Stapel, Liste, Schlange)

File 11. Vorlesung (19.11.2019): Druckversion

File 12. Vorlesung (26.11.2019): Hashing

File 12. Vorlesung (26.11.2019): Druckversion

File 13. Vorlesung (28.11.2019): Binäre Suchbäume

File 13. Vorlesung (28.11.2019): Druckversion

File 14. Vorlesung (03.12.2019): Rot-Schwarz-Bäume

File 14. Vorlesung (03.12.2019): Druckversion

File 15. Vorlesung (05.12.2019): Augmentieren von Datenstrukturen

File 15. Vorlesung (05.12.2019): Druckversion

File 16. Vorlesung (10.12.2019): Amortisierte Analyse

File 16. Vorlesung (10.12.2019): Druckversion

File 17. Vorlesung (12.12.2019): Nächstes Paar (Teile und Herrsche)

File 17. Vorlesung (12.12.2019): Druckversion

File 18. Vorlesung (17.12.2019): Graphen, Breitensuche

File 18. Vorlesung (17.12.2019): Druckversion

File 19. Vorlesung (07.01.2020): Kürzeste Wege und Dijkstras Algorithmus

File 19. Vorlesung (07.01.2020): Druckversion

URL Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959)

Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959)
URL Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005

Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005
File 20. Vorlesung (09.01.2020): Tiefensuche und topologische Sortierung

File 20. Vorlesung (09.01.2020): Druckversion

File 21. Vorlesung (14.01.2020): Minimale Spannbäume (Jarník-Prim, Kruskal)

File 21. Vorlesung (14.01.2020): Druckversion

File 22. Vorlesung (16.01.2020): Dynamische Programmierung

File 22. Vorlesung (16.01.2020): Druckversion

File 23. Vorlesung (21.01.2020): Greedy- und Approximationsalgorithmen

File 23. Vorlesung (21.01.2020): Druckversion

File 24. Vorlesung (28.01.2020): TSP – Approximation und exakte Lösung

File 24. Vorlesung (28.01.2020): Druckversion

URL William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012)
File 25. Vorlesung (30.01.2020): Karps Algorithmus zur Berechnung leichter Kreise

File 25. Vorlesung (30.01.2020): Druckversion

URL Karps Originalartikel "A characterization of the minimum cycle mean in a digraph" (nur drei Seiten!)
File Probeklausur
Übungen File Anleitung zur Bearbeitung von Programmieraufgaben

Anleitung zur Bearbeitung von Programmieraufgaben
File 1. Präsenzübung (für 19./20.11.2019)
File 2. Präsenzübung (für 17./18.12.2019)
File 3. Präsenzübung (für 21./22.01.2020)
File 4. Präsenzübung (für 4.2./5.2.2020)
ADS-Repetitorium File Tag 1

File Tag 2

File Tag 3

File Tag 4

File Tag 5