You are given n = 2k coins, all of which look identical. However, one of the coins is defective it weighs either slightly more or slightly less than the rest (you dont know which). You also have at your disposal an electronic equivalence tester, which has two compartments. You may place any set of objects in each compartment; the tester tells you whether or not the two sets weigh the same. Note that the tester does not tell you which side is heavier and which one lighter only whether they weigh the same or not. Your goal is to determine which of the coins is defective using the tester at most k times. You may assume that k > 1, that is, n > 2. (Is it possible to find the defective coin when n = 2?) Note that you are allowed to use the tester only k times, not O(k) or k plus a few more times. You will receive partial credit for slightly worse solutions. (a) Describe a divide and conquer algorithm for this problem. (b) Argue that your algorithm uses the tester at most k times. (c) Prove the correctness of your algorithm, in other words that it always correctly identifies the defective coin.