2
$\begingroup$

A real problem from the hospital.

Suppose we have $n$ blood samples to test HIV. We don't want test them one by one, since the cost is huge and most people don't have a positive result. So we try to merge them into groups, and then we just use the machine to test groups. Assume we have $k$ positive in $n$ samples, but we don't know $k$. Does a algorithm of $O(k\log_2n)$ tests (times of using the machine) exist?

  • 0
    @MaxW: this does not directly answer the question, so it is better as a comment.2012-08-16

1 Answers 1

2

Hint: if $k=1$ a binary tree (split the samples in half, mix each half, test) works. If $k \ll n$, suppose you do a binary tree and quit testing any batch that shows negative?

  • 0
    @Ross: Thanks! So, you split$n$into two n/2 groups, then get a mix inside each group (for n/2 samples) and test it, and depending whether both are negative or not, you will continue with two or one recursive calls, right? And you finish when you have a group of 2 samples. At the very last level you will do at most$k$tests and you get klogn.But this is in case when$k$<< n or if k=O(logn). If$k$is very close to n , we can do this in linear time. But what do you think about other cases? When$k$is between logn and n? Can we improve the linear algorithm?2012-01-26