All algorithms are in pseudocode

A powerful queen has a cellar containing n barrels of expensive wine. Her guards have just caught a spy after poisoning precisely one of the queens wine barrels. To make matters worse, the poison the spy used was very deadly - just on drop from the poisoned barrel is enough to kill someone. Even so, the poison works slowly - it takes a full month for the person to die. The queen wants to discover the poisoned barrel in only one month. 1

3.1 (5p) Design a brute force algorithm that that allows the queen to determine exactly which one of her wine barrels was poisoned in just one months time. How many people need to taste the wine ?

3.2 (5p) If she can wait for few more month, design a decrease by factor algorithm that requires less people to taste the wine. How many people are needed ?

3.3 (10p) Can you think of an algorithm that will discover the poisoned barrel in one month but reduces the number of people that need to test the wine to at most dlog(n)e ? Hint: Start by thinking recursively. Assuming you have a tasting scheme for n barrels with k tasters, devise a poison-finding tasting scheme for 2n barrels using k + 1 tasters. Then unravel the recursion to see what barrels will the j-th taster drink from. It is OK if you think of n as a power of 2 for the purpose of finding the algorithm, but your algorithm should work for any n. Also, is easier if you number the barrels from 0 to n