Introduction to Sub-linear algorithms -- Read from (W1)-(W3) and (B2)

Folklore majority finding algorithm, Frequency estimation (Misra-Gries algorithm) -- Read from (W2)

Approximate counting: Morris's algorithm; initial technique of Variance minimization by taking the average of multiple instances; Read from (W1)

Initial ideas of distinct elements -- Read from (B1)

Vitter's reservoir sampling -- Read from (W4)

Finding distinct elements and initial ideas of use of hashing -- Read from (B1)

Some ideas on hashing -- Read from (B1) and (W3)

Using the median trick on Morris to boost up success probability -- Read from (W1) and (W2)

Idea on streaming models like vanilla, cash register, turnstile, etc. and sketching -- Read from (W2)

Heavy hitters and count min sketch -- Read from (W4) and (W2)

Count sketch -- Read from (W2)

Estimating the number of distinct elements: a constant multiplicative error algorithm
Read from (W2)

Estimating the number of distinct elements: an (epsilon, delta) algorithm
Read from (W2) and the paper by Bar-yossef et al.

AMS tug-of-war sketch for F_2;
Read from (W2); the original paper is here.

A geometric interpretation (on dimensionality reduction) of AMS Tug-of-war sketch:
AMS algorithm for estimating F_k;
Read from (W2); the original paper is here.

Introduction to (one-way) communication complexity: EQUALITY (EQ), INDEX, DISJOINTNESS (DISJ)
Linear lower bounds for deterministic protocols for EQ, INDEX, DISJ;
Connections to space lower bounds for streaming algorithms;
Linear lower bound on 1-pass MAJORITY streaming problem.
Read from (W2) and (W5)

A brief discussion on reductions;
A randomized protocol for EQ -- Read from (W2) ;
A lower bound for a randomized streaming algorithm for F_∞ -- Read from (W5) ;