The streaming-algorithm tag has no wiki summary.
5
votes
4answers
92 views
Space complexity for finding the minimum number outside the list of numbers
We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$.
We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$.
What is the ...
0
votes
0answers
50 views
Streaming Knapsack Problem
I want to implement efficiently "streaming Knapsack" problem in java.
The problem is I have a stream input of integer data coming continuously for example -1, 2, 9, 5, 5, 11, 1 -3,...
The question ...
3
votes
1answer
209 views
Minimum space needed to sort a stream of integers
This question has gotten a lot of attention on SO:
Sorting 1 million 8-digit numbers in 1MB of RAM
The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: ...
12
votes
4answers
410 views
Is every linear-time algorithm a streaming algorithm?
Over at this question about inversion counting, I found a paper that proves a lower bound on space complexity for all (exact) streaming algorithms. I have claimed that this bound extends to all linear ...
2
votes
2answers
140 views
Counting with constant space bounded TMs
The problem, coming from an interview question, is:
You have a stream of incoming numbers in range 0 to 60000 and you have
a function which will take a number from that range and return the
...
2
votes
1answer
70 views
Choosing an element from a set satisfying a predicate uniformly at random in $O(1)$ space
We are given a set of objects, say integers, $S$. In addition, we are given a predicate $P$, for example $P(i): \Leftrightarrow i \geq 0$. We don't know in advance how many elements of $S$ satisfy the ...
6
votes
1answer
101 views
Streaming algorithm and random access
Consider an array $X$ of $n$ cells, each containing a number from $\{1,..., n\}$. There is at least
one duplicate number, i.e., a number that appears at least twice. I want output some duplicate ...
