Professor Diogenes has n supposedly identical VLSI chips that in principle are c

Question

Professor Diogenes has n supposedly identical VLSI chips that in principle are capable of testing each other. The professor's test jig accommodates two chips at a time. When the jig is loaded, each chip tests the other and reports whether it is good or bad. A good chip always reports accurately whether the other chip is answer of a bad chip cannot be trusted. Thus, the four possible outcomes of a test are as follows: 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 [n/2] pairwise tests are sufficient to reduce the problem to one of nearly half the size.

Explanation / Answer

Algorithm can be as follows:

No paiwise checking does not reduce the problem to hals as it is possible that every set has one bad chip becuse as per our assumption n/2 are good chips.

1.Pick up one chip
2.Test the chip with all the other chips
3. As we know that there are n/2 chips are ok.
4.We will look at the result (Assuming bad chip will give wrong result and good chip will give correct reult)
   if the selected chip is good---the number of good reults will be atleast (n/2-1)
   if the selected chip is bad---the number of bad reults will be atleast (n/2)
5. By this we can say wheteher a given chip is good or bad.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.