Algorithms and Data Structures

Exercise lab sessions given as a student assistant.

Topics (in German Language)

• Einführung
  • Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten, Ein-Schritt-Berechnung, Verkleinerungsprinzip
• Sortierung durch Vergleichen
  • Sortieren durch Einfügen, Entwurfsmuster: Teile-und-Herrsche, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation), Sortieren durch Auswählen, Problemklassen, Quicksort, Heaps als Datenstrukturen, Heapsort
• Sortierung durch Verteilen
  • Counting Sort, Stabiles Sortieren, Radix-Sort, Wiederholung: Listen, Keller, Schlangen, Bucket-Sort
• Prioritätswarteschlangen
  • Binomial-Heaps, Fibonacci-Heaps, amortisierte Analyse
• Selektion
  • K-kleinstes Element
• Mengen
  • Selbstorganisierende Datenstrukturen, binäre Suchbäume, Iteratoren und Navigationsstrukturen, Ausgeglichenheit, 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, Universelles Hashing
• Graphen
  • Operationen auf Graphen, Graphrepräsentationen, Breiten- und 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
  • 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
• Schwierige 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, Dependenzgesteuertes 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)