0
$\begingroup$

An engineer has n supposedly identical integrated-circuit chips that in principle are capable of testing each other. The engineer 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 engineer cannot trust the answer of a bad chip. Assume that thenumber of good chips is greater than the number of bad chips. Thenanswer the following question:

Is it possible to design an algorithm that finds all the good chips after at most O(n log n) pairwise tests?

|cite|improve this question
$\endgroup$
  • $\begingroup$ Is it possible to design an answer to the question of whether this is a school assignment? $\endgroup$ – Mark L. Stone May 30 at 20:50
  • $\begingroup$ I know two solutions one in O (n ^ 2) and one in O (n) but I would like to know if a solution is possible in O (n log n). $\endgroup$ – neider May 30 at 21:22
  • 1
    $\begingroup$ Hmm, isn't O(n) better than O(n logn), leaving constants aside? $\endgroup$ – Mark L. Stone May 30 at 22:15
  • 3
    $\begingroup$ @MarkL.Stone is correct. $O(n)$ is better. Even more, if we look at $O$ notation (and not $\Theta$ - tight notation), $O(n)$ would qualify for an $O(n\log n)$. $\endgroup$ – Anton Menshov♦ May 30 at 22:36
0
$\begingroup$

The answer is yes. It is possible. What have you tried so far? Have you implemented any code to test different algorithms?

I also suspect this is homework, but I will give you some ways to think about this problem. What would be the -worst- way to test the chips? If you check any chip with every other one you would have n² checks to perform. Is there any way you could use the additional information, that there are more correct than incorrect readings, to improve this?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The only way that I think possible is an algorithm with a recurrence T (n) = 2T (n / 2) + cn. But how to split the set in two ensuring that one part has more good chips than bad ones? $\endgroup$ – neider Jun 2 at 19:38
  • $\begingroup$ You are thinking of a divide-and-conquer algorithm. Maybe you don't even need that. Lets say you pick up one chip, and test all the other ones with this one (that takes N cheks). you sort them into two stacks wether they agree with the one that you are testing with and not.. $\endgroup$ – MPIchael Jun 4 at 9:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.