Assume that you have to test n person's blood samples for a particular disease. One way to accomplish this is to partition the samples into groups of size k (assume n is evenly divisible by k). And then test each of the n/k groups using n/k tests. Each of these tests will tell you whether or not at least one person in the group has the disease. If at least one person in the group has the disease, then you need to individually check each person in the group using k tests. Assume that each person has the disease with a known probability p, independent of whether other's have the disease. Compute the expected number of tests as a function of n, k, and p. Determine the value of k that minimizes the expected number of tests, as a function of n and p. Call this value of k the critical value. Determine the expected number of tests as a function of n and p at the critical value k. You may be off by a multiplicative constant in your calculations.
Hint: Use linearity of expectation and some basic probability. You will like need to make use of the folowing facts. If f(k) is increasing in k and g(k) is decreasing in k, then the minimum of max(f(k), g(k)) occurs when f(k)=g(k). Max(x, y) and x+y are within a factor of 2 for positive x and y. ln (1+x) is about x when x is near zero.
Assume that you have to test n person's blood samples for a particular disease. You again have group tests telling whether none or a positive number of people in the group have the disease. Your goal is to determine for each person whether they have the disease or not.
Assume that each person has the disease with a unknown probability p, independent of whether others have the disease. Give an algorithm to solve problem where the expected number of tests is big Oh of the expected number of tests you computed in the previous problem where p was known a priori.
Hint: Use dividing and conquer. If a group tests positive, split the group into two equal sized subgroups and recurse.
Hint: Show that the expected number of tests before you reach the critical level is big Oh of the number of tests on the critical level
Hint: Bound the tail. Show that the expected number of tests that a person is part of after the critical level is O(1).
Assume that an unknown number j of people have the disease. Give a randomized algoirthm to determine for each person whether they have the dissease or not. Explain why you would expect (so I'm looking for an informal discussion, not a formal proof) that the expected number of tests is approximately the average number of tests you would expected for the deterministic divide and conquer algorithm if each person had the disease with probability p = j/n.