COMSM0068 Advanced Topics in Theoretical Computer Science - 2020/2021 (TB1)

Subject in 2020/2021: Data Streaming Algorithms

Teaching Staff: Teaching Units: (weeks 1-7)
  • Lectures: online videos
  • Q & A session: Mondays 3pm-4pm
  • Exercise classes: Thursdays 10am-11am
We use ZOOM for the Q & A sessions and exercise classes. The link to the ZOOM meeting and the password can be found on the blackboard unit page in the Welcome page section. click here

Assessment: (only exam option available) Discussion Board: Course Material: This unit is inspired by a similar unit at Dartmouth College (see [1] for lecture notes).
  1. Amit Chakrabarti's notes
  2. MIT lecture notes
  3. Kale, Tirodkar 2017
  4. Konrad 2015
  5. Ahn, Guha, McGregor 2012

Schedule

Week LectureSubjectTopicsSlidesRecordingReadingsScribe
W1: 05 - 09 Oct1What is streaming?IntroductionPDF video
2Probability overviewMarkov, Chebyshev, ChernoffPDF
PDF (Adv Alg)
video
video (Adv Alg)
[2]
W2: 12 - 16 Oct3Finding frequent elementsThe Misra-Gries algorithmPDF videoCh. 1 in [1] Roshan Ark, Kamen Bachvarov
4Counting distinct elementsThe Tidemark algorithmPDFvideoCh. 2 in [1]Krzysztof Góra, Theano Xircouchaki
W3: 19 - 23 Oct5Approximate countingThe Morris counterPDFvideo Ch. 4 in [1] George Ioannou, Theodoros Constantinides
6Finding frequent itemsCountSketch/Min Sketch PDFvideo Ch. 5 in [1]
7Sparse recoveryFingerprinting and hashingPDFvideo Ch. 9 in [1] Dan Gorringe
W4: 26 - 30 Oct8l0-samplingSample by frequency Sec. 10.2 in [1]Cezar Alexandru
9Graph streams?Connectivity, Bipartiteness Sec. 14.2, 14.3 in [1]Thomas van Aalst, James Hawkins
W5: 02 - 06 Nov10Shortest distancesComputing spanners Sec. 14.4 in [1]Fergus Longley, Josh Turner
11Matchings IUnweighted and weighted Sec. 15 in [1]Tom Raybould, Jacob Chalk
12Matchings IIMultiple passes Sec. 3 in [3]
W6: 09 - 13 Nov13Matchings IIIInsertion-deletion streams Sec. 5 in [4]
14The AGM sketchConnectivity with deletions Sec. 16 in [1], [5]
W7: 16 - 20 Nov15Lower Bounds ICommunication Complexity Ch. 18 in [1]Edward Milsom, Adithya Diddapur
16Lower Bounds IIYao's Lemma, INDEX problem Ch. 18 in [1]Solly Varcoe