Subject in 2021/2022: Data Streaming Algorithms
Teaching Staff:

Week  Lecture  Subject  Topics  Slides  Recording  Readings 

W1: 27 Sept  01 Oct  1  What is streaming?  Introduction  video  
2  Probability overview  Markov, Chebyshev, Chernoff  PDF PDF (Adv Alg)  video video (Adv Alg)  [2]  
W2: 04  08 Oct Exercise Sheet 1 PDF Solution  3  Finding frequent elements  The MisraGries algorithm  video  Ch. 1 in [1]  
4  Counting distinct elements  The Tidemark algorithm  video  Ch. 2 in [1]  
W3: 11  15 Oct Exercise Sheet 2 PDF Solution HLLanswers.pl  5  Approximate counting  The Morris counter  video  Ch. 4 in [1]  
6  Finding frequent items  CountSketch/Min Sketch  video  Ch. 5 in [1]  
7  Sparse recovery  Fingerprinting and hashing  video  Ch. 9 in [1]  
W4: 18  22 Oct Exercise Sheet 3 PDF countsketch.py countsketchanswers.py  8  l_{0}sampling  Sample by frequency  video  Sec. 10.2 in [1]  
9  Graph streams?  Connectivity, Bipartiteness  video  Sec. 14.2, 14.3 in [1]  
W5: 25  29 Oct Exercise Sheet 4  10  Shortest distances  Computing spanners  video  Sec. 14.4 in [1]  
11  Matchings I  Unweighted and weighted  video  Sec. 15 in [1]  
12  Matchings II  Multiple passes  video  Sec. 3 in [3]  
W6: 01  05 Nov  READING WEEK  
W7: 08  12 Nov  13  Matchings III  Insertiondeletion streams  Sec. 5 in [4]  
14  The AGM sketch  Connectivity with deletions  Sec. 16 in [1], [5]  
W8: 15  19 Nov  15  Lower Bounds I  Communication Complexity  Ch. 18 in [1]  
16  Lower Bounds II  Yao's Lemma, INDEX problem  Ch. 18 in [1] 