Wir veranschaulichen unseren grundlegenden Ansatz zur Entwicklung und Analyse von Algorithmen anhand des Problems der dynamischen Konnektivität. Wir stellen den Datentyp union-find vor und betrachten verschiedene Implementierungen (quick find, quick union, weighted quick union und weighted quick union mit Pfadkompression). Schließlich wenden wir den Datentyp union-find auf das Perkolationsproblem aus der physikalischen Chemie an.

Die Grundlage unseres Ansatzes zur Analyse der Leistung von Algorithmen ist die wissenschaftliche Methode. Wir beginnen mit der Durchführung von Computerexperimenten, um die Laufzeiten unserer Programme zu messen. Wir verwenden diese Messungen, um Hypothesen über die Leistung zu entwickeln. Als nächstes erstellen wir mathematische Modelle, um ihr Verhalten zu erklären. Schließlich analysieren wir die Speichernutzung unserer Java-Programme.

Wir betrachten zwei grundlegende Datentypen für die Speicherung von Sammlungen von Objekten: den Stapel und die Warteschlange. Wir implementieren beide entweder mit einer einfach verketteten Liste oder einem Array mit Größenänderung. Wir stellen zwei fortschrittliche Java-Funktionen vor - Generics und Iteratoren - die den Client-Code vereinfachen. Schließlich betrachten wir verschiedene Anwendungen von Stapeln und Warteschlangen, die vom Parsen arithmetischer Ausdrücke bis zur Simulation von Warteschlangensystemen reichen.

Wir stellen das Sortierproblem und die Schnittstelle Comparable von Java vor. Wir untersuchen zwei elementare Sortiermethoden (Auswahlsortierung und Einfügesortierung) und eine Variation einer dieser Methoden (Shellsort). Wir betrachten auch zwei Algorithmen zum gleichmäßigen Mischen eines Arrays. Wir schließen mit einer Anwendung des Sortierens zur Berechnung der konvexen Hülle über den Graham-Scan-Algorithmus.

Wir untersuchen den Mergesort-Algorithmus und zeigen, dass er garantiert jedes Array mit n Elementen mit höchstens n lg n Vergleichen sortiert. Wir betrachten auch eine nicht-rekursive Bottom-Up-Version. Wir beweisen, dass jeder auf Vergleichen basierende Sortieralgorithmus im schlimmsten Fall mindestens n lg n Vergleiche durchführen muss. Wir diskutieren die Verwendung verschiedener Ordnungen für die Objekte, die wir sortieren, und das damit verbundene Konzept der Stabilität.

Wir führen den randomisierten Quicksort-Algorithmus ein, implementieren ihn und analysieren seine Leistung. Wir betrachten auch randomized quickselect, eine Variante von quicksort, die das k-te kleinste Element in linearer Zeit findet. Schließlich betrachten wir 3-Wege-Quicksort, eine Variante von Quicksort, die besonders gut bei Vorhandensein von doppelten Schlüsseln funktioniert.

Wir stellen den Datentyp Prioritätswarteschlange und eine effiziente Implementierung unter Verwendung der binären Heap-Datenstruktur vor. Diese Implementierung führt auch zu einem effizienten Sortieralgorithmus, der als Heapsort bekannt ist. Wir schließen mit einer Anwendung von Prioritätswarteschlangen, bei der wir die Bewegung von n Teilchen simulieren, die den Gesetzen der elastischen Kollision unterliegen.

Wir definieren eine API für Symboltabellen (auch bekannt als assoziative Arrays, Maps oder Dictionaries) und beschreiben zwei elementare Implementierungen mit einem sortierten Array (binäre Suche) und einer ungeordneten Liste (sequentielle Suche). Wenn die Schlüssel vergleichbar sind, definieren wir eine erweiterte API, die die zusätzlichen Methoden min, max, floor, ceiling, rank und select enthält. Um eine effiziente Implementierung dieser API zu entwickeln, untersuchen wir die binäre Suchbaum-Datenstruktur und analysieren ihre Leistung.

In dieser Vorlesung ist es unser Ziel, eine Symboltabelle mit garantierter logarithmischer Leistung für Suchen und Einfügen (und viele andere Operationen) zu entwickeln. Wir beginnen mit 2-3 Bäumen, die leicht zu analysieren, aber schwer zu implementieren sind. Als nächstes betrachten wir rot-schwarze binäre Suchbäume, die wir als eine neuartige Möglichkeit ansehen, 2-3 Bäume als binäre Suchbäume zu implementieren. Schließlich stellen wir B-Bäume vor, eine Verallgemeinerung von 2-3 Bäumen, die häufig zur Implementierung von Dateisystemen verwendet werden.

Wir beginnen mit der 1d- und 2d-Bereichssuche, bei der das Ziel darin besteht, alle Punkte in einem bestimmten 1d- oder 2d-Intervall zu finden. Um dies zu erreichen, betrachten wir kd-Bäume, eine natürliche Verallgemeinerung von BSTs, wenn die Schlüssel Punkte in der Ebene (oder höheren Dimensionen) sind. Wir betrachten auch Schnittpunktprobleme, bei denen das Ziel darin besteht, alle Schnittpunkte zwischen einer Menge von Liniensegmenten oder Rechtecken zu finden.

Wir beginnen mit einer Beschreibung der wünschenswerten Eigenschaften von Hash-Funktionen und ihrer Implementierung in Java, einschließlich eines grundlegenden Grundsatzes, der als einheitliche Hash-Annahme bekannt ist und die Grundlage für den potenziellen Erfolg einer Hash-Anwendung bildet. Anschließend betrachten wir zwei Strategien für die Implementierung von Hash-Tabellen - getrennte Verkettung und lineares Probing. Beide Strategien liefern eine zeitlich konstante Leistung für das Suchen und Einfügen unter der Annahme eines einheitlichen Hashings.

Wir betrachten verschiedene Anwendungen von Symboltabellen, darunter Sets, Wörterbuch-Clients, Indexierungs-Clients und spärliche Vektoren.