1. There are n marble balls, one of which is made of a different material. You have access to a Comparator that can compare two inputs (of an arbitrary number of marble balls) and determine if the two inputs are the same or not. The problem is to find the single marble ball that is different from the others while minimizing the number of times you access the Comparator. Design an efficient algorithm based on prune-and-search to solve the problem. Derive the time complexity of your algorithm.
2. Show how to maintain a dynamic set Q of numbers that supports the operation MIN-GAP, which gives the magnitude of the difference of the two closest numbers in Q. For example, if Q ={1, 5, 9, 15, 18, 22}, then MIN-GAP.Q/ returns 18 – 15 = 3, since 15 and 18 are the two closest numbers in Q. Make the operations INSERT, DELETE, SEARCH, and MIN-GAP as efficient as possible, and analyze their running times.
