Exercise 1. DIVIDE-AND-CONQUER: DESIGNING A COVID TESTING STRATEGY. A total of n vacationers

are on a cruise ship but it is suspected that there is a COVID outbreak, and the number of COVID testing

kits is severely limited. We need to identify the infected passengers as efficiently as possible. Each

passenger has an unlimited amount of snot, all carefully collected and kept in separate jars. Snot of

different passengers can be combined in one test. Design a strategy that insures that all k sick people can

be found while using not more than O(1+ klog₂ (2n/k)) tests, where 0 ≤ k ≤n is not known beforehand.