Skip to main content
Side panel
More
English (en)
Català (ca)
Deutsch (de)
Deutsch (du) (de_du)
English (en)
Español - Internacional (es)
Français (fr)
Italiano (it)
Português - Portugal (pt)
Svenska (sv)
Türkçe (tr)
Русский (ru)
العربية (ar)
You are currently using guest access
Log in
Open course index
Home
Wintersemester 2021/2022
Grundständige Studiengänge (Bachelor, ...)
WS21_ADS
Vorlesungsfolien
09. Vorlesung (16.11.2021): Druckversion
09. Vorlesung (16.11.2021): Druckversion
Click
ads-ws21-vl09-sortieren-in-linearzeit-druckversion.pdf
link to view the file.
◄ 09. Vorlesung (16.11.2021): Sortieren in Linearzeit
Jump to...
Jump to...
Allgemeine Informationen WS 2021/22
00. Vorlesung (19.10.2021): Organisatorisches
00. Vorlesung (19.10.2021): Druckversion
01. Vorlesung (19.10.2021): Sortieren I
01. Vorlesung (19.10.2021): Druckversion
02. Vorlesung (21.10.2021): Sortieren II (MergeSort)
02. Vorlesung (21.10.2021): Druckversion
03. Vorlesung (26.10.2021): Laufzeitanalyse
03. Vorlesung (26.10.2021): Druckversion
04. Vorlesung (28.10.2021): Laufzeitanalyse am Beispiel
04. Vorlesung (28.10.2021): Druckversion
05. Vorlesung (02.11.2021): Rekursionsgleichungen lösen
05. Vorlesung (02.11.2021): Druckversion
06. Vorlesung (04.11.2021): Prioritätsschlangen, Heaps und HeapSort
06. Vorlesung (04.11.2021): Druckversion
07. Vorlesung (09.11.2021): Zufallsexperimente [09.11., 12:10: kleine Änderungen, besonders rot-grün vermieden]
07. Vorlesung (09.11.2021): Druckversion
08. Vorlesung (11.11.2021): QuickSort und RandomizedQuickSort
08. Vorlesung (11.11.2021): Druckversion
09. Vorlesung (16.11.2021): Sortieren in Linearzeit
10. Vorlesung (23.11.2021): Das Auswahlproblem
10. Vorlesung (23.11.2021): Druckversion
11. Vorlesung (25.11.2021): Elementare Datenstrukturen
11. Vorlesung (25.11.2021): Druckversion
12. Vorlesung (30.11.2021): Hashing [kleine Änderungen am 30.11., z.B. alle Tabellen v.u.n.o. nummeriert]
12. Vorlesung (30.11.2021): Druckversion
13. Vorlesung (02.12.2021): Binäre Suchbäume
13. Vorlesung (02.12.2021): Druckversion
14. Vorlesung (07.12.2021): Rot-Schwarz-Bäume
14. Vorlesung (07.12.2021): Druckversion
15. Vorlesung (09.12.2021): Augmentieren von Datenstrukturen [Monat des 2. Zwischentests von Nov. auf Dez. korrigiert]
15. Vorlesung (09.12.2021): Druckversion
16. Vorlesung (14.12.2022): Amortisierte Analyse
16. Vorlesung (14.12.2022): Druckversion
17. Vorlesung (21.12.2021): Nächstes Paar
17. Vorlesung (21.12.2021): Druckversion
18. Vorlesung (11.01.2022): Graphen: Repräsentation und Breitensuche
18. Vorlesung (11.01.2022): Druckversion
19. Vorlesung (13.01.2022): Kürzeste Wege und Dijkstras Algorithmus
19. Vorlesung (13.01.2022): Druckversion
Dijkstras Originalartikel (Numerische Mathematik 1, S. 296–271, 1959)
Das Geheimnis des kürzesten Wegs. Ein mathematisches Abenteuer. Peter Gritzmann und René Brandenberg: Springer-Verlag, 3. Auflage, 2005
20. Vorlesung (18.01.2022): Tiefensuche und topologische Sortierung
20. Vorlesung (18.01.2022): Druckversion
21. Vorlesung (25.01.2022): Minimale Spannbäume [25.1. – historische Notiz: auch Dijkstra hat den Alg. von Jarník-Prim entdeckt – 1959 :-) ]
21. Vorlesung (25.01.2022): Druckversion
22. Vorlesung (27.01.2022): Dynamisches Programmieren
22. Vorlesung (27.01.2022): Druckversion
23. Vorlesung (31.01.2022): Greedyalgorithmen [01.02., 12:00 Uhr – winzige Änderung: e_0 -> e[0]
23. Vorlesung (31.01.2022): Druckversion
24. Vorlesung (03.02.2022): Das Problem der Handlungsreisenden (TSP: Approximation & DP)
24. Vorlesung (03.02.2022): Druckversion
William Cook: "In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation" (Princeton University Press; 2012) – Schon die Einleitung ist sehr lesenswert!
25. Vorlesung (08.02.2022): Leichte Kreise (DP) [nach der VL: letzte Folie: k=1 to n statt n-1]
25. Vorlesung (08.02.2022): Druckversion
Teilnahme am 1. Zwischentest am 18.11
1. Zwischentest
2. Zwischentest
3. Zwischentest
Latex-Template
Anleitung zur Bearbeitung von Programmieraufgaben
Probeklausur
0. Übungsblatt
1. Übungsblatt
2. Übungsblatt
3. Übungsblatt
4. Übungsblatt
5. Übungsblatt
6. Übungsblatt
7. Übungsblatt
8. Übungsblatt
9. Übungsblatt
10. Übungsblatt
Feedback Repetitorium
Animationen
Quiz 0 (Konvergenz, Pseudocode)
Quiz 1 (InsertionSort, Schleifeninvariante)
Quiz 2 (Laufzeitklassifikation, Merge)
Quiz 3 (InsertionSort, MergeSort, Laufzeitklassifikation)
Quiz 4 (Laufzeiten, Heaps)
Quiz 5 (Meistermethode, Heaps)
Quiz 6 (Partition, RadixSort, Stabilität)
Quiz 7 (Partition, RadixSort, InSitu)
Quiz 8 (Hashing, Binärbäume)
Quiz 9 (Hashing, Binäre Suche)
Quiz 10 (Rot-Schwarz Bäume)
10. Vorlesung (23.11.2021): Das Auswahlproblem ►