# Tag Info

15

For streaming algorithms to be meaningful, they have to work with significantly smaller amount of work space than the input itself. For example, if you allow the same amount of work space as the input, then you can trivially state any algorithm as a “single-pass streaming algorithm” which first copies the input to the work space in single pass and then only ...

7

Let me give an explanation which does not differ in content from the accepted answer, but brings the question back to the realm of regular languages. The language you are dealing with can be defined as follows. Let $s \in \Sigma^{\mathbb{N}}$ be a (countably) infinite string of symbols from some finite alphabet $\Sigma$, and let $s[1:i]$ be the prefix of ...

6

Orlp gives a solution using $O(n)$ words of space, which are $O(n\log n)$ bits of space (assuming for simplicity that $n=m$). Conversely, it is easy to show that $\Omega(n)$ bits of space are needed by reducing set disjointness to your problem. Suppose that Alice holds a binary vector $x_1,\ldots,x_n$ and Bob holds a binary vector $y_1,\ldots,y_n$, and they ...

6

In the streaming model you are only allowed to store constant or poly-logarithmic extra-data while scanning through the input. If you consider a linear time algorithm that follows the divide and conquer paradigm, you need to store more information and/or you should scan through your data as many times as the depth of the recursion. One example is the DC3 ...

5

For simplicity assume, you don't have 600.000 numbers but only 1. At some time $i$ a certain number of 1s have been sent. We call this number the prefix of the stream. There are infinitely many possible prefixes. Since there is only a constant size work tape, the TM can have at most a constant number of configurations. Thus, there are at least two ...

5

The following approach is often referred to as reservoir sampling. Start scanning the set $S$ and maintain an index $j$ to the set. The first element you encounter satisfying the predicate, set $j$ to it with probability $1/1$. Update your choice for $j$ when you encounter the second such element with probability $1/2$. When you encounter the $k$th element ...

4

You can solve this in time $O(n\log B)$ and constant space (assuming a machine word can store numbers up to $\max(n,B)$) using binary search. Edit: Here are some more details. I am making the assumption that no number appears twice - perhaps that's an unfounded assumption. Given $K$, we can check whether $K<L$, $K=L$ or $K>L$ by counting how many ...

4

Ok, it's way past my bedtime, but this won't let me go, so here's a second try (deleted my first)... Before going into the specifics of how to sort the numbers, I will start by representing them not as a sequence of integers $i_1, i_2, \dots , i_n$, but as a sequence of their differences, i.e. $\delta_k = i_k - i_{k-1}$ where, by convention, $i_0 = 0$. ...

4

I interpret your question as follows. Let's fix some computational problem $P$. We define: $R(P)$ is the smallest workspace that any linear time random access algorithm for $P$ can have. I think the exact model does not matter all that much, but let's say that the we have a word RAM which is given the input as a random-access read-only array. $S(P)$ is the ...

4

Here's a sketch of an algorithm that only keeps two rows in memory at a time, so $O(m)$ memory. But since you can run this algorithm on the transpose of the matrix without issues, the actual complexity is $O(\min(m, n))$ memory. Processing time is $O(mn)$. Initialization. Scan over the first row and find all connected substrings of that row. Assign each ...

4

When reading from a source, often a program wants to read data a few bytes at a time. For instance, the program can ask the OS for the next 4 bytes from a file, so to read the next 32-bit integer. Then, it can repeat the operation again and again, until all the integers have been read. However, that is rather inefficient. First, disk (or even SSD) reads are ...

4

A balanced binary search tree can support access to arbitrary elements in $O(\log N)$ time per access. Augment the data structure to store, in each node, the number of values stored in the subtree under that node. Then you can find the $i$th largest value in the list in $O(\log N)$ time as well; thus, all basic operations can be done in $O(\log N)$ time.

4

Maintain two data structures as you move along. A hash $H$ table of frequencies. An array of sets $A$ containing the integers in each frequency. So $A$ is the set of all integers that occur once in the window, $A$ all that occur twice, etc. When you move the window, you need to do two updates, one to increment a frequency of the new integer and one ...

3

Checking whether the number of nonzero elements on each row is at most $2$ can be done in $O(1)$ space on a row-by-row basis by simply counting those elements. Therefore the only interesting part is checking the condition over the columns. This can be done in $O(M)$ space by keeping a counter for each column. In details, the counter $c_i \in \{0,1,2\}$ ...

3

Here is another way of looking at $p_A$ and $p_B$. We can think of $B$ as a deterministic algorithm which accepts an additional input $r$ representing the randomness. This input is drawn from some distribution $R$. Also, denote by $P(x)$ the correct answer. Then $$p_B(x) = \Pr_{r \sim R} [B(x,r) = P(x)].$$ Let $M = O(n\delta^{-2}\log m)$, and sample $r_1,\... 3 For your second question, one can obtain some space bounds for deterministic streaming. (See Sasho Nikolov's answer for the randomized single-pass case.) If$n$is constant, you can find the minimum using$\lceil \log_2 B \rceil$bits, by storing the smallest element not seen so far, and streaming the list$n$times. Each pass is guaranteed to either ... 2 Here's how to reduce your problem to cycle detection. Your array is a mapping$f$from$[n]$to$[n]$. From each starting point$x$, you can iterate$f$. Using a cycle detection algorithm, you can either find out that the iterates of$xform a cycle, or find two iterates that map to the same point (your duplicate). For some starting point, you will find a ... 2 Here is proof by example: \begin{align*} &[0110000,1101011] = \\ &[0110000,0110000] \cup \\ &[0110001,1000000] \cup \\ &[1000001,1100000] \cup \\ &[1100001,1101000] \cup \\ &[1101001,1101010] \cup \\ &[1101011,1101011] \end{align*} More generally, the first step is to decompose your range[a,b]$into$[a,2^k] \cup [2^k+1,b]$... 2 There's an efficient streaming algorithm for computing the average degree. Note that if you have the sum of the degrees and the number of vertices, you can compute the average -- so we'll try to keep track of those two values. Also note that if you delete or insert an edge, it is easy to update the sum of the degrees. If you delete or insert a vertex, it ... 2 An easy reduction from the Index problem shows a lower bound of$\Omega(B)$for single pass randomized algorithms. Recall that in the Index problem Alice is given a subset$S$of$U$and Bob is given an element$e$of$U$. The goal is to compute whether$e \in S$. The (randomized) one-way communication complexity of Index is$\Omega(|U|)$. For the ... 1 First, it should not be surprising that if you want to sort some numbers, a dedicated sorting algorithm is faster than using a data structure that is capable of sorting and also doing other things (finding given elements efficiently, inserting new elements efficiently, removing elements efficiently). (That said, you should find that the difference is "only" ... 1 Suppose that$x + y = A$and$x^2 + y^2 = B$. Then $$xy = \frac{(x+y)^2 - (x^2+y^2)}{2} = \frac{A^2-B}{2}.$$ Consider now the polynomial $$(t-x)(t-y) = t^2 - (x+y)t + xy = t^2-At + \frac{A^2-B}{2}.$$ The polynomial on the right has the two roots$x,y$. If$x + y = z + w$and$x^2 + y^2 = z^2 + w^2$then both$x,y$and$z,w$are the two roots of the same ... 1 As mentioned above LL would allow streaming out of box, since it would have to report the top of the parse tree with all non-terminals before reporting any terminal symbol that is coming from the text being parsed. Like in your example: S→ aS + b Upon reading first 'a' from input string 'aaa' it would have to say first that it is start of rule (non-... 1 I believe that the LR(k) property corresponds to your notion of a grammar which can be parsed in a streaming fashion. It's probably useful to (re)read Donald Knuth's 1965 paper On the Translation of Languages from Left to Right. In that paper, Knuth defines the LR(k) property in terms of the construction of the parse tree; a grammar is LR(k) iff "any handle ... 1 The first solution coming to mind is an extension of Brzozowski's derivatives as context-free grammars are closed under derivative operation with respect to a letter. Here that question answered: https://cstheory.stackexchange.com/questions/3280/generalizations-of-brzozowskis-method-of-derivatives-of-regular-expressions-to 1 One optimized way is a streaming algorithm given by Charikar, Chen and Farach-Colton, known as CountSketch. See Finding Frequent Items in Data Streams, ICALP 2002 It takes logarithmic space (in the size of your input), and gives an approximation for the$k$most-frequent elements in that input.$k$is an input parameter, that also affects the memory in use.... 1 tl;dr: This solution is quite good for random noise, but fails for bursty noise, or if you wish to get extremely low failure probability. Random Noise Assume the average noise (across the entire stream) is 10%, that is, each symbol is flipped with probability 0.1. The naive approach you suggest can be summarized as taking small chunks of data ("small" ... 1 Suppose instead that you're interested in the parity of$x$. Consider the two-player communication scenario where one player gets the even half of$L$and the other player gets the odd half of$L$. It seems plausible that the deterministic communication complexity of this game is$\Omega(n)$, and so the usual argument would give an$\Omega(n)\$ bits space ...

1

Even in the simplest definition of "streaming algorithm" (an algorithm which, after every incremental iteration on the source, results in the immediate knowledge of the next incremental piece of the result), I can think of a few linear algorithms that don't behave that way. Hashing algorithms are a big one; FNV-1a is linear to the number of bytes in the ...

Only top voted, non community-wiki answers of a minimum length are eligible