1. (a) What is the maximum number of nodes that a kD-tree for n points can have, as a function of n? Include the nodes at all levels of the kD-tree hierarchy, not just the leaves. (b) What is the minimum number of nodes that a quadtree for n points can have, as a function of n? (c) Draw a set of 5 points, and a kD-tree for that set, that achieves the maximum number of nodes from part (a). Also draw a different set of 5 points, and a quadtree for that set, that achieves the minimum number of nodes from part (b). 2. Let L1 = 2, 3, 5, 7, 11, 13 ... be the sequence of prime numbers. Let L2 = 0, 4, 8, 12, 16, ... be the sequence of multiples of four. And let L3 = 1, 4, 9, 16, 25, 36, ... be the sequence of nonzero square numbers. (a) List the first ten numbers in each of the three lists formed in a fractional cascading data structure for L1, L2, and L3. (b) Let q=10, and suppose that we wish to find in each input list Li the first number xi that is greater than or equal to q. Which numbers in the second and third of the fractionally cascaded lists would be examined as part of this query?