Minimize calls to find all bad test pairs

You have (n) atomic tests (t_1, t_2, \dots, t_n).

You are given access to a black-box function:

which behaves as follows:

• runTest(S) == True if the subset (S) contains no incompatible (bad) pair of tests.
• runTest(S) == False if the subset (S) contains at least one incompatible (bad) pair of tests.

There is some unknown set of unordered bad pairs ((t_i, t_j)), where (i \ne j). You do not know in advance which pairs are bad or how many bad pairs there are.

Your goal is to discover all bad pairs while making as few calls to runTest as possible. You may adaptively choose each subset (S) based on the results of previous calls.

Tasks

1. Design an algorithm that, using only calls to runTest , finds all bad pairs ((t_i, t_j)).
2. Analyze the number of calls to runTest your algorithm requires, as a function of:
   • (n): the total number of tests, and
   • (k): the total number of bad pairs.
3. Argue why your algorithm is correct (i.e., why it will eventually find every bad pair and not report any good pair as bad).

You do not need to provide full production code, but describe the algorithm clearly enough that it could be implemented.