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

- 141.2K All Categories
- 104.5K Programming Languages
- 6.4K Assembler Developer
- 1.9K Basic
- 39.8K C and C++
- 4.3K C#
- 7.9K Delphi and Kylix
- 4 Haskell
- 9.6K Java
- 4.1K Pascal
- 1.3K Perl
- 2K PHP
- 511 Python
- 48 Ruby
- 4.3K VB.NET
- 1.6K VBA
- 20.8K Visual Basic
- 2.6K Game programming
- 311 Console programming
- 89 DirectX Game dev
- 1 Minecraft
- 110 Newbie Game Programmers
- 2 Oculus Rift
- 8.9K Applications
- 1.8K Computer Graphics
- 729 Computer Hardware
- 3.4K Database & SQL
- 522 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 256 XML Development
- 3.3K Classifieds
- 195 Co-operative Projects
- 182 For sale
- 189 FreeLance Software City
- 1.9K Jobs Available
- 600 Jobs Wanted
- 201 Wanted
- 2.9K Microsoft .NET
- 1.7K ASP.NET
- 1.1K .NET General
- 3.2K Miscellaneous
- 3 Join the Team
- 0 User Profiles
- 349 Comments on this site
- 59 Computer Emulators
- 2K General programming
- 178 New programming languages
- 609 Off topic board
- 166 Mobile & Wireless
- 40 Android
- 124 Palm Pilot
- 335 Multimedia
- 151 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 19 Cloud Computing
- 53 FreeBSD
- 1.7K LINUX programming
- 367 MS-DOS
- 0 Shell scripting
- 320 Windows CE & Pocket PC
- 4.1K Windows programming
- 887 Software Development
- 405 Algorithms
- 68 Object Orientation
- 87 Project Management
- 90 Quality & Testing
- 236 Security
- 7.5K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 2 Bootstrap Themes
- 55 CGI Development
- 19 ColdFusion
- 222 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 2.2K JavaScript
- 34 JQuery
- 283 WEB Servers
- 149 WEB-Services / SOAP

viola89
Posts: **3**Member

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

438Member: 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

3Member438Member[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]

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

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