1. Consider the following eight-node tree, rooted at node A: B F / / A--C--G--H \ D \ E (a) List the nodes in the order in which they would be given in an Euler tour. (When visiting the children of a node, visit them in top-down order; i.e., visit B before C and C before D.) (b) List the distances from the root in the same order. (c) Indicate a subinterval of this list of distances that would correspond to a lower-common-ancestor query that asked for the lowest common ancestor of D and F. 2. Draw a Cartesian tree for the sequence 3, 13, 6, 12, 1, 9, 19, 11, 5, 16, 17. In the tree, indicate the pair of nodes that would correspond to a range minimum query for the subsequence from 9 to 5. 3. In the linear-space range minimum structure of Bender and Farach-Colton, suppose that (after using the Cartesian tree and Euler tour transformations to make each consecutive pair of numbers differ by +/- 1) we partition the initial input array of numbers into blocks of 8 numbers each. (a) Define the "pattern" of a block to be the sequence of differences (+/- 1) between the consecutive pairs of numbers within the block. How many different patterns are there? (b) Suppose that we build a table T[pattern,starting position,ending position] that stores the position of the minimum value in a subarray of a block with the given pattern, starting at the given starting position within the block and ending at the given ending position within the block. Since T is a three-dimensional array, its size is x*y*z where x is the number of patterns, y is the number of possible starting positions, and z is the number of possible ending positions. How big is T? (c) Not every entry in T is useful: some indexes may not correspond to valid combinations of a pattern, starting position, and ending position. Approximately what fraction of the space for T is wasted? 4. Suppose that the tree from question 1 is represented as a collection of nodes, each with a pointer to its first child (the topmost child in the drawing; e.g. the first child of A is B) and its next subling (e.g. the next sibling of C is D). Draw the binary tree that you would get from the same set of nodes and pointers by re-interpreting the first-child pointer as instead being the left child and re-interpreting the next-sibling pointer as instead being the right child.