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

- 141.9K All Categories
- 104.8K Programming Languages
- 6.4K Assembler Developer
- 1.9K Basic
- 39.9K C and C++
- 4.3K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 526 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 312 Console programming
- 89 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 733 Computer Hardware
- 3.5K Database & SQL
- 534 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 257 XML Development
- 3.3K Classifieds
- 198 Co-operative Projects
- 189 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 602 Jobs Wanted
- 203 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 6 Join the Team
- 0 User Profiles
- 354 Comments on this site
- 66 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 613 Off topic board
- 179 Mobile & Wireless
- 53 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 22 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 369 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 913 Software Development
- 409 Algorithms
- 68 Object Orientation
- 89 Project Management
- 90 Quality & Testing
- 256 Security
- 7.6K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 35 JQuery
- 292 WEB Servers
- 154 WEB-Services / SOAP

viola89
Member Posts: **3**

in Algorithms

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

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

Terms of use / Privacy statement / Publisher: Lars Hagelin

Programmers Heaven articles / Programmers Heaven files / Programmers Heaven uploaded content / Programmers Heaven C Sharp ebook / Operated by CommunityHeaven LLC

© 1997-2015 Programmersheaven.com - All rights reserved.

## Comments

439: 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

:

[code]

for i := 2 to n step 2 do

if (a[i] = 0) and (a[i-1] = 0) then

3439[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]

3I 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)

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