Algebraic Graph Algorithms – Spring 2014

Course Description: The course will focus algorithmic issues in Big-Data. This is a two semester course. In the first semester we will focus on streaming algorithms and in the second semester we will focus on sketching and sampling.

Textbooks: There is no course text.

Prerequisites: Mathematical maturity and comfort with undergraduate algorithms, basic probability and linear algebra.

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