The VLSI chip testing problem - CLRS 4.7

Problem:
Professor Diogenes has 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 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, 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.
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 [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 O(n) (proportional to 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.

Solution:
I'm assuming at least n/2 of the chips are good. The following provides a solution to the problem based on the above assumption.

A naive method

We are going to test each chip individually by comparing it against all remaining chips. We take votes from the remaining chips and let the majority decide. In case of equality, good wins. If a chip is declared bad, it is junked and we continue.

Time Analysis :

(n-1)+(n-2)+(n-3)+...+(n/2) n + n + .... + n = (n2)/2 = O(n2)

However such time is unacceptable, for it greatly exceeds O(n) time.

Divide and Conquer Approach

Definitions :
* g : a good chip
* b : a bad chip
* G : set of all good chips
* B : set of all bad chips
* B-B : pair of chips that has been declared "bad, bad"
* B-G : pair of chips that has been declared "bad, good"
* G-G : pair of chips that has been declared "good, good"

Here is one iteration of the divide and conquer approach:

If n = 1 or n = 2,
then return one chip (it is good).

If n is odd,
test odd chip.

If odd chip is good,
return the chip (it is good).

If odd chip is bad,
with remaining chips do :

* pair all chips
* junk all B-G, B-B pairs
* junk one chip of every G-G pair
* find (recursively) one good chip among the remaining chips

/*
Loop invariant : If before the iteration, |G| > |B|, then after the iteration, |G| > |B|
n(gg) + n(bb) + n(bg) + n(gb) = n (total number of chips)
When we junk B-G and G-B pairs we are removing bg/gb/bb pairs.
When we remove n(gb) and n(bg) we are removing equal number of g and b.
So the remaining n(gg) + n(bb) will have more g's. => the G-G pair list will have more g's.
*/

Remarks :

1.
If before the iteration, |G| > |B|, then after the iteration, |G| > |B|. Before the pairing step, we have |G| |B| + 2.
Each B-B, B-G pair has at one bad chip. So we junk at least as many bad chips as good ones.
So, we still have |G| |B| + 2. Each G-G pair has either two good chips or two bad ones;
what matters is that both chips are alike. Thus, the halving step leaves us with |G| |B| + 1.

2.

Time Complexity :
If T(n) is the worst-case time for n chips, then T(2) = T(1) = 0 and

T(n) = T([n/2]) + [n/2] which is clearly O(n).