- 04.07.2014: Das elfte und letzte Aufgabenblatt ist online.
- 13.06.2014: Das zehnte Aufgabenblatt ist online.
- 06.06.2014: Das neunte Aufgabenblatt ist online.
- 30.05.2014: Das achte Aufgabenblatt ist online.
- 23.05.2014: Das siebte Aufgabenblatt ist online.
- 16.05.2014: Das sechste Aufgabenblatt ist online.
- 09.05.2014: Das fünfte Aufgabenblatt ist online.
- 02.05.2014: Das vierte Aufgabenblatt ist online.
- 25.04.2014: Das dritte Aufgabenblatt ist online.
- 18.04.2014: Das zweite Aufgabenblatt ist online.
- 01.04.2014: Das erste Aufgabenblatt ist online.
- 12.02.2014: Die Website ist online. Die erste Vorlesung
findet statt am 15.04.2014.
Die Übungszettel werden ausschließlich online erscheinen
und zwar hier auf dieser Seite.
- Self-adjusting data structures
- Splaybäume und ihre Eigenschaften
- statische und dynamische Optimalität
- untere Schranken
- Tangobäume
- Transdichotome Modelle
- van-Emde-Boas Bäume
- Fusion trees
- Integer Sorting
- Hashing
- Cuckoo-Hashing mit Analyse
- Tabulation Hashing
- Dynamisches Hashing
- Bloomier Filters
- Persistente Datenstrukturen
- schwache und starke Persistenz. Die Transformation von
Driscoll-Sarnak-Sleator-Tarjan
- Dynamische Datenstrukturen
- Link-cut trees
- Dynamische Graphen
- Probleme auf Bäumen
- lca problem
- level-ancestor problem
- geometrische Datenstrukturen
- geometrische Bereichssuche
- Filtering search
- Fractional Cascading
- Untere Schranken
- Cell-probe model
- timestamping
- Communication complexity und round elimination
- Dienstag, den 15. 04. 2014
- Administrativa
- Einleitung
- Splaybäume
- Die Splay-Operation:
zick, zick-zick und zick-zack
- Einfügen, Löschen und Suchen
- Amortisierte Analyse der Laufzeit
- Freitag, den 18. 04. 2014 (Karfreitag)
- Dienstag, den 22. 04. 2014
- Abschluss der Analyse von Splaybäumen: Access-Lemma,
Balance Theorem, statische Optimalität
- Freitag, den 25. 04. 2014
- dynamische Optimalität; Modell, Definitionen,
Wettbewerbsfähigkeit; Dynamische Optimalitätsvermutung
- Die Wechselschranke (Interleave Bound)
- Tangobäume: Idee
- Dienstag, den 29. 04. 2014
- Freitag, den 02. 05. 2014
- Dienstag, den 06. 05. 2014
- van-Emde-Boas Bäume
- Anfang Fusion-Trees
- Freitag, den 09. 05. 2014
- Dienstag, den 13. 05. 2014
- Fusion-Trees: Fortsetzung
- Freitag, den 16. 05. 2014
- keine Vorlesung wegen Euler-Vorlesung; nachgeholt am
Montag.
- Montag, den 19. 05. 2014
- Fusion-Trees: Ende
- Cuckoo-Hashing: Algorithmus und Kuckusgraph
- Dienstag, den 20. 05. 2014
- Cuckoo-Hashing: Kompressionsargument und Analyse
- Freitag, den 23. 05. 2014
- Cuckoo-Hashing: Abschluss
- Integer Sorting: Strategie und Bereichsreduktion
- Dienstag, den 27. 05. 2014
- Integer Sorting: gepacktes Sortieren
- Freitag, den 30. 05. 2014
- Integer Sorting: Abschluss
- Universelles Hashing
- Dienstag, den 03. 06. 2014
- Statisches und Dynamisches Perfektes Hashing
- Freitag, den 06. 06. 2014
- Amortisierte Analyse von Dynamischem Perfektem Hashing
- Tabulation Hashing: Definition und Eigenschaften
- Dienstag, den 10. 06. 2014
- Analyse von Tabulation Hashing für wenige
Schlüssel: Schälbarkeit
- Freitag, den 13. 06. 2014
- Analyse von Tabulation Hashing für wenige
Schlüssel: Abschluss
- Persistente Datenstrukturen: Partielle Persistenz
- Dienstag, den 17. 06. 2014
- Persistente Datenstrukturen: Volle Persistenz
- Einführung Fractional Cascading
- Freitag, den 20. 06. 2014
- Dienstag, den 24. 06. 2014
- Freitag, den 27. 06. 2014
- Dienstag, den 01. 07. 2014
- Fractional Cascading: inkrementeller Aufbau und Analyse
- Freitag, den 04. 07. 2014
- Dynamisierung von Datenstrukturen für zerlegbare
Suchprobleme: Bentley-Saxe Transformation
- Dienstag, den 08. 07. 2014
- Dynamisierung von Datenstrukturen für zerlegbare
Suchprobleme: Deamortisierung und Löschen
- Freitag, den 11. 07. 2014
- Dienstag, den 15. 07. 2014
- Probleme auf Bäumen: level ancestors
- Untere Schranken: Zellensondierungsmodell
- Freitag, den 18. 07. 2014
- Untere Schranken: Zellensondierungsmodell und Letzter?-Spiel
- Schluss
- Dienstag, den 22. 07. 2014
- Montag, den 06. 10. 2014
Voraussetzungen
- Kenntnis grundlegender diskreter Mathematik und
Wahrscheinlichkeitstheorie
- Schein in "Höhere Algorithmik", "ALP 3" oder
vergleichbarer Veranstaltung
- Vordiplom in Informatik, Mathematik o.ä. oder vier erfolgreiche
Semester im BSc-Studiengang.
Ähnliche Vorlesungen
Für den Scheinerhalt muss man
- regelmäßig an dem Tutorium teilnehmen
- mindestens 60% der Punkte auf den Übungszetteln erreichen und
mindestens zweimal im Tutorium vorrechnen; und
- die Abschlussprüfung bestehen.
Im Bachelor- und Masterstudiengang sind die erfolgreiche Teilnahme am
Übungsbetrieb und das Bestehen der Abschlussprüfung
unabhängige Leistungen.
Die Scheine sind benotet. Die Note beruht nur auf dem Ergebnis
der Abschlussprüfung.
Die genauen Prüfungsmodalitäten werden noch bekannt gegeben.
Die Vorlesung findet
Dienstags von 08–10 Uhr im SR 053 und
Freitags von 12–14 Uhr im SR 055 statt, die Übung
Montags von 10–12 im SR 046.
Es wird jede Woche ein neuer Übungszettel veröffentlicht. Die
Übungszettel werden ausschließlich online erscheinen. Die normale Bearbeitungszeit ist von
Freitag bis zum Dienstag 11 Tage später.
| Nr. | Ausgabe | Abgabe |
pdf | tex | Bemerkungen |
| 1 |
01.04.2014 |
22.04.2014 |
|
|
|
| 2 |
18.04.2014 |
29.04.2014 |
|
|
|
| 3 |
25.04.2014 |
06.05.2014 |
|
|
|
| 4 |
02.05.2014 |
13.05.2014 |
|
|
|
| 5 |
09.05.2014 |
20.05.2014 |
|
|
|
| 6 |
09.05.2014 |
20.05.2014 |
|
|
|
| 7 |
23.05.2014 |
03.06.2014 |
|
|
|
| 8 |
30.05.2014 |
10.06.2014 |
|
|
|
| 9 |
06.05.2014 |
17.06.2014 |
|
|
|
| 10 |
13.06.2014 |
01.07.2014 |
|
|
Fractional Cascading I
Fractional Cascading II
|
| 11 |
04.07.2014 |
11.07.2014 |
|
|
letztes Aufgabenblatt
Aufgabe 2 wurde aktualisiert (08.07).
|
Im Anschluss an die Veranstaltung können
Studien–, Bachelor–, Examens–, Diplom– und
Masterarbeiten vergeben werden.