Assignment

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. Exercise 14.3-6 (page 354). Use an example to demonstrate your augmented data structure and operations.

(14.3-6 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 D f1; 5; 9; 15; 18; 22g, then MIN-GAP.Q/ returns 18  15 D 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.). This is the exercise question 14.3-6 as mentioned above.