Wir definieren einen ungerichteten Graphen API und betrachten die Darstellungen der Adjazenzmatrix und der Adjazenzlisten. Wir stellen zwei klassische Algorithmen für die Suche in einem Graphen vor - die Tiefensuche und die Breitensuche. Wir betrachten auch das Problem der Berechnung von verbundenen Komponenten und schließen mit verwandten Problemen und Anwendungen.

In dieser Vorlesung untersuchen wir gerichtete Graphen. Wir beginnen mit der Deep-First-Suche und der Broadth-First-Suche in Digraphen und beschreiben Anwendungen von der Müllabfuhr bis zum Web-Crawling. Anschließend stellen wir einen auf der Tiefensuche basierenden Algorithmus zur Berechnung der topologischen Ordnung eines azyklischen Digraphen vor. Schließlich implementieren wir den Kosaraju-Sharir-Algorithmus zur Berechnung der starken Komponenten eines Digraphen.

In dieser Vorlesung untersuchen wir das Problem des minimalen Spannbaums. Wir beginnen mit der Betrachtung eines generischen gierigen Algorithmus für dieses Problem. Als nächstes betrachten wir zwei klassische Algorithmen für das Problem - Kruskal's Algorithmus und Prim's Algorithmus - und implementieren sie. Wir schließen mit einigen Anwendungen und offenen Problemen.

In dieser Vorlesung untersuchen wir Probleme mit kürzesten Wegen. Wir beginnen mit der Analyse einiger grundlegender Eigenschaften von kürzesten Wegen und einem generischen Algorithmus für dieses Problem. Wir stellen Dijkstras Algorithmus für Probleme mit kürzesten Wegen mit nichtnegativen Gewichten vor und analysieren ihn. Als nächstes betrachten wir einen noch schnelleren Algorithmus für DAGs, der auch dann funktioniert, wenn die Gewichte negativ sind. Wir schließen mit dem Bellman-Ford-Moore-Algorithmus für kantengewichtete Digraphen ohne negative Zyklen. Wir betrachten auch Anwendungen, die von inhaltsbezogenem Füllen bis zu Arbitrage reichen.

In dieser Vorlesung stellen wir die Probleme des maximalen Flusses und des minimalen Schnitts vor. Wir beginnen mit dem Ford-Fulkerson-Algorithmus. Um seine Korrektheit zu analysieren, stellen wir das Maxflow-Mincut-Theorem auf. Als Nächstes betrachten wir eine effiziente Implementierung des Ford-Fulkerson-Algorithmus, die die Regel des kürzesten augmentierenden Pfades verwendet. Schließlich betrachten wir Anwendungen, darunter Bipartite Matching und Baseball-Elimination.

In dieser Vorlesung betrachten wir spezialisierte Sortieralgorithmen für Strings und verwandte Objekte. Wir beginnen mit einem Unterprogramm zum Sortieren ganzer Zahlen in einem kleinen Bereich. Dann betrachten wir zwei klassische Radix-Sortieralgorithmen - LSD und MSD Radix-Sorts. Als nächstes betrachten wir eine besonders effiziente Variante, eine Mischung aus MSD-Radixsortierung und Quicksort, die als 3-Wege-Radix-Quicksort bekannt ist. Wir schließen mit Suffixsortierung und verwandten Anwendungen.

In dieser Vorlesung betrachten wir spezialisierte Algorithmen für Symboltabellen mit String-Schlüsseln. Unser Ziel ist eine Datenstruktur, die so schnell wie Hashing und noch flexibler als binäre Suchbäume ist. Wir beginnen mit Multiway-Versuchen; als nächstes betrachten wir ternäre Suchversuche. Schließlich betrachten wir zeichenbasierte Operationen, einschließlich Präfixübereinstimmung und längstes Präfix, sowie verwandte Anwendungen.

In dieser Vorlesung betrachten wir Algorithmen für die Suche nach einer Teilzeichenkette in einem Textstück. Wir beginnen mit einem Brute-Force-Algorithmus, dessen Laufzeit im schlimmsten Fall quadratisch ist. Als nächstes betrachten wir den genialen Knuth-Morris-Pratt-Algorithmus, dessen Laufzeit im schlimmsten Fall garantiert linear ist. Dann stellen wir den Boyer-Moore-Algorithmus vor, dessen Laufzeit bei typischen Eingaben sublinear ist. Schließlich betrachten wir den Rabin-Karp-Fingerprint-Algorithmus, der auf clevere Weise Hashing verwendet, um die Teilstringsuche und verwandte Probleme zu lösen.

Ein regulärer Ausdruck ist eine Methode zur Angabe einer Menge von Zeichenketten. Unser Thema in dieser Vorlesung ist der berühmte grep-Algorithmus, der feststellt, ob ein bestimmter Text eine beliebige Teilzeichenkette aus der Menge enthält. Wir untersuchen eine effiziente Implementierung, die unsere Digraphen-Erreichbarkeitsimplementierung aus Woche 1 nutzt.

Wir untersuchen und implementieren mehrere klassische Datenkompressionsverfahren, darunter Run-Length Coding, Huffman-Kompression und LZW-Kompression. Wir entwickeln effiziente Implementierungen von Grund auf, indem wir eine Java-Bibliothek für die Manipulation von Binärdaten verwenden, die wir zu diesem Zweck entwickelt haben und die auf Implementierungen von Prioritätswarteschlangen und Symboltabellen aus früheren Vorlesungen basiert.

Unsere Vorlesungen in dieser Woche konzentrieren sich auf die Idee von Problemlösungsmodellen wie Maxflow und kürzester Weg, wobei ein neues Problem als Instanz eines dieser Probleme formuliert und dann mit einem klassischen und effizienten Algorithmus gelöst werden kann. Zum Abschluss des Kurses beschreiben wir das klassische ungelöste Problem aus der theoretischen Informatik, das sich auf das Konzept der Effizienz von Algorithmen konzentriert und uns bei der Suche nach effizienten Lösungen für schwierige Probleme leitet.

Die Quintessenz des Problemlösungsmodells ist die lineare Programmierung, und die Simplex-Methode zu ihrer Lösung ist einer der am häufigsten verwendeten Algorithmen. In dieser Vorlesung geben wir einen Überblick über dieses zentrale Thema des Operations Research und beschreiben seine Beziehung zu den Algorithmen, die wir betrachtet haben.

Gibt es ein universelles Problemlösungsmodell, auf das sich alle Probleme, die wir lösen möchten, reduzieren lassen und für das wir einen effizienten Algorithmus kennen? Sie werden vielleicht überrascht sein, dass wir die Antwort auf diese Frage nicht kennen. In dieser Vorlesung führen wir die Komplexitätsklassen P, NP und NP-vollständig ein, stellen die berühmte P = NP-Frage und betrachten die Implikationen im Zusammenhang mit den Algorithmen, die wir in diesem Kurs behandelt haben.