- 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