Problem 3 COVID testing

During this pandemic, epidemiologists have been faced with many challenging problems. One issue that arose was tracking the dominant variant of the virus that was infecting the population.

Suppose a testing lab is given n viral samples from a population on a given day. Using specialized test equipment, it is possible to use a compare test to determine whether two samples are the same or different variants. Although this test is expensive, it is faster and cheaper than running full genetic sequencing on both strands and then comparing the sequences; however, the test only returns whether the two samples are the same or not.

On input the n samples (s1, . . . ,sn), give the pseudo-code of a divide and conquer algorithm that uses only Θ(n) calls to compare(si ,sj) to determine if there is one variant that is a majority among the day’s samples. Explain why your algorithm is correct. Analyze the number of tests your algorithms performs using a recurrence.

Hint: this problem is similar to the counting problem from our first lecture. Be careful to handle all base cases properly. Your pseudo-code should require no more than 15 lines in total.