In diesem Modul lernen Sie, dass Programme, die auf effizienten Algorithmen basieren, das gleiche Problem milliardenfach schneller lösen können als Programme, die auf naiven Algorithmen basieren. Sie werden lernen, wie Sie die Laufzeit und den Speicherbedarf eines Algorithmus abschätzen können, ohne ihn überhaupt zu implementieren. Mit diesem Wissen werden Sie in der Lage sein, verschiedene Algorithmen zu vergleichen, die effizientesten auszuwählen und sie schließlich als unsere Programmieraufgaben zu implementieren!

In diesem Modul lernen Sie eine scheinbar naive, aber leistungsstarke Klasse von Algorithmen kennen, die gierigen Algorithmen. Nachdem Sie die Schlüsselidee hinter den gierigen Algorithmen kennengelernt haben, werden Sie vielleicht das Gefühl haben, dass sie das algorithmische Schweizer Taschenmesser darstellen, mit dem Sie fast alle Programmieraufgaben in diesem Kurs lösen können. Aber seien Sie gewarnt: Abgesehen von einigen Ausnahmen, die wir behandeln werden, funktioniert diese intuitive Idee in der Praxis nur selten! Aus diesem Grund ist es wichtig zu beweisen, dass ein gieriger Algorithmus immer eine optimale Lösung liefert, bevor Sie diesen Algorithmus verwenden. Am Ende dieses Moduls werden wir Ihre Intuition und Ihre Vorliebe für gierige Algorithmen testen, indem wir Ihnen mehrere Programmieraufgaben stellen.

In diesem Modul lernen Sie eine leistungsstarke algorithmische Technik kennen, die Divide et Conquer genannt wird. Auf der Grundlage dieser Technik werden Sie sehen, wie Sie riesige Datenbanken millionenfach schneller durchsuchen können als mit einer naiven linearen Suche. Sie werden sogar erfahren, dass die Standardmethode zum Multiplizieren von Zahlen (die Sie in der Grundschule gelernt haben) bei weitem nicht die schnellste ist! Anschließend werden wir die Divide-and-Conquer-Technik anwenden, um zwei effiziente Algorithmen (Merge Sort und Quick Sort) für die Sortierung großer Listen zu entwerfen, ein Problem, das in der Praxis viele Anwendungen findet. Schließlich werden wir zeigen, dass diese beiden Algorithmen optimal sind, d.h. kein Algorithmus kann schneller sortieren!

In diesem letzten Modul des Kurses lernen Sie die leistungsstarke algorithmische Technik zur Lösung vieler Optimierungsprobleme kennen, die Dynamische Programmierung. Es hat sich herausgestellt, dass die dynamische Programmierung viele Probleme lösen kann, die sich allen Versuchen entziehen, sie mit einer gierigen oder einer Divide-and-Conquer-Strategie zu lösen. In der Praxis gibt es unzählige Anwendungen der dynamischen Programmierung: von der Maximierung der Werbeeinnahmen eines Fernsehsenders über die Suche nach ähnlichen Internetseiten bis hin zur Gensuche (das Problem, bei dem Biologen die minimale Anzahl von Mutationen finden müssen, um ein Gen in ein anderes zu verwandeln). Sie werden erfahren, wie dieselbe Idee dabei hilft, automatisch Rechtschreibkorrekturen vorzunehmen und die Unterschiede zwischen zwei Versionen desselben Textes aufzuzeigen.

In diesem Modul üben wir weiterhin die Implementierung von Lösungen für die dynamische Programmierung.