In diesem Modul besprechen wir Dynamische Arrays: eine Möglichkeit, Arrays zu verwenden, wenn im Voraus nicht bekannt ist, wie viele Elemente benötigt werden. Hier besprechen wir auch die amortisierte Analyse: eine Methode zur Bestimmung der amortisierten Kosten einer Operation über eine Folge von Operationen. Die amortisierte Analyse wird sehr häufig zur Analyse der Leistung von Algorithmen verwendet, wenn die direkte Analyse unbefriedigende Ergebnisse liefert, aber die amortisierte Analyse hilft zu zeigen, dass der Algorithmus tatsächlich effizient ist. Sie wird sowohl für die Analyse dynamischer Arrays als auch am Ende dieses Kurses für die Analyse von Splay-Bäumen verwendet.

Wir beginnen dieses Modul mit der Betrachtung von Prioritätswarteschlangen, die zur effizienten Planung von Aufträgen verwendet werden, entweder im Kontext eines Computerbetriebssystems oder im wirklichen Leben, zum Sortieren großer Dateien, was der wichtigste Baustein für jeden Big Data-Verarbeitungsalgorithmus ist, und zur effizienten Berechnung kürzester Pfade in Graphen, ein Thema, das wir in unserem nächsten Kurs behandeln werden. Aus diesem Grund gibt es für Prioritätswarteschlangen in vielen Programmiersprachen, darunter C++, Java und Python, integrierte Implementierungen. Wir werden sehen, dass diese Implementierungen auf der schönen Idee beruhen, einen kompletten Binärbaum in einem Array zu speichern, das es ermöglicht, alle Prioritätswarteschlangenmethoden in nur wenigen Zeilen Code zu implementieren. Anschließend werden wir zur Datenstruktur der disjunkten Mengen übergehen, die z.B. bei der dynamischen Graphenkonnektivität und der Bildverarbeitung verwendet wird. Wir werden wieder sehen, wie einfache und natürliche Ideen zu einer Implementierung führen, die sowohl einfach zu programmieren als auch sehr effizient ist. Nach Abschluss dieses Moduls werden Sie in der Lage sein, diese beiden Datenstrukturen von Grund auf effizient zu implementieren.

In diesem Modul lernen Sie eine sehr leistungsfähige und weit verbreitete Technik namens Hashing kennen. Zu seinen Anwendungen gehören die Implementierung von Programmiersprachen, Dateisystemen, Mustersuche, verteilte Schlüssel-Wert-Speicherung und vieles mehr. Sie lernen, wie man Datenstrukturen zum Speichern und Ändern von Objektmengen und Zuordnungen von einem Objekttyp zu einem anderen implementiert. Sie werden sehen, dass naive Implementierungen entweder riesige Mengen an Speicher verbrauchen oder langsam sind. Dann werden Sie lernen, wie man Hash-Tabellen implementiert, die linearen Speicher verbrauchen und im Durchschnitt in O(1) arbeiten! Schließlich werden Sie lernen, wie Hash-Funktionen in modernen verteilten Systemen eingesetzt werden und wie sie zur Optimierung der Speicherung von Diensten wie Dropbox, Google Drive und Yandex Disk verwendet werden!

In diesem Modul befassen wir uns mit binären Suchbäumen, einer Datenstruktur für die Suche in sich dynamisch verändernden geordneten Mengen. Sie werden viele der Schwierigkeiten bei der Bewältigung dieser Aufgabe kennenlernen und erfahren, wie wir sie überwinden können. Dazu müssen Sie die Grundstruktur von binären Suchbäumen kennen, wissen, wie man einfügt und löscht, ohne diese Struktur zu zerstören, und wie man sicherstellt, dass der Baum ausgeglichen bleibt.

In diesem Modul setzen wir das Studium der binären Suchbäume fort. Wir studieren ein paar nicht-triviale Anwendungen. Anschließend untersuchen wir die neue Art von ausgewogenen Suchbäumen - Splay Trees. Sie passen sich dynamisch an die Abfragen an und sind in vielerlei Hinsicht optimal.