Advanced Graph Algorithms (Jan-Apr 2014)
I assisted this course taught by Prof. Saket Saurabh at Institute of Mathematical Sciences, Chennai. Here are the lecture notes for the course prepared by the students that I reviewed.
- Lecture 1: Warm up (1) Algorithms on trees (8/1/2014), Scribe: Prafullkumar P Tale [pdf]
- Lecture 2: Warm up (2) Algorithms on t-decomposible graphs (9/1/2014), Scribe: Anantha Padmanabha MS [pdf]
- Lecture 3: Defining Tree Decompositions and their existence (10/1/2014), Scribe: Aditya Potukuchi [pdf]
- Lecture 4: Another equivalent definition of Tree Decompositions (13/1/2014), Scribe: Diptapriyo Majumdar [pdf]
- Lecture 5: An Approximation Algorithm for finding Tree Decomposition of a graph (14/1/2014), Scribe: Roohani Sharma [pdf]
- Lecture 6: Nice Tree Decompositions and Dynamic Programming on them (15/1/2014), Scribe: Prafullkumar P Tale [pdf]
- Lecture 7: Determinants, PIT and reducing Perfect Matching to PIT (20/1/2014), Scribe: Anantha Padmanabha MS [pdf]
- Lecture 8: Finding weight of minimum weighted cycle in a graph (21/1/2014), Scribe: Aditya Potukuchi [pdf]
- Lecture 9: Pfaffian of a Matrix (22/1/2014), Scribe: Diptapriyo Majumdar [pdf]
- Lecture 10: Counting number of Perfect Matchings in a graph using Pfaffian orientation (27/1/2014), Scribe: Roohani Sharma [pdf]
- Lecture 11: Finding Perfect Matching in O(n^(w+1)) time (28/1/2014), Scribe: Prafullkumar P Tale [pdf]
- Lecture 12: Finding Perfect Matching in O(n^w) time (Hervey's Algorithm) (28/1/2014), Scribe: Anantha Padmanabha MS [pdf]
- Lecture 13: Introduction to Matroids (1/2/2014), Scribe: Sanjukta Roy [pdf]
- Lecture 14: Representability of Matroids, Reduction of graph problems to Matroid Intersection and Matroid Parity (1/2/2014), Scribe: Sanjukta Roy [pdf]
- Lecture 15, 16: Solving Matroid Parity (3/2/2014, 5/2/2014), Scribe: Aditya Potukuchi [pdf]
- Lecture 17, 18: An O(mr^w) Algorithm for Matroid Parity (12/3/2014, 17/3/2014), Scribe: Aditya Potukuchi [pdf]
- Lecture 19: An O(m^w) algorithm for deciding Matroid Parity (19/3/2014), Scribe: Aditya Potukuchi [pdf]
- Lecture 20: An O(mr^(w-1)) algorithm for Matrid Parity (24/3/2014), Scribe: Aditya Potukuchi [pdf]
- Lecture 21: Matrix Multiplication and some applications (26/3/2014), Scribe: Diptapriyo Majumdar [pdf]
- Lecture 22, 23: All pair Shortest Paths in O(n^w log n) time (5/4/2014), Scribe: Roohani Sharma [pdf]
- Lecture 24: Finding the witness matrix in almost O(n^w) time (26/3/2014), Scribe: Sanjukta Roy [pdf]
- Presentation 1: Lemma of Gessel Viennot (22/4/2014), Diptapriyo Majumdar [pdf]
- Presentation 2: Proof of Tutte’s Matrix Tree Theorem using Gessel Viennot lemma (23/4/2014), Sanjukta Roy [pdf]
- Presentation 3: Counting Steiner Trees and Hamiltonian Cycles on bounded treewidth graphs (25/4/2014), Aditya Potukuchi [pdf]
- Presentation 4: Courcelle's Theorem (25/4/2014), Anantha Padmanabha MS [pdf]
- Presentation 5: Solving Minimum Steiner Tree on bounded treewidth graphs using Guassian elimination (2/5/2014), Roohani Sharma [pdf]
- Presentation 6: Construction of Almost k-wise Independent Random Variables (11/5/2014), Prafullkumar P Tale [pdf]