b) Fix n and k. Give an upper bound (in terms of n and k) for the number of test
ID: 3671414 • Letter: B
Question
b) Fix n and k. Give an upper bound (in terms of n and k) for the number of tests that will be performed by FindInfected on an input of n samples, k of which are infected. Explain why you will always be able to locate all infected samples using no more than this number of tests.
5. Suppose you have n blood samples, k of which are infected with a certain disease. In a single blood test, you can specify any subset of the samples, combine a drop of blood from each of these samples, and get a test result. If any sample in the subset is infected, the test will come up positive, otherwise it will come up negative. Your goal is to identify all of the infected samples with as few group tests as possible. This idea of testing multiple samples at a time has been used in history at times when it was impractical or expensive to perform tests, for example, to find out which soldiers in World War II were carrying diseases. We have seen this problem in Homework 3 in the special case of k = 1, when there was only one infected sample. In that case, we saw it was best to use binary search to find the infected sample (see the solutions to Homework 3). We will now address the problem more generally, when any number of samples can be infected, and we want to identify all of them. Here is an algorithm for finding all k infected samples. We will assume for simplicity that n/k is a power of two, so that n/k is an integer, and log(n/k) is also an integer FindInfected(n blood samples, k of which are infected) 1.Break the samples into k groups of size n/k 2. For each group G 3. 4. 5. 6. Test a combination of blood from all samples in G If the test is negative, go on to the next group Otherwise, while G contains some infected sample, Use binary search to find one infected sample in G Add that infected sample to the output list. Remove the infected sample from G Retest the remaining samples in G 10. Return the list of infected samples. (a) (4 points) Suppose we have 12 blood samples and 3 of them are known to be infected. Number the samples from 1 to 12. If samples 2, 3, and 11 are infected, trace through the algorithm, and make a list of all the tests the algorithm performs by filling in the following table samples tested result of test (positive or n tive or negative Assume that in line 6, we use binary search by taking the first half (rounded up if the number of samples is odd) of the samples in the group and testing them. If the test returns positive, we know there is an infected sample in the first half, and we recursively search there. If the test returns negative, we do a binary search in the second half.Explanation / Answer
a)
we have n samples == 12 blood samples
k = infected ones .. k =3
So we will split into groups into n/k = 12/3 = 4 groups..
we know samples 2,3,11 are infected.
-----------------------------------------------------------------------
samples Tested result of Test
{1,2,3} Negative (2 and 3 are negative)
{4,5,6} Positive
{7,8,9} Positive
{10,11,12} Negative (11 is infected)
==================================================================================
b)
As we are splitting n samples into n/k so we will have n/k datasets and each dataset contains K elements.
We are following binary search approach .. it takes complexity O(log n)
so for n/k sets .. the complexity for upper bound is O(n/k log k)
As we are splitting into each set .. and each set is searched by binary search,
it will checks from root node to its all child nodes. So, infected one must iterates.
Therefore we will find infected ones always.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.