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

- 141K All Categories
- 103.7K Programming Languages
- 6.5K Assembler Developer
- 1.9K Basic
- 40K C and C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.7K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 550 Python
- 37 Ruby
- 4.4K VB.NET
- 1.6K VBA
- 20.9K Visual Basic
- 2.6K Game programming
- 317 Console programming
- 92 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 742 Computer Hardware
- 3.4K Database & SQL
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 258 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 603 Jobs Wanted
- 210 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 3.4K Miscellaneous
- 8 Join the Team
- 355 Comments on this site
- 70 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 627 Off topic board
- 209 Mobile & Wireless
- 81 Android
- 126 Palm Pilot
- 339 Multimedia
- 155 Demo programming
- 184 MP3 programming
- Bash scripts
- 27 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 370 MS-DOS
- Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 942 Software Development
- 417 Algorithms
- 68 Object Orientation
- 92 Project Management
- 95 Quality & Testing
- 269 Security
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 62 AJAX
- 4 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 37 JQuery
- 307 WEB Servers
- 150 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

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

## Comments

447✭✭: 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

3447✭✭[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)

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