(5 pts for S70/fbonus for 470)Professor Dogenes has n suposedly dentical integra

Question

(5 pts for S70/fbonus for 470)Professor Dogenes has n suposedly dentical integrated-circuit 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 good or bad, but the professor cannot trust the answer of a bad chip. Thus, the four possible outcomes of a test are as follows: Chip A says Chip 8 says Conclusion 8 is good A is good both are good, or both are bad 8 is good A is bad 8 is bad B is bad The solution to finding a good chip from the batch is very similar to a problem we studied in elass. What is that problem? A is good A is bad at least one is bad at least one is bad at least one is bad

Explanation / Answer

Hey there,  

Ques is that "whats the problem discussed in your class to find the chips weather they are good or bad .

So im going to give all the methods for solving this type of problem, now its up to you

First one

If more than half are bad

Lets say that there are g<n/2 good chips. The same amount of the remaining bad chips can choose to act similar to good chips. That is, they can identify each other as good and all other as faulty. Since this is what the good chips would do, both groups are symmetric in regards to the operation of parwise comparison. No strategy can distinguish between the two groups.

Finding a single good chip in logarithmic time

We split the chips in groups of two and compare them. We can take one of the chips if the outcome is the first one (both are good or both are bad) and but both away otherwise. When putting away, we're removing at least one bad chip for every good one we remove. Out of the pairs we've chosen a chip from, there would be more good chips than bad chips (there would be more good pairs, because the good chips are more than the half). Now we have at most n/2 chips, where at least half of them are good.

Finding the good chips

The recurrence for finding at least one good chip is:

T(n)=T(n/2)+n/2

By the master method, this is (n). After we've found one, we can compare it will all others, which is a (n) operation.

########second PHYTHON code for this problem ########

Thank yoy

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

---

---

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