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

(maximize frame)

Subject in 2021/2022: Data Streaming Algorithms

Teaching Staff: Teaching Units: (weeks 1-7)
  • Lectures: online videos
  • Discussion / Q & A sessions: Monday 4pm-5pm, either online or in-person
  • Exercise classes: Tuesdays 3pm-4pm in Queens Building 1.7. starting in week 2

Assessment: (only exam option available)

Viva during the January examination period (counts 100% towards your final grade); See the welcome page of the unit on blackboard for further information

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: 27 Sept - 01 Oct1What is streaming?IntroductionPDF video
2Probability overviewMarkov, Chebyshev, ChernoffPDF
PDF (Adv Alg)		video
video (Adv Alg)		[2]
W2: 04 - 08 Oct

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

Exercise Sheet 2
PDF  Solution
HLL-answers.pl		5Approximate countingThe Morris counterPDFvideo Ch. 4 in [1]
6Finding frequent itemsCountSketch/Min SketchPDFvideo Ch. 5 in [1]
7Sparse recoveryFingerprinting and hashingPDFvideo Ch. 9 in [1]
W4: 18 - 22 Oct

Exercise Sheet 3
PDF    Solution
countsketch.py
countsketch-answers.py		8l0-samplingSample by frequencyPDFvideoSec. 10.2 in [1]
9Graph streams?Connectivity, BipartitenessPDFvideo Sec. 14.2, 14.3 in [1]
W5: 25 - 29 Oct

Exercise Sheet 4
PDF    Solution		10Shortest distancesComputing spannersPDFvideo Sec. 14.4 in [1]
11Matchings IUnweighted and weightedPDFvideo Sec. 15 in [1]
12Matchings IIMultiple passesPDFvideoSec. 3 in [3]
W6: 01 - 05 NovREADING WEEK
W7: 08 - 12 Nov

Exercise Sheet 5
PDF  Solution		13Matchings IIIInsertion-deletion streamsPDFvideo Sec. 5 in [4]
14The AGM sketchConnectivity with deletionsPDFvideo Sec. 16 in [1], [5]
W8: 15 - 19 Nov

Exercise Sheet 6
PDF  solution		15Lower Bounds ICommunication Complexity PDFvideo Ch. 18 in [1]
16Lower Bounds IIYao's Lemma, INDEX problemPDFvideo Ch. 18 in [1]
W12: 13 - 17 DecRECAP WEEK