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

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

- 140.8K All Categories
- 103.6K Programming Languages
- 6.4K Assembler Developer
- 401 Assembly Code Share
- 239 Getting started in assembly
- 4.6K x86 Assembly
- 1.9K Basic
- 97 Qbasic
- 39.9K C and C++
- 5.6K Beginner C/C++
- 330 C/C++ on Linux/Unix
- 450 C/C++ Windows API
- 522 C++ Builder
- 253 C++ Game Development
- 3.3K C++ MFC
- 103 C++.NET
- 404 Visual C++
- 2.9K C#
- 7.9K Delphi and Kylix
- 334 Advanced Delphi
- 360 Delphi beginners
- 4 Haskell
- 9.7K Java
- 56 Enterprise JavaBeans
- 1.3K Java Beginners
- 304 Java Server Pages
- 4.1K Pascal
- 1.3K Perl
- 11 Perl 6
- 2K PHP
- 546 Python
- 37 Ruby
- 4.4K VB.NET
- 258 Advanced VB.Net
- 1.6K VBA
- 20.8K Visual Basic
- 767 Access databases and VB
- 831 Advance Visual Basic
- 1.2K Beginner VB
- 2.6K Game programming
- 315 Console programming
- 90 DirectX Game dev
- 1 Minecraft
- 112 Newbie Game Programmers
- 2 Oculus Rift
- 9K Applications
- 1.8K Computer Graphics
- 279 3D Graphics
- 129 DirectX
- 125 OpenGL
- 740 Computer Hardware
- 9 Cooling & Overclocking
- 3.4K Database & SQL
- 1.1K Access
- 91 ADO Programming
- 288 MySQL
- 358 Oracle
- 440 SQL-Server
- 535 Electronics development
- 1.6K Matlab
- 628 Sound & Music
- 25 DirectSound
- 257 XML Development
- 3.3K Classifieds
- 199 Co-operative Projects
- 198 For sale
- 190 FreeLance Software City
- 1.9K Jobs Available
- 603 Jobs Wanted
- 209 Wanted
- 2.9K Microsoft .NET
- 1.8K ASP.NET
- 1.1K .NET General
- 22 .NET WEB-Services
- 129 .NET WinForms
- 14 .NET XML
- 50 ADO.NET
- 142 C# & VB.NET School Support
- 3.4K Miscellaneous
- 4 Join the Team
- 354 Comments on this site
- 69 Computer Emulators
- 2.1K General programming
- 187 New programming languages
- 621 Off topic board
- 200 Mobile & Wireless
- 72 Android
- 126 Palm Pilot
- 338 Multimedia
- 154 Demo programming
- 184 MP3 programming
- 0 Bash scripts
- 27 Cloud Computing
- 1 Witsbits Go Cloud
- 53 FreeBSD
- 1.7K LINUX programming
- 1 Awk scripting
- 332 Linux Support
- 0 Sed scripting
- 370 MS-DOS
- 0 Shell scripting
- 321 Windows CE & Pocket PC
- 4.1K Windows programming
- 177 COM/DCOM
- 61 Networking And Security
- 17 Windows 2003 Server
- 6 Windows Vista
- 176 Windows XP
- 939 Software Development
- 416 Algorithms
- 68 Object Orientation
- 24 RUP & UML
- 91 Project Management
- 95 Quality & Testing
- 268 Security
- 63 Evil Scripting
- 81 Hacking
- 7.7K WEB-Development
- 1.8K Active Server Pages
- 61 AJAX
- 4 Bootstrap Themes
- 55 CGI Development
- 28 ColdFusion
- 224 Flash development
- 1.4K HTML & WEB-Design
- 1.4K Internet Development
- 131 Mobile Internet & Messaging
- 211 Wireless development
- 2.2K JavaScript
- 37 JQuery
- 304 WEB Servers
- 153 Apache
- 79 IIS
- 150 WEB-Services / SOAP

## Comments

: 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

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

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)

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.