1. Suppose that you have constructed a suffix tree for a long string T. Describe how to use it to answer the following query: is-repeated(q) takes as input a query string, and returns as output a Boolean value, true if q appears more than once as a substring of T and false otherwise.

2. Suppose we have a set of dynamic intervals, whose endpoints are
integers in the range 1, 2, ..., n, subject to operations in which an
individual interval is inserted or deleted. At any point in this
process, we wish to find the value in the given range that belongs to
the largest possible number of intervals.  Describe how to augment the
nodes of a segment tree with additional information that would allow one
to quickly find this most heavily covered point, and that could be
quickly updated when an interval is inserted or deleted.

3. Describe a set of n intervals for which an interval tree would always
use a total of n nodes, no matter which binary tree it is based on.

4. (a) Does a quadtree for a set of n points always have O(n) nodes? Why or why not?
(b) Does a kD-tree for a set of n points always have O(n) nodes? Why or why not?