There are n samples that need to be tested for coronavirus. The testing process (known as PCR) involves using a special machine, testing one sample at a time, which is both time-consuming and expensive. Thus, we would like to have a method that is better than the trivial method of testing each sample one by one sequentially. Fortunately this is possible because we expect most samples to return a negative result (not containing the virus), and so we can 'combine multiple samples to be tested together. For example, we can take one drop from each of the samples 1, 2, 3 to form a new sample, and test this mixed sample. If it returns a negative result, then all samples 1, 2, 3 are negative. But if it returns a positive result, we only know some of them contain the virus and not which one(s), or indeed how many of them, contain the virus, and further tests are needed. Assume each individual sample contains sufficient contents so many drops can be taken from each of them, and that if a sample contains the virus, any drop taken from it will contain the virus. 1. (a) Suppose we know that exactly one of the n samples contains the virus. Design an algorithm for identifying it that takes O(log n) tests. [20 marks] 2. (b) Suppose instead we know that at most one of the n samples contains the virus. Design an algorithm for identifying the positive sample (or determine that there are Activate Wir none) using as few tests as you can. [20 marks] Go to Settings to 3. (c) Suppose instead we know that at most two of the n samples contain the virus. Repeat (b). [25 marks] There are n samples that need to be tested for coronavirus. The testing process (known as PCR) involves using a special machine, testing one sample at a time, which is both time-consuming and expensive. Thus, we would like to have a method that is better than the trivial method of testing each sample one by one sequentially. Fortunately this is possible because we expect most samples to return a negative result (not containing the virus), and so we can 'combine multiple samples to be tested together. For example, we can take one drop from each of the samples 1, 2, 3 to form a new sample, and test this mixed sample. If it returns a negative result, then all samples 1, 2, 3 are negative. But if it returns a positive result, we only know some of them contain the virus and not which one(s), or indeed how many of them, contain the virus, and further tests are needed. Assume each individual sample contains sufficient contents so many drops can be taken from each of them, and that if a sample contains the virus, any drop taken from it will contain the virus. 1. (a) Suppose we know that exactly one of the n samples contains the virus. Design an algorithm for identifying it that takes O(log n) tests. [20 marks] 2. (b) Suppose instead we know that at most one of the n samples contains the virus. Design an algorithm for identifying the positive sample (or determine that there are Activate Wir none) using as few tests as you can. [20 marks] Go to Settings to 3. (c) Suppose instead we know that at most two of the n samples contain the virus. Repeat (b). [25 marks]
