In this problem, your goal is to identify who among a group of people has a cert

Question

In this problem, your goal is to identify who among a group of people has a certain disease. You collect a blood sample from each of the people in the group, and label them 1 through n. Suppose that you know in advance that exactly one person is infected with the disease, and you must identify who that person is by performing blood tests. In a single blood test, you can specify any subset of the samples, combine a drop of blood from each of these samples, and then get a 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 find the infected person with as few blood 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 blood tests, for example, to find out which soldiers in World War II were carrying diseases. In those situations, the problem was even harder because there could be any number of infected people in the group. Later, we will encounter this same problem in more generality. Give an algorithm that finds the infected sample in a set of n blood samples, using as few tests as you can. Write pseudocode and a high-level English description of how your algorithm works. You don't need to prove the correctness of your algorithm.

Explanation / Answer

Find_Infected(i, j):
   if i equals j
       return i
   else if first half of samples tested positive:
       Find_Infected(i, (i + j) / 2)
   else
       Find_Infected((i + j) / 2, j)
      
Find_Infected(1, n) is how we call this method
This is a recursive solution to the problem

In high-level English Description:
-----------------------------------
This is quite easy eliminating process
1) From a set of samples, check first half of samples for the disease
2) If first half of samples tested positive then Remove the second half of the samples
3) else remove the first half of the samples for the total set
4) continue to do this until there is only one blood sample is left
5) That final blood sample which is left at the end is the one with the disease

Analysis:
-----------
If there are a total of n samples, it takes O(log n) tests to find the infected person
so, If there are a million samples, it takes about 20 tests to find the infected person, This algorithm is very efficient

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.