Algorithms and Data Structures

Exercise lab sessions given as a student assistant.

Topics (in German Language)

• Einführung
  • Algorithmen, Summenbildung, Entwurfsmuster: schrittweises Abarbeiten (linearer Aufwand), Berechnung mit konstantem Aufwand, Verkleinerungsprinzip: Sortieren durch Einfügen
• Sortierung durch Vergleichen, Algorithmenanalyse
  • Sortieren durch Auswählen, Problemkomplexität, Algorithmenanalyse: asymptotische Komplexität eines Algorithmus (O-Notation), 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
• 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, Familie universeller Hashfunktionen
• 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
• 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
• 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