Course Page for Graphs on Algorithms, 2024

Algorithms on Graphs (STCS VV 2024)
Course outline	Social networks, financial networks, road networks, computer networks, neural networks - these are only some of the networks we encounter in our lives. Graphs are a mathematical abstraction for studying networks. In this course we'll look at some of these networks, and study algorithms for analysing them. Topics we will cover include matchings, maximum flows, minimum cuts (and other types of cuts), planarity in graphs, and games on graphs. Course instructors: Umang Bhaskar and Juhi Chaudhary
Details	Classes will be held July 22nd - 26th in AG-66.
Reference material	A great lecture by Dan Spielman on Algebraic Graph Theory. A course by Nikhil Bansal and Jesper Nederlof on Graphs and Algorithms. An NPTEL course on Graph Algorithms. A course by David P Williamson on Spectral Graph Theory. A course by Dan Spielman on Spectral Graph Theory.

Lectures and Exercises
July 22	Session 1a: Basic graph algorithms. Notes - pptx and pdf. Session 1b: Exercises - pptx and pdf.
July 23	Session 2a: A card trick, and Eulerian walks. Notes - pptx and pdf. Session 2b: The Traveling Salesperson Problem (TSP) - pptx and pdf. References: Here is a paper that improves upon Christofides' algorithm for R^d. The run-time increases with dimension d.
July 24	Session 3: Catch them if you can - cops and robbers - pdf.
July 25	Session 4a: The Graham Pollak theorem - pdf. Session 4b: The PageRank algorithm, and Markov chains - pdf. References: Lecture notes on the fundamental theorem, and stationary distributions. Various proofs of the fundamental theorem. A great description of the PageRank algorithm. A chapter on PageRank (with exercises!) in the book by Justin Wyss-Gallifent. An alternative proof of the Graham-Pollak theorem.
July 26	Session 5: Maximum flows, minimum cuts, and the Ford-Fulkerson algorithm - pdf.
We shall not cease from exploration And the end of all our exploring Will be to arrive where we started And know the place for the first time. Happy explorations!