Slides and Exercises
Day 1: Graph Theory
Day 2: Probability Theory
Day 3: Randomized Algorithms
Day 4: Max-Flow-Min-Cut
Day 5: Geometrical Algorithms
This page contains the slides weekly exercise and other useful materials for the course Algorithms & Probability. Since I will also be holding a PVW in this subject the respective materials can also be found here. They will be very similar to the ones of the weekly sessions but mainly in English.
Day 1: Graph Theory
Day 2: Probability Theory
Day 3: Randomized Algorithms
Day 4: Max-Flow-Min-Cut
Day 5: Geometrical Algorithms
Connectedness, Cut-Vertices/-Edges, DFS with Low Values
Hamiltonian Cycles, Dirac, TSP (2-Approximation)
Augmenting Path, Frobenius, TSP (1.5-Approximation)
Greedy Algorithm, Heuristic, Brooks, 3-Colorable Graphs
Notation, Addition-/Multiplication Rule, Inclusion-Exclusion Principle, Union Bound, Combinatorics, Conditional Probability, Law of total Probability
Bayes Theorem, Independence, Random Variables, PDF/CDF, Expected Value, Linearity of Expectation, Indicator Variables, (Distributed Algorithms)
Variance, Standard Deviation, Coupon Collector, Probability Distributions: Bernoulli, Binomial, Geometric, Poisson
Las Vegas, Monte Carlo, 'Üppige-Auswahl'-Problem, Primality Testing
Quick Sort, Quick Select, Finding Duplicates, "Hase-Igel"-Algorithm
Rainbow Algorithm, Max-Flow-Min-Cut Theorem
Bipartite Matching, Edge Disjoint Paths, Vertex Disjoint Paths, Image Segmentation, Bootstrapping, Edge Contractions, Smallest Enclosing Circle
Convexity, Jarvis Wrap, Local Repair