Algorithms and Data Structures

Topics (in German Language)

• Algorithmen, Entwurfsmuster, Problemkomplexität, Algorithmenanalyse (O-Notation)
• Sortierung durch Teile und Herrsche, Mergesort, Quicksort, Omega- und Theta-Notation, Heaps als Datenstrukturen, Heapsort
• Sortierung durch Verteilen, Counting Sort, stabile Sortierverfahren, Radix-Sort, Bucket-Sort, Wiederholung: Listen, Keller, Schlangen
• Prioritätswarteschlangen, Realisierung mit binären Heaps, Binomial-Heaps und Fibonacci-Heaps, amortisierte Analyse
• Selektion, k-kleinstes Element
• Mengen, selbstorganisierende Datenstrukturen, binäre Suchbäume, Splay-Bäume, Rot-Schwarz-Bäume, AVL-Bäume
• Mengen von Zeichenketten, Tries, PATRICIA Tries
• Disjunkte Mengen, Union-Find Datenstruktur
• Assoziation von Objekten, Hash-Tabellen, Dynamisches Hashing (Kollisionslisten, Lineare Sondierung, Quadratische Sondierung, Doppeltes Hashing), Statisches Hashing, Familie universeller Hashfunktionen
• Graphen, Graphenrepräsentation, Breitensuche, Tiefensuche, Zusammenhangskomponenten, Kürzeste Wege, Single-Source-Shortest-Paths (Dijkstras Algorithmus, A*-Algorithmus, Bellman-Ford-Algorithmus), All-Pairs-Shortest-Paths, Transitive Hülle, Minimaler Spannbaum (Kruskals Algorithmus, Jarnik-Prim-Algorithmus), Netzwerkflüsse (Ford-Fulkerson-Algorithmus, Edmonds-Karp-Algorithmus), Bipartites Matching, Eulerkreis, Eulerweg, Hamilton-Kreis
• Suchgraphen für Spiele, Minimax-Suche, Suchraumaufbau, Alpha-Beta-Pruning zur Suchraumbeschneidung
• Dynamische Programmierung, gierige Verfahren, 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