复旦大学：《数据结构与算法设计》实验设计_Lab 2. Divide and Conquer

Lab 2 Problem: VLSI chip testing Professor Diogenes has n 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 fo 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 d at least B is bad a. Show that if more than n/2 chips are bad, the professor cannot necessarily determine which hips are good using any strategy based on this kind of pairwise test. Assume that the bad chi to fool the profe b. Consider the problem of finding a single good chip from among n chips, assuming the 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)pairwise tests, assuming that more that n/2 of the chips are goods. Give and solve the recurrence that describes the number of tests

Lab 2 Problem: VLSI chip testing Professor Diogenes has n 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 the 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 Θ(n) pairwise tests, assuming that more that n/2 of the chips are goods. Give and solve the recurrence that describes the number of tests