weems@cse.uta.edu (Bob Weems) (06/27/91)
Cormen, Leiserson, and Rivest's "Introduction to Algorithms" gives a problem on testing chips pairwise. The goal of the problem is to demonstrate that the good chips (which are in the majority) can be found in linear time. Since the problem is in an early chapter on solving recurrences, it does not seem that the algorithm should be that challenging. Nonetheless, it has me stumped. The problem seems related to system-level fault diagnosis and the 1967 IEEE T-C paper of Preparata et.al., but that seems like overkill. Send responses by email. Bob Weems weems@cse.uta.edu