1. (a) What is the smallest possible number of nodes in an interval tree for n intervals? Describe a construction of a set of n intervals (for any n) that achieves this minimum, assuming the interval tree construction algorithm described in class that at each step chooses the median of the remaining endpoints as the key for each node. (b) What is the largest number of nodes that the same construction algorithm could produce, given n intervals? Describe a construction of a set of n intervals (for any n) that achieves this maximum. 2. Suppose we wish to maintain a set of points in the Euclidean plane, subject to point insertions and deletions, and at each step maintain also the diameter of the point set (the maximum Euclidean distance between any two points). Describe a distance function that would let us solve this dynamic diameter problem using the dynamic closest-pair data structure described in class. 3. If D is a dictionary (set of strings), and q is a query string that is a prefix of at least one dictionary string, define the "completion" of q to be the longest string c with the following two properties: (a) q is a prefix of c, and (b) for every dictionary string d, if q is a prefix of d then c is also a prefix of d. Describe how to use a compressed trie for D to find the completion of q (if it exists) in time proportional to the length of q. Note that the completion may be much longer than q, and in this case the query algorithm should only take time proportional to q and not to c.