4
$\begingroup$

Problem 1: Consider the following problem: given a binary string $w=a_1a_2\cdots a_n \in\{0,1\}^*$, decide whether $w$ contains 00000 as a substring (i.e., where $w$ contains five consecutive 0's). There is an obvious $O(n)$-time algorithm. You will investigate the hidden constant factor, concerning the number of bits that need to be examined (i.e., the number of $a_i$'s that need to be evaluated) to solve this problem.

  1. (10/100 points) First argue that every deterministic algorithm solving this problem needs to evaluate $\Omega(n)$ bits in the worst case.
  2. (30/100 points) Prove that for a sufficiently large constant $c$, for any string $a_1 \cdots a_c$ of length $c$ that does not contain 00000, there must exist two indices $i,j \in \{1,\ldots,c\}$ with $a_i=a_j=1$ and $2 \leq |i-j| \leq 5$.
  3. (60/100 points) Design a Las Vegas randomized algorithm solving this problem (with zero error probability) that evaluates an expected $\alpha n + o(n)$ number of bits for any input, for some constant $\alpha$ strictly smaller than $1$. (You do not need to optimize the constant $\alpha$.)

Above is a question some friends and I have looked at to prepare for a qualifying exam and is itself from a past qualifying exam. Parts 1 and 2 are fine but what we are having troubles with is part 3. I think the idea behind this problem is to imagine that evaluating some bit $s_i$ is really expensive, so we would like to get the right answer while minimizing how many of these bits we evaluate. That said, there is some ambiguity to us about whether we (1) care about the number of distinct bits we evaluate or (2) the total number of times we evaluate any bit. Clearly if we were worried about the latter, we could just store the result of the bit evaluation and avoid doing an expensive evaluation again, but we are not sure. For now, I assume the latter case and specifically that if we want the value for the same bit twice, we assume we need to evaluate it each time and incur $2$ units to the cost we are trying to minimize.


Now I have some idea for this problem and to help explain my idea, let us consider a simple deterministic algorithm with the pseudocode written below. We will loop from the start of the string to the end, checking all meaningful 5 bit substrings. If we ever find a $1$ bit as we loop over a 5 bit substring, we know that substring cannot be $00000$ but if we start at the bit right after that $1$ bit, there might be one. Thus, we update our new starting point to the position right after that $1$ bit and then start back up again from there.

On input $s$:

  1. set $i \leftarrow 1$
  2. while($i \leq (n-4)$):
    • set $b \leftarrow \text{true}$
    • for($j = 0$ to $4$):
      • if( $a_{i+j} = 1$ ):
        • $i \leftarrow (i+j+1)$
        • $b \leftarrow \text{false}$
        • break for loop.
    • if( $b = \text{true}$ ):
      • return TRUE
  3. return FALSE

My idea for a Las Vegas algorithm was to do the same algorithm but slightly modify it by making the inner loop performed in random order, making the pseudocode now be

On input $s$:

  1. set $i \leftarrow 1$
  2. while($i \leq (n-4)$):
    • set $b \leftarrow \text{true}$
    • for($j = 0$ to $4$ in random order):
      • if( $a_{i+j} = 1$ ):
        • $i \leftarrow (i+j+1)$
        • $b \leftarrow \text{false}$
        • break for loop.
    • if( $b = \text{true}$ ):
      • return TRUE
  3. return FALSE

The positive thing going for this algorithm is that if there exists a $1$ bit in the 5 bit substring we are looking at in the inner loop, we will find it in at most $3$ loop iterations in expectation. However, if I define a bit string $s$ to be $$s = 100001 100001 100001 \cdots 100001$$ then the algorithm should require looking at $6$ bits (potentially some of the same ones multiple times) in expectation to get past each $100001$ substring. This implies on this input we will go to see the value of $n$ bits (the number of distinct bits seen may be less) in expectation before we answer the question of if $00000$ is contained in $s$. Thus, this algorithm does not seem sufficient.

Does anyone have any thoughts on how to approach this problem or think we should actually be worried about the number of distinct bits we evaluate? If yes to the latter, then I could potentially see other ways to tackle this problem.

$\endgroup$
6
  • 1
    $\begingroup$ I think storing evaluation results is what intended. The only operation measured is "bit evaluation", so storing the result should have zero cost. Alternatively, since the length of $00000$ is constant, you can precompute what indices need checking after $i$ changes. E.g. assume that you've already checked positions 5, 3 and 1 (in the substring). Now you check 2 and see that this bit is 1. After that, you shift $i$ and 3 becomes $3-2=1$ and 5 becomes $3$. So you know that you need to check only $2,4,5$. You can use bitmasks to create an efficient map: $(j, checked_j) \mapsto new\_checked_j$. $\endgroup$ – user114966 Feb 23 at 7:28
  • 1
    $\begingroup$ The question makes it clear that you are only interested in the query complexity, that is, in how many bits of the input are read. $\endgroup$ – Yuval Filmus Feb 23 at 7:38
  • $\begingroup$ Have you tried using part 2 to solve part 3? $\endgroup$ – Yuval Filmus Feb 23 at 7:39
  • $\begingroup$ @YuvalFilmus thank you for your comments, they help to remove what we felt was some ambiguity. Since we are after query complexity, that changes the picture a little bit. That said, we looked at part 2 and suspected it was there to be used in the design of the Las Vegas algo, but it is not clear to us how it is useful. Maybe using the contrapositive of part 2 could help? $\endgroup$ – spektr Feb 23 at 7:51
  • $\begingroup$ You can use Part 2 to handle the No case easily. $\endgroup$ – Yuval Filmus Feb 23 at 7:52
2
$\begingroup$

Let $c$ be the constant from part 2, and assume for simplicity that $n$ is divisible by $c$ (otherwise, query the first $n \bmod c$ bits).

Partition the string into intervals of length $c$, and go over them one by one in an arbitrary order. The order doesn't need to be random – you can go over them from left to right.

For each interval $I$, choose a pair $(i,j)$ out of all pairs $i,j \in \{1,\ldots,c\}$ at distance $j-i \in \{2,\ldots,5\}$, and query the points $I_1,\ldots,I_i,I_j,\ldots,I_c$. If $I_i=I_j=1$, then there is no need to query the points $I_{i+1},\ldots,I_{j-1}$, otherwise do query them. If the interval contains 00000, immediately halt, answering Yes.

After going through all intervals, check whether the string contains 00000 (the unqueried points make no difference here), and answer accordingly.

According to part 2, if an interval $I$ doesn't contain 00000, then with probability $p \geq 1/4c$ the chosen pair $(i,j)$ will satisfy $I_i = I_j = 1$, and in this case we query at most $c-1$ out of the $c$ points. If it does contain 00000, then we query all points, and immediately halt. This shows that on average, we query at most $(1-1/4c^2)n + 2c$ points (taking into account the case in which $n$ is not divisible by $c$).

$\endgroup$
1
  • $\begingroup$ Thanks so much for the insights! It also seems that if we did loop over the length $c$ intervals in a random order, the expected number of bits we evaluate when the string contains 00000 should be a bit smaller. I will have to sit down and put this to paper. My friends will be happy to see what you came up with! $\endgroup$ – spektr Feb 23 at 22:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.