VLSI chip testing in Introduction to Algorithm
in [Theory]
|
From: neophyte on 14 Jul 2007 04:16 how to solve this problem:VLSI chip testing in Introduction to Algorithm Professor Diogenes has n supposedly identical VLSI[1] 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. and can any body give a concret algorithm to this problem ? i'm not clear there is a linear algorithm to solve it!
From: neophyte on 14 Jul 2007 12:50 my classmates get the algorithm it 's like divide and conquer but how to proof the first question?
|
Pages: 1 Prev: Fibonacci heap and Dijkstra's algorithm Next: Reduction from Vertex Cover to SAT |