4-6 Chip testing

Professor Diogenes has $n$ supposedly identical 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 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 at least $n/2$ chips are bad, the professor 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 professor.

Now you will design an algorithm to identify which chips are good and which are bad, assuming that more than $n/2$ of the chips are good. First, you will determine how to identify one good chip.

b. Show that $\lfloor n/2 \rfloor$ pairwise tests are sufficient to reduce the problem to one of nearly half the size. That is, show how to use $\lfloor n/2 \rfloor$ pairwise tests to obtain a set with at most $\lceil n/2 \rceil$ chips that still has the property that more than half of the chips are good.

c. Show how to apply the solution to part (b) recursively to identify one good chip. Give and solve the recurrence that describes the number of tests needed to identify one good chip.

You have now determined how to identify one good chip.

d. Show how to identify all the good chips with an additional $\Theta(n)$ pairwise tests.

a

If the professor want to determine which chip is good, he must get case 1 that A and B both say the other is good, and ensure there is no bad chip left. So he need to use case 2,3,4 to drop bad chips, since bad chips conspire to fool the professor, each time will drop a bad chip together a good one.

If bad chips number is more than good chips, the professor cannot necessarily determine which chips are good.

b

findgoodCchip(chips)
    if chips num is zero//end is good chips number equal bad chips  
        return NIL
    if chips num is one//must be good chips
        return this one
    if chips num is odd//good chips is more than bad chips 
        A=left one chip aside 
    else 
        A=NIL
    divide rest chips into pairs
    //floor(n/2) operation
    for each pairs//this for loop ensure good chips number are great than or eqaul bad chips
        if the report says at least one of them is bad
            drop both
        else
            drop one in the pair//worst-case: halve the size
    flag=findgoodCchip(chips)
    if flag = NIL and A!=NIL//A is good chip
        return A
    if flag = NIL and A==NIL//no good chip from this call stack
        return flag
    if flag
        return flag

c

already apply the solution recursively in part(b),

$$ \begin{aligned} T(n)=n/2+T(n/2)\cr T(n)=\Theta(n)\cr \end{aligned} $$

d

use the good chip to test other chips$\Theta(n)$.