Algorithms for Big Data

Algorithms for Big Data (Fall 2019)

Course description: This course covers algorithmic techniques for large-scale data, with emphasis on streaming, sketching, sampling, graph streams, multiplicative weights, and submodular optimization.

Textbooks:  There is no course text.

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

Schedule

• Lectures were held on Mondays and Fridays.

Monday: 11:30–13:00 and 14:00–15:30

Friday: 11:30–13:00 and 14:00–15:30

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. Additional material and references will be added as needed.