Computing an average, a max, or a median of a finite state is easy and we all know how to achieve it. However, computing an average, a max or a median for a stream is much more complex. Even solutions like ‘sliding windows’ who only consider a subset of the stream at any given time may be too expensive to us.
Scientists (yay!) have been working on such problems for years and we will introduce you to some of these techniques, including the secretary algorithm, lossy counting, or the greedy algorithm!