Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten (linearer Aufwand), Berechnung mit konstantem Aufwand,Verkleinerungsprinzip: Sortieren durch Einfügen, Sortieren durch Auswählen, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation)
Sortierung durch Teile und Herrsche, Algorithmenanalyse, Entwurfsmuster Teile-und-Herrsche: Mergesort, Quicksort, Omega- und Theta-Notation, Heaps als Datenstrukturen, Heapsort
Sortierung durch Verteilen, Counting Sort, Mehrkriteriensortierung durch stabile Sortierverfahren, Radix-Sort, Bucket-Sort, Wiederholung: Listen, Keller, Schlangen
Prioritätswarteschlangen, Realisierung mit binären Heaps, Binomial-Heaps und Fibonacci-Heaps, amortisierte Analyse
Suchgraphen für Spiele, Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung
Dynamische Programmierung, Gierige Verfahren, Optimierungsprobleme, Sequenz-Alignment (Longest-Common-Subsequence, LCS), Rucksackproblem, Planungs- und Anordnungsprobleme, Wechselgeldbestimmung, Vollständigkeit von Algorithmen
Zeichenkettenabgleich, Exakte Algorithmen (Knuth-Morris-Pratt, Boyer-Moore, Rabin-Karp, Suffix-Bäume und Felder), Approximativer Zeichenkettenabgleich durch dynamische Programmierung
Schwere Probleme, Erfüllbarkeitsproblem 3-SAT, P=NP, Clique-Problem, Problemreduktion, NP-schwere und NP-vollständige Probleme, Algorithmische Entwurfsmuster zur Behandlung NP-schwerer Probleme (DPLL, Nicht-chronologisches Backtracking), Abbildung von Sudoku auf 3-SAT, 2-SAT, Constraint-Satisfaction-Probleme, Reduktion des Backtrackings durch Heuristiken (am Beispiel der Probleme Chromatische Zahl und n-Damen), Constraint-Propagierung, Eulerkreis, Eulerweg, Hamilton-Kreis
Pruning und Subgraph-Isomorphie, Ullmanns Algorithmus, Anwendungen zur Zeichenerkennung, Erkennung von Proteinstrukturen, usw.
Approximation, Aufgabe der optimalen Lösung und Verwendung von Näherungsverfahren? Approximationsgüte gieriger Verfahren, Beispiel: Lastbalancierung