1. Suppose we are given a sequence of n numbers as input, within which
we wish to find range minima for contiguous subsequences. We form a
Cartesian tree from the numbers, converting the range minimum problem
into an LCA problem, and then form an Euler tour of the Cartesian tree,
converting the LCA problem back into a range minimum problem again.
What is the length of the sequence for this transformed problem?

2. Suppose we are given a computer communications network in the form of
a tree, and wish to determine the bandwidth between any pair of nodes in
the tree. Each link of the tree has a bandwidth, and the bandwidth
between nodes is the minimum bandwidth of any link on the path
connecting them. Describe how to generalize the Cartesian tree idea so
that this minimum bandwidth problem can be transformed into an LCA
problem on a related tree.

3. Let T be an alpha-balanced binary tree, for some constant
0 < alpha < 1/2. Suppose we wish to use the jump table method to compute
level ancestors in T, rather than the more complex method described in
lecture with linear space and constant query time. What would be the
space and query time bounds for jump tables on T?