Algorithms and Probability

• Profs: R. Kyng, J. Lengler, V. Traub
• Moodle: https://moodle-app2.let.ethz.ch/course/view.php?id=24833
• Admin: Admin
• Material: Material
• Videos:
  • https://video.ethz.ch/lectures/d-infk/2025/spring/252-0030-00L.html (Note: videos are deleted after 2 weeks)
  • HomeLab (personal)

Lecture Notes

• 01 Introduction, Connectedness, Blocks
• 02 Finding Cut Vertices and Bridges, Cycles and Circuits, Hamiltonian Cycles and Gray Codes
• 03 Hamiltonian Cycles, Dirac’s Theorem, Complexity Theory, Traveling Salesman
• 04 Cycles, Travelling Salesman Problem, Metric TSP, Matching, Augmenting Paths, Hall’s Marriage Theorem
• 05 Matchings in Bipartite Graphs
• 06 Augmenting Paths, Hopcroft-Karp, 1.5 Approximation for Metric TSP
• 07 Graph Coloring, Greedy Coloring, Smallest-Last Heuristics, Block Graph Colorings
• 08 Five-Color Theorem, Brooks Theorem, 3-Colorable Coloring Approximation, Randomness
• 09 Discrete Probability Space, Properties of Probability, Union of Events, Laplace Space, Composite Probability, Combinatorics
• 10 Conditional Probability, Independence, and Bayes’ Theorem
• 11 Independence of Multiple Events, Random Variables
• 12 Randomized QuickSort, Indicator Variables, Common Probability Distributions, Coupon Collector
• 13 Conditional Random Variables, Multiple Random Variables (Joint PMF, Marginal PMF), Independence of Random Variables, Sum of Independent Random Variables, Wald’s Identity, Variance and Concentration
• 14 Rules for Moments (Expectation, Variance), Estimating Probabilities (Markov, Chebyshev), Chernoff Bounds
• 15 Randomized Algorithms, Monte Carlo vs Las Vegas, Reducing Error Probability
• 16 Target-Shooting, Finding Duplicates, Hashing, Bloom Filter
• 17 Floyd’s Cycle-Finding (Tortoise and Hare), Primality Testing
• 18 Fermat and Miller-Rabin Primality Tests
• 19 Long-Path Problem and Reduction to Hamiltonian Cycle, Solving Hamiltonian Cycle using DP, Long-Path via Randomized Coloring
• 20 Detecting Colorful Paths using DP, Flow Networks
• 21 Flow Networks, Cuts, Max-Flow Min-Cut, Residual Networks, Ford-Fulkerson
• 22 Ford-Fulkerson with Integer Capacities, Applications of Max Flow (Max Bipartite Matching, Edge-Disjoint Paths, Image Segmentation)
• 23 Randomized Algorithms for Global Min-Cut in Undirected Graphs
• 24 Smallest Enclosing Disk via Randomized Algorithms
• 25 Convex Hulls - Geometry, Algorithms, and Complexity

Script

Still WIP…

Fundamental Definitions and Notations

Graph Theory:

• 01 Fundamentals, Connectivity
• 02 Trees, Minimum Spanning Trees
• 03 Shortest Paths
• 04 Connectivity, Articulation Points, Bridges, Block Decomposition
• 05 Cycles, Euler Tours, Hamiltonian Cycles, Traveling Salesman Problem
• 06 Matchings, Colorings

Probability:

• 01 Fundamentals, Probability Spaces and Events
• 02 Conditional Probabilities, Independence
• 03 Random Variables, Expectation, Variance
• 04 Important Discrete Distributions
• 05 Multiple Random Variables
• 06 Estimating Probabilities
• 07 Randomized Algorithms