# 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 ... 3 Let$(u,v,w)$be a particular triangle in the stream, and suppose that the edge$(u,v)$appears first. The probability that we chose$(u,v)$in the first step is$1/m$. The probability that we chose$w$in the second step is$1/(n-2)$. Hence the probability that we chose the triangle$(u,v,w)$is$1/[m(n-2)]$. Let us denote this event by$E_{u,v,w}$. If$(...

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

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 ...

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

This is an interesting question. It is not directly an LTL (Linear Temporal Logic) question -- rather a question about whether there is an algorithm or tool that takes an input stream and modifies it a somewhat minimal way to satisfy a given LTL property. Whether that you want can be done or has been done depends on what exactly the allowed modifications to ...

2

At each step, if $c == 0$, set $c=1$. Otherwise, if $c>0$, either increment $c$ or decrement $c$. Since $c$ is 0 initially, it is always true that $c\ge0$. That means, $-c\le0$ all the time. Suppose, at some moment, $c'$ is positive. The definition of $c'$ says $c'=c$ when $a^*=v$ and $c'=-c$ otherwise. Since $-c\le0$, $c'\not=-c$. So, the situation ...

1

However, I can't seem to figure the answer to the second exercice ? Is it simply to choose 'a' and 'b' in a certain manner ? or are these functions not good to generate equally randomly numbers with trailing 0s and no trailing 0s ? You have the right idea. I believe what the question is trying to suggest is that this hash function has a problem with certain ...

1

In the worst case, there is no algorithm with better space complexity than storing all data points from the past hour. So, I think you should focus on optimizing time complexity. A reasonable data structure would be to store them in a balanced binary tree, keyed on timestamp, where each node is augmented with the maximum price over all descendants of that ...

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

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

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-terminal) ...

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 ...

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