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

Subject in 2020/2021: Data Streaming Algorithms

Teaching Staff:

Lecturers: Raphael Clifford (first half) and Christian Konrad (second half)
TA: Kheeran Naidu

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)

Viva: Counts 90% towards your final grade; See the welcome page of the unit on blackboard for further information
Scribe a lecture: Counts 10% towards your final grade. Use the template here. See here for an example.

Discussion Board:

We will use Piazza as our discussion board (click here to sign up)
Feel free to ask questions. We wish to see active participation.

Course Material: This unit is inspired by a similar unit at Dartmouth College (see [1] for lecture notes).

Exercise Sheet: Download here

Schedule

Week	Lecture	Subject	Topics	Slides	Recording	Readings	Scribe
W1: 05 - 09 Oct	1	What is streaming?	Introduction	PDF	video
W1: 05 - 09 Oct	2	Probability overview	Markov, Chebyshev, Chernoff	PDF PDF (Adv Alg)	video video (Adv Alg)	[2]
W2: 12 - 16 Oct	3	Finding frequent elements	The Misra-Gries algorithm	PDF	video	Ch. 1 in [1]	Roshan Ark, Kamen Bachvarov
W2: 12 - 16 Oct	4	Counting distinct elements	The Tidemark algorithm	PDF	video	Ch. 2 in [1]	Krzysztof Góra, Theano Xircouchaki
W3: 19 - 23 Oct	5	Approximate counting	The Morris counter	PDF	video	Ch. 4 in [1]	George Ioannou, Theodoros Constantinides
	6	Finding frequent items	CountSketch/Min Sketch	PDF	video	Ch. 5 in [1]
	7	Sparse recovery	Fingerprinting and hashing	PDF	video	Ch. 9 in [1]	Dan Gorringe
W4: 26 - 30 Oct	8	l₀-sampling	Sample by frequency	PDF	video	Sec. 10.2 in [1]	Cezar Alexandru
W4: 26 - 30 Oct	9	Graph streams?	Connectivity, Bipartiteness	PDF	video	Sec. 14.2, 14.3 in [1]	Thomas van Aalst, James Hawkins
W5: 02 - 06 Nov	10	Shortest distances	Computing spanners	PDF	video	Sec. 14.4 in [1]	Fergus Longley, Josh Turner
	11	Matchings I	Unweighted and weighted	PDF	video	Sec. 15 in [1]	Tom Raybould, Jacob Chalk
	12	Matchings II	Multiple passes	PDF	video	Sec. 3 in [3]
W6: 09 - 13 Nov	13	Matchings III	Insertion-deletion streams	PDF	video	Sec. 5 in [4]
W6: 09 - 13 Nov	14	The AGM sketch	Connectivity with deletions	PDF	video	Sec. 16 in [1], [5]
W7: 16 - 20 Nov	15	Lower Bounds I	Communication Complexity	PDF	video	Ch. 18 in [1]	Edward Milsom, Adithya Diddapur
	16	Lower Bounds II	Yao's Lemma, INDEX problem	PDF	video	Ch. 18 in [1]	Solly Varcoe