COMSM0068 Advanced Topics in Theoretical Computer Science - 2022/2023 (TB1)



Subject in 2022/2023: Data Streaming Algorithms

Teaching Staff: Teaching Units: (weeks 1-8)
  • Lectures: Tuesdays 10:00, Thursdays 11:00.
  • Problems classes: Queens 1.69. Mondays 9:00 on 3, 10, 24 October and 7, 14 November and 12 December.
  • Office hours: MVB 3.15, Tuesdays 14:00-15:00
  • TA office hours: MVB 2.59, Thursdays 10:00-11:00.

Assessment: (only exam option available)

Written exam in January (counts 100% towards your final grade)

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 LectureSubjectTopicsSlidesRecordingReadings
W1: 1What is streaming?IntroductionPDF video
2Probability overviewMarkov, Chebyshev, ChernoffPDF
PDF (Adv Alg)		video
video (Adv Alg)		[2]
W2:

Exercise Sheet 1
PDF   Solutions		3Finding frequent elementsThe Misra-Gries algorithmPDF videoCh. 1 in [1]
4Counting distinct elementsThe Tidemark algorithmPDFvideoCh. 2 in [1]
W3:

Exercise Sheet 2
PDF  Solutions
HLL-answers.py		5Approximate countingThe Morris counterPDFvideo Ch. 4 in [1]
6Finding frequent itemsCountSketch/Min SketchPDFvideo Ch. 5 in [1]
W4:

Exercise Sheet 3
PDF    Solution
countsketch.py
countsketch-answers.py		7Sparse recoveryFingerprinting and hashingPDFvideo Ch. 9 in [1]
8l0-samplingSample by frequencyPDFvideoSec. 10.2 in [1]
W5:

Exercise Sheet 4
PDF    Solution		9Graph streams?Connectivity, BipartitenessPDFvideo Sec. 14.2, 14.3 in [1]
10Shortest distancesComputing spannersPDFvideo Sec. 14.4 in [1]
W6: READING WEEK
W7:

11MatchingsUnweighted and weightedPDFvideo Sec. 15 in [1]
12The AGM sketchConnectivity with deletionsPDFvideo Sec. 16 in [1], [5]
W8:

Exercise Sheet 5
PDF   Solution		 13Lower Bounds ICommunication complexityPDFvideo Ch. 18 in [1]
14Lower Bounds IIYao's Lemma, INDEX problemPDFvideo Ch. 18 in [1]
W12: RECAP WEEK