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

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