Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people, just like you, are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
Solved

A Computer Science/Math Algorithm Question

Posted on 2008-10-06
7
397 Views
Last Modified: 2008-10-15
Calling all Math and CS Theory wizards, here's an algorithm question that I need help with. This would require use of recurrence and divide and conquer strategy:

There are n supposedly identical VLSI chips that in principle are capable of testing each other. Each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is good or bad, but the answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows:

Chip A says  Chip B says     Conclusion
B is good       A is good          both are good, or both are bad
B is good       A is bad            at least one is bad
B is bad         A is good          at least one is bad
B is bad         A is bad            at least one is bad

a. Show that if more than n/2 chips are bad, we cannot necessarily determine which chips are good using any strategy based on this kind of pairwise test. Assume that the bad chips can conspire to fool the the tester.


b. Consider the problem of finding a single good chip from among n chips, assuming that more than n/2 of the chips are good. Show that floor(n/2) pairwise tests are sufficient to reduce the problem to one of nearly half the size.


c. Show that the good chips can be identified with Theta(n) pairwise tests, assuming that more than n/2 of the chips are good. Give and solve the recurrence that describes the number of tests.
0
Comment
Question by:zxzwin
  • 3
  • 2
  • 2
7 Comments
 
LVL 84

Expert Comment

by:ozo
ID: 22656706
if more than n/2 chips are bad. a possible outcome is all bad chips report other bad chips as good, and good chips as bad
this is indistinguishable from the result if all the bad were good and all the good were bad.
0
 

Author Comment

by:zxzwin
ID: 22656835
Hmm, ok. I think a) is easier to understand conceptually. But parts b and c require more rigorous math, which is what I'm stuck on... Any more help on those parts are appreciated! Thanks in advance.
0
 

Accepted Solution

by:
zxzwin earned 0 total points
ID: 22656918
0
Free Tool: Path Explorer

An intuitive utility to help find the CSS path to UI elements on a webpage. These paths are used frequently in a variety of front-end development and QA automation tasks.

One of a set of tools we're offering as a way of saying thank you for being a part of the community.

 
LVL 18

Expert Comment

by:deighton
ID: 22657728
I don't understand, if they are all good then you get nothing but good readings, if they are all bad then you may also get nothing but good readings, so how can you be sure you have the first case and not the second?


0
 
LVL 84

Expert Comment

by:ozo
ID: 22664794
> how can you be sure you have the first case and not the second?
If you know that more than n/2 of the chips are good, it rules out the second case.
If you know that more than n/2 chips are bad, it rules out the first case.
0
 
LVL 18

Expert Comment

by:deighton
ID: 22668408
>>If you know that more than n/2 of the chips are good, it rules out the second case.

but then they've been tested by some other means in the first place in order to know that.  
0
 
LVL 84

Expert Comment

by:ozo
ID: 22668450
Or you can just assume it, as the question instructs.
0

Featured Post

Networking for the Cloud Era

Join Microsoft and Riverbed for a discussion and demonstration of enhancements to SteelConnect:
-One-click orchestration and cloud connectivity in Azure environments
-Tight integration of SD-WAN and WAN optimization capabilities
-Scalability and resiliency equal to a data center

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
We are taking giant steps in technological advances in the field of wireless telephony. At just 10 years since the advent of smartphones, it is crucial to examine the benefits and disadvantages that have been report to us.
This is a video describing the growing solar energy use in Utah. This is a topic that greatly interests me and so I decided to produce a video about it.
Finds all prime numbers in a range requested and places them in a public primes() array. I've demostrated a template size of 30 (2 * 3 * 5) but larger templates can be built such 210  (2 * 3 * 5 * 7) or 2310  (2 * 3 * 5 * 7 * 11). The larger templa…

856 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question