Datenstrukturen & Algorithmen

Einführung. Algorithmenentwurf. Güte von Algorithmen.

• Begriff des Algorithmus. Rolle der Algorithmik innerhalb der Informatik
• Beispiel des Algorithmenentwurfs: Schnelle Multiplikation ganzer Zahlen, Karatsuba/Ofman 1962. Star ermitteln durch Fragen
• Einheitskostenmodell. O-Notation, Omega, Theta

Algorithmenentwurf durch einfache Induktion.

• Maximum Subarray: Naive Lösung, Präfixsumen vorberechnen, Divide-and-Conquer, linear Scan

Suchen I: Suchen. Das Auswahlproblem.

• Lineare Suche, binäre Suche, Interpolationssuche, obere und untere Schranken.
• Randomisierte Berechnung des Medians. Berechnung des Medians nach Blum.

Suchen II: Hashing.

• Prinzip des Hashing, Hashfunktionen, universelles Hashing.
• Kollisionsauflösung durch Verkettung, offene Hashverfahren, Sondieren.

Sortieren I: Elementare Verfahren. Heapsort.

• Bubblesort, Odd-Even Transposition Sort, Sortieren durch Auswahl, Sortieren durch Einfügen.
• Heapsort, implizite Repräsentation des Heap, Heapbilden in Linearzeit.

Sortieren II: Mergesort, Quicksort.

• Mergesort.
• Quicksort: Schlüsselvergleiche im besten und im schlechtesten Fall, Bewegungen im schlechtesten Fall. Zusätzlich benötigter Speicher. Schlüsselvergleiche bei randomisiertem Quicksort skizziert.

Sortieren III: Untere Schranken. Radixsort. Wörterbücher I: Elementare Konzepte.

• Untere Schranke mit Entscheidungsbaum, mittlere Höhe eines Blatts im Binärbaum. Radix-Exchange-Sort.
• Wörterbuch: Array, lineare Liste, Skipliste.

Wörterbücher II: Natürliche Suchbäume. AVL-Bäume.

• Natürlicher binärer Suchbaum (Durchlaufen, Suchen, Einfügen, Entfernen).
• AVL-Bäume: Höhe,Einfügen.

Wörterbücher III: AVL-Bäume. Amortisierte Analyse. Selbstanordnung.

• AVL-Bäume: Amortisierte Analyse des Einfügens.
• Selbstanordnung in linearen Listen: Move-to-Front mit Analyse.

Dynamische Programmierung I.

• Längste aufsteigende Teilfolge
• Editierdistanz.
• Matrixkettenmultiplikation

Dynamische Programmierung II.

• Subset sum.
• Rucksackproblem.
• FPTAS.

Algorithmenentwurf: divide-and-conquer, dynamisches Programmieren, greedy

• Matrixmultiplikation nach Strassen.
• Häufigkeitsoptimale Suchbäume, Konstruktion mit dynamischer Programmierung.
• Huffman Coding.

Selbstanordnung in Suchbäumen: Splay Trees

• Splay Trees.

Graphenalgorithmen 1.

• Reflexive, transitive Hülle.
• Traversieren: DFS, BFS.
• Zusammenhangskomponenten.
• Topologisches Sortieren.

Graphenalgorithmen 2.

• Minimaler spannender Baum: Grundlage, Greedy-Verfahren, Kruskal mit Union-Find.

Graphenalgorithmen 3.

• Minimaler spannender Baum: Minimaler Spannbaum mit dem Algorithmus von Prim/Dijkstra.
• Fibonacci-Heap (ohne Analyse).

Graphenalgorithmen 4.

• Analyse des Fibonacci Heaps.
• Kürzeste Wege: Dijkstra, Ford, Bellman.

Graphenalgorithmen 5. Kürzeste Wege

• One-to-all kürzeste Wege: Bellman; Bellman-Ford.
• All-to-all kürzeste Wege: Floyd-Warshall; Johnson.
• Heuristiken: Bidirektional, A*.

Wunderbare Welt der Algorithmen.

• Online-Algorithmen (Kuhproblem)
• Streaming-Algorithmen (majority element)
• verteilte Algorithmen (Chang's echo, two generals)
• Approximationsalgorithmen (Christofides)

Backtracking, Branch-and-Bound.

• Backtracking. Beispiele 4 Damen, SAT.
• Branch-and-Bound. Beispiele MAX SAT, Knapsack, TSP.

Flüsse in Netzen I.

• Zunehmende-Wege-Algorithmus nach Ford, Fulkerson.
• Max-Flow-Min-Cut Theorem.

Flüsse in Netzen II.

• Vergrössernde Wege durch Kapazitätenskalierung; kürzeste vergrössernde Wege nach Edmonds/Karp; nach Dinitz.
• Matching in bipartiten Graphen.

Geometrische Algorithmen I.

• Konvexe Hülle für Punktmenge in der Ebene. Jarvis, Graham, linearer Scan.
• Schnitt orthogonaler Liniensegmente.

Geometrische Algorithmen II.

• Schnitte beliebig orientierter Liniensegmente.
• Intervalle als 2-dim Punkte.

Geometrische Algorithmen III.

• Schnitt achsenparalleler Rechtecke: 2-dim range tree; Segmentbaum; tile tree/Intervallbaum; Prioritätssuchbaum.

Datenstrukturen für Externspeicher.

• B-Bäume.

Introduction and Algorithm Design.

• Introduction and Algorithm Design. Role of algorithms in computer science.
• An example for the design of algorithms: fast multiplication of integers, Karatsuba/Ofman 1962. Finding a star by asking questions.
• Uniform cost model. Growth of functions: big O notation, Omega, Theta.

Algorithm Design by Induction.

• Maximum subarray problem: naı̈ve algorithm, precomputation of prefix sums, divide and conquer, linear scan.

Searching I: Searching. Computing the Median.

• Linear search, binary search, interpolation search, upper and lower bounds.
• Randomized median computation. Blum’s algorithm for computing the median.

Searching II: Hashing.

• Hash tables, hash functions, universal hashing.
• Collision resolution by chaining, open hashing, probing.

Sorting I: Elementary Sorting Methods. Heapsort.

• Bubblesort, odd-even transposition sort, selection sort, insertion sort.
• Heapsort, implicit representation of the heap, creating a heap in linear time.

Sorting II: Mergesort, Quicksort.

• Mergesort.
• Quicksort: key comparisons: best case, worst case; Movements: worst case; Additionally required memory. Key comparisons for randomized quicksort.

Sorting III: Lower bounds. Radix sort. Dictionaries I: Basic concepts.

• Lower bound for decision-based sorting: decision tree, average height of a leaf in a binary tree. Radix Exchange Sort.
• Dictionaries: Array, linear list, skip list.

Dictionaries II: Binary Search Trees, AVL Trees.

• Binary search tree: traversal,searching, insertion, deletion.
• AVL trees: height of the tree, insertion.

Dictionaries III: AVL Trees. Amortized Analysis. Self-Organizing Linear Lists.

• AVL trees: Amortized analysis of the insert operation.
• Self-organizing linear lists, move-to-front rule (with analysis).

Dynamic Programming 1

• Longest increasing subsequence
• Edit distance.
• Matrix chain multiplication.

Dynamic Programming 2

• Subset sum.
• Knapsack problem.
• FPTAS.

Algorithm design: divide-and-conquer, dynamic programming, greedy

• Matrix multiplication by Strassen.
• Optimal search trees, construction with dynamic programming.
• Huffman Coding.

Self-organizing search trees: Splay trees

• Splay Trees.

Graph Algorithms I

• Reflexive and transitive closure.
• Graph traversal: BFS, DFS.
• Connected components.
• Topological sorting.

Graph Algorithms II

• Minimum spanning trees: introduction, greedy algorithms, Kruskal’s algorithm with union find structure.

Graph Algorithms III

• Minimum spanning trees with Prim/Dijkstra.
• Fibonacci heaps (w/o analysis)

Graph Algorithms IV

• Analysis of Fibonacci heaps
• Shortest paths from a single source. Algorithm of Dijkstra, Ford, Bellman

Graph Algorithms V. Shortest paths

• One-to-all shortest paths: Bellman; Bellman-Ford.
• All-to-all shortest paths: Floyd-Warshall; Johnson.
• Heuristics: Bidirectional, A^*.

Wunderbare Welt der Algorithmen.

• Online algorithms (lost-cow problem)
• Streaming algorithms (majority element)
• Distributed algorithms (Chang's echo, two generals)
• Approximation algorithms (Christofides)

Backtracking, Branch-and-Bound.

• Backtracking. Examples 4 Damen, SAT.
• Branch-and-Bound. Examples MAX SAT, Knapsack, TSP.

Flows in Networks I.

• Augmenting path algorithm by Ford and Fulkerson.
• Max-flow min-cut theorem.

Flows in Networks II.

• Augmenting path by capacity scaling; shortest augmenting paths (Edmonds and Karp), Dinic
• Matchings in bipartite graphs.

Geometric Algorithms I.

• Convex hull of points in the plane: Jarvis, Graham, linear scan.
• Intersection of orthogonal line segments

Geometric Algorithms II.

• Intersection of arbitrarily oriented line segments.
• Intervals as 2-dimensional points

Geometric Algorithms III.

• Intersection of axis-parallel rectangles: 2-dimensional range trees; segment trees; tile trees/interval trees, and priority trees

External Memory Structures.

• B-Trees