<p>In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following:</p>

<ol>
<li><p>Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space.</p></li>
<li><p>Approximate bit counting on a sliding window - given a bit-stream, answer queries approximating the number of $1$'s in the last $N$ bits, and do so using $O(\log N)$ space.</p></li>
<li><p>Sampling from a sliding window (at any point, give a sample of $k$ elements uniformly chosen from the last $N$ elements of a stream).</p></li>
<li><p>Exact item counting - answer queries of the form "how many times did $x$ appear in the stream" such that the answer will be correct w.h.p. using only sublinear space (modern data structures are quite complex, but <a href="http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch">Count–min sketch</a> seems to fit undergrad course).</p></li>
</ol>

CC BY-SA 3.0
2014-12-01T18:44:47.653Z
Exact item counting with high probability requires linear space. CM sketch approximates the item count by a factor proportional to the total count of all items. But I agree it's a good choice.
Sasho Nikolov
CC BY-SA 3.0
2014-12-02T08:37:34.940Z
Only issue is you have to handwave-away the fact that the hash functions can be stored in small space.
arnab
CC BY-SA 3.0
2014-12-01T12:57:41.640Z
2014-12-01T12:57:41.640Z
R B
<p>There are several algorithms for <a href="http://en.wikipedia.org/wiki/Count-distinct_problem" rel="noreferrer">estimating cardinality</a>. This problem seems to be important enough in practice. For example, Redis, which describes itself as a ‘data structure server’, supports it. I suspect students would find this a good motivation. The algorithm that Redis uses, HyperLogLog, may be too difficult to analyze in an undergrad course. But, there are some alternative algorithms that seem good for an undergrad course. One is to use the minimum value of all hash values seen. Another is to keep the maximum $k$ such that $2^k$ divides at least one of the hash values. The HyperLogLog paper is a good starting point for even more alternatives:</p>

<ul>
<li>Flajolet et al., <em><a href="http://scholar.google.com/scholar?hl=en&amp;q=HyperLogLog%3A%20the%20analysis%20of%20a%20nearly-optimal%20cardinality%20estimation%20algorithm" rel="noreferrer">HyperLogLog: the analysis of a nearly-optimal cardinality estimation algorithm</a></em>, 2007</li>
</ul>

CC BY-SA 3.0
2014-12-19T14:34:37.197Z
2014-12-19T14:34:37.197Z
Radu GRIGore
<p>I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course.</p>

<p>Good choices should probably satisfy the following requirements:</p>

<ul>
<li><p>Solve a problem that is useful in practice or easy to motivate, or alternatively, illustrate techniques that are beautiful or useful.</p></li>
<li><p>Be suitable for presentation in an undergraduate algorithms course.  This means the algorithm and analysis can't be too complex.  Also they shouldn't require too much heavy probability theory to analyze (sadly, this rules out many beautiful algorithms).</p></li>
</ul>

<p>What would be a good candidate?</p>

<p>One beautiful algorithm is the deterministic algorithm to find an element that occurs with frequency at least 50% (if any such element exists), using $O(1)$ space; or its generalization, find all items that occur with frequency at least $1/k$, using $O(k)$ space.  Are there any others that would be an excellent choice for an undergraduate course?</p>

CC BY-SA 3.0
2014-12-01T12:40:00.047Z
Here is a cool one http://geomblog.blogspot.com/2008/01/happy-birthday-don-knuth.html
Pratik Deoghare
CC BY-SA 3.0
2014-12-01T16:19:11.080Z
what about compression (eg [LZW](http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch))?
vzn
<ds.algorithms><teaching><online-algorithms><streaming-algorithms>
Streaming algorithms suitable for undergrad course
D.W.
# Streaming algorithms suitable for undergrad course

(Asked by: username_0 on 2014-12-01)

I am looking for interesting streaming algorithms that would be suitable for presentation in an undergraduate algorithms course.

Good choices should probably satisfy the following requirements:

* Solve a problem that is useful in practice or easy to motivate, or alternatively, illustrate techniques that are beautiful or useful.
* Be suitable for presentation in an undergraduate algorithms course. This means the algorithm and analysis can't be too complex. Also they shouldn't require too much heavy probability theory to analyze (sadly, this rules out many beautiful algorithms).

What would be a good candidate?

One beautiful algorithm is the deterministic algorithm to find an element that occurs with frequency at least 50% (if any such element exists), using $O(1)$ space; or its generalization, find all items that occur with frequency at least $1/k$, using $O(k)$ space. Are there any others that would be an excellent choice for an undergraduate course?

**Tags:** ds.algorithms, teaching, online-algorithms, streaming-algorithms

> **Comments:**
> **username_1**: Here is a cool one http://geomblog.blogspot.com/2008/01/happy-birthday-don-knuth.html  
> **username_2**: what about compression (eg [LZW](http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welch))?  

---

## 2 answers

### Answer by username_3 on 2014-12-01. Score: 8

In addition to the Heavy Hitters problem you've mentioned (which has quite a few algorithms: batch-decrement, space-saving, etc.), I'd consider presenting the following:

1. Reservoir sampling - maintain a sample of $k$ elements, uniformly sampled from the set of items which appeared in the stream so far, in $O(k)$ space.
2. Approximate bit counting on a sliding window - given a bit-stream, answer queries approximating the number of $1$'s in the last $N$ bits, and do so using $O(\log N)$ space.
3. Sampling from a sliding window (at any point, give a sample of $k$ elements uniformly chosen from the last $N$ elements of a stream).
4. Exact item counting - answer queries of the form "how many times did $x$ appear in the stream" such that the answer will be correct w.h.p. using only sublinear space (modern data structures are quite complex, but [Count–min sketch](http://en.wikipedia.org/wiki/Count%E2%80%93min_sketch) seems to fit undergrad course).

> **Comments:**
> **username_4**: Exact item counting with high probability requires linear space. CM sketch approximates the item count by a factor proportional to the total count of all items. But I agree it's a good choice.  
> **username_5**: Only issue is you have to handwave-away the fact that the hash functions can be stored in small space.  

---

### Answer by username_6 on 2014-12-19. Score: 5

There are several algorithms for [estimating cardinality](http://en.wikipedia.org/wiki/Count-distinct_problem). This problem seems to be important enough in practice. For example, Redis, which describes itself as a ‘data structure server’, supports it. I suspect students would find this a good motivation. The algorithm that Redis uses, HyperLogLog, may be too difficult to analyze in an undergrad course. But, there are some alternative algorithms that seem good for an undergrad course. One is to use the minimum value of all hash values seen. Another is to keep the maximum $k$ such that $2^k$ divides at least one of the hash values. The HyperLogLog paper is a good starting point for even more alternatives:

* Flajolet et al., *[HyperLogLog: the analysis of a nearly-optimal cardinality estimation algorithm](http://scholar.google.com/scholar?hl=en&q=HyperLogLog%3A%20the%20analysis%20of%20a%20nearly-optimal%20cardinality%20estimation%20algorithm)*, 2007


---

