finding two consecutive zeros in a bit string - Programmers Heaven

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

#### Categories

Welcome to the new platform of Programmer's Heaven! We apologize for the inconvenience caused, if you visited us from a broken link of the previous version. The main reason to move to a new platform is to provide more effective and collaborative experience to you all. Please feel free to experience the new platform and use its exciting features. Contact us for any issue that you need to get clarified. We are more than happy to help you.

# finding two consecutive zeros in a bit string

Posts: 3Member
Hi,
Please help to design an algorithm that determines if a bit string of length n contains two consecutive zeros. It has to solve the problem by examining fewer than n bits. Or I need to give an adversary strategy to force algorithm to examine every bit. n = 2,3,5.
Thanks for help

• Posts: 438Member
: Hi,
: of length n contains two consecutive zeros. It has to solve the
: problem by examining fewer than n bits. Or I need to give an
: adversary strategy to force algorithm to examine every bit. n =
: 2,3,5.
: Thanks for help
:
[code]
for i := 2 to n step 2 do
if (a[i] = 0) and (a[i-1] = 0) then
• Posts: 3Member
if n=2, your code checks both a[2] and a[1] in the second line. Probably only adversary strategy can be applied when n=2,3,5 to force algorithm to examine every bit.
• Posts: 438Member
: if n=2, your code checks both a[2] and a[1] in the second line.
[blue]
Not necessarily. If your compiler uses left to right short circuit evaluation then a[1] will be checked only if a[2] = 0. But so what? What exactly are you saying?
[/blue]
: Probably only adversary strategy can be applied when n=2,3,5 to
: force algorithm to examine every bit.
:
[blue]
Define "adversary strategy." And what is the significance of n=2,3,5?

Is not the requirement to check fewer than n bits? Dropping that requirement allows for a much simpler algorithm.
[/blue]
[code]
for i := 2 to n
if (a[i-1] = 0) and (a[i] = 0) then
return TRUE
return FALSE
[/code]

• Posts: 3Member
Sorry for the confusion. The problem I need to solve is that if I cannot solve a problem with n-1, I will instead try to come up with an adversary strategy that forces each bit to be tested/checked.

I know that you can check with less than n-1 if n=4, and I am convinced that I cannot solve in n-1 if n=2,3, or 5. So my challenge is to devise an adversary strategy that forces each bit to be analyzed. For n=3 if the odd position is chosen first, then adversary reveals a one, which will force an algorithm to check both position two and three. If the even position is chosen first, then the adversary reveals a zero, any next position picked will reveal a one, and the algorithm is again forced to check all bits. I am not sure that my thinking is correct and I am not sure when n=5.

The algorithm has to behave the same in all cases for the same size of n, meaning if it checks n-1, then it should be correct in all cases (000, 001, 010, 100, 101, 110, 111). But if a[i] is zero when n=3, and a[i-1] is one, you will still have to check a[i] to be sure there is no zero there.
The idea for the adversary is to force the algorithm to check all positions. I believe it is useful when we want to find out worst-case running time of the algorithm. For example, when n=2, if any position is chosen, the adversary says it is zero, because if it tells that it is one, then the algorithm does not need to check the other position.

How can it not check a[i] when a[i-1] is zero when n=2 or why would it check a[i] if a[i-1] is one? (00, 01, 10,11)
• Posts: 438Member
[red]Please help to design an algorithm that determines if a bit string of length n contains two consecutive zeros. It has to solve the problem by examining fewer than n bits. Or I need to give an adversary strategy to force algorithm to examine every bit. n = 2,3,5.[/red]

At this point I don't think I understand the requirement, so let's go back to the beginning, starting with defining terms.

A [b]bit[/b] is a variable that can only assume values of 0 or 1.
A [b]bit string[/b] means a one dimensional array, or matrix, of bits.
The [b]length n[/b] of the bit string is its size. The elements of the array are indexed from 1 .. n.
[b]two consecutive zeros[/b] refers to any two elements of the array whose values are 0 and whose indices differ by 1, i.e., a[i] = a[j] = 0 and | i - j | = 1.

The term [b]adversary[/b] is confusing. Synonyms for [b]adversary[/b] are [b]enemy, opponent, opposing, conflicting[/b]. I suspect you mean [b]alternate[/b]. Synonyms for alternate are [b]substitute, different, complementary[/b].

So much for definitions.

My understanding of the requirement itself is this:

Given a bit string of length n, the algorithm should return TRUE if and only if there exist i and j such that:

1. 0 <= i <= n
2. 0 <= j <= n
3. | i - j | = 1
4. a[i] = a[j] = 0

Under this interpretation, if n = 3 then each of the algorithm should return TRUE for each of the following.

[000], [001], [100]

and FALSE for

[010], [011], [101], [110], [111]

I am also confused as to what is special about n = 2,3,5.