In diesem Modul lernen die Teilnehmer die Grundlagen von Datenstrukturen kennen, die Daten organisieren, um bestimmte Arten von Operationen schneller durchzuführen. Das Modul beginnt mit einer allgemeinen Einführung in Datenstrukturen und spricht über einige einfache Datenstrukturen wie First-in-First-out-Warteschlangen und Last-in-First-out-Stapel. Als nächstes stellen wir die Heap-Datenstruktur und die grundlegenden Eigenschaften von Heaps vor. Es folgen Algorithmen zum Einfügen, Löschen und Finden des minimalen Elements eines Heaps sowie deren Zeitkomplexität. Schließlich untersuchen wir die Datenstruktur der Prioritätswarteschlange und stellen einige Anwendungen vor.

Wir werden die Algorithmen quicksort und quickselect zur effizienten Sortierung und Auswahl des k-ten kleinsten Elements in einem Array durchgehen. Dies ist auch eine Einführung in die Rolle der Randomisierung bei der Entwicklung von Algorithmen. Als nächstes werden wir uns mit Hashtabellen beschäftigen: eine äußerst nützliche Datenstruktur, die eine effiziente Suche und Abfrage von großen Datenmengen ermöglicht. Wir lernen die grundlegenden Prinzipien von Hash-Tabellen und Operationen mit Hash-Tabellen kennen.

In diesem Modul lernen wir die randomisierte Pivot-Auswahl für Quicksort und Quickselect kennen. Wir lernen, wie wir die Komplexität der randomisierten Quicksort- und Quickselect-Algorithmen analysieren können. Wir lernen Open Address Hashing kennen: eine Technik, die das Design von Hashtables vereinfacht. Als nächstes werden wir den Entwurf von Hash-Funktionen und deren Analyse untersuchen. Schließlich stellen wir Bloom-Filter vor und analysieren sie, die in verschiedenen Anwendungen wie der Abfrage von Streaming-Daten und der Zählung eingesetzt werden.