Algorithms for Big-Data

Algorithms for Big-Data (Spring 2019)

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 and basic probability.

Lectures Timing and Schedule:

• Lecture will be held every

Monday: 11:30 to 13:00 and 1400: 1530

Friday: 11:30 to 13:00 and 1400: 1530

1. Lecture 01: Insertion Only Stream, Dynamic Stream Connectivity [Scribes] [Video]
2. Lecture 02: Dynamic Stream Connectivity (Lo-sampling, randomised construction) [Scribes] [Video]
3. Lecture 03: l_0 sampling - using 2 wise hash functions [Scribes] [Video]
4. Lecture 04: Application of connectivity Sketch, Bipartiteness, Approx MST [Scribes] [Video]
5. Lecture05: Application of Connectivity Sketch [Scribes] [Video]
6. Lecture 06: Sparsifiers in Dynamic Stream [Scribes] [Video]
7. Lecture 07: Sparsifiers and Local Ratio [Scribes] [Video]
8. Lecture 08: Weighted Maximum Matching in Insertion Stream [Scribes] [Video]
9. Lecture 09: Reservoir Sampling, Estimated on Max Matching in Graphs of bounded Arboricity [Scribes] [Video]
10. Lecture 10: Estimate on Max Matching in graphs of bounded Arboricity, Small Matching (Insertion) [Scribes] [Video]
11. Lecture 11: Small matching in dynamic stream [Scribes] [Video]
12. Lecture 12: Multiplicative Weight update Algorithms 1 [Scribes] [Video]
13. Lecture 13: Multiplicative Weight update Algorithms 2 [Scribes] [Video]
14. Lecture 14: Multiplicative Weight update Algorithms 3 [Scribes] [Video]
15. Lecture 15: Multiplicative Weight update Algorithms 4 [Scribes] [Video]
16. Lecture 16: Multiplicative Weight update and Primal-Dual [Scribes] [Video]
17. Lecture 17: Primal-Dual Algorithms -1 [Scribes] [Video]
18. Lecture 18: Primal-Dual Algorithms -2 [Scribes] [Video]
19. Lecture 19: Multiple-Pass Matchings via Multiplicative Weights [Scribes] [Video]
20. Lecture 20: Max-Coverage and Set Cover Greedy Approximation and Streaming Algorithm for Max-Coverage [Scribes] [Video]
21. Lecture 21: Submodularity, Greedy Approximation for Montone Non-negative Submodular Maximization and its streaming version [Scribes] [Video]
22. Lecture 22: Non Monotone Submodular Maximisation 1 [Scribes] [Video]
23. Lecture 23: Non Monotone Submodular Maximisation 2 [Scribes] [Video]
24. Lecture 24: Cardinality Sudmodular Maximization [Scribes] [Video]
25. Lecture 25: Submodular Maximization with Cardinality Constraint: Streaming [Scribes] [Video]
26. Lecture 26: Set Cover: Streaming [Scribes] [Video]
27. More lectures to be added as and when we complete. (Scribes are coming)