Spring 2006 CSIE 922 U0110, Programming Assignment #4

1. Solving LCA problem by ±1 RMQ. In programming assignment 1, we see that we can solve the RMQ by transforming it into a LCA problem of a Cartesian tree in amortized O(n) time. We will further come up an algorithm to solve the LCA problem of any rooted tree with n nodes in O(1) time in this assignment. Therefore, we can solve the RMQ in O(1) time by using this algorithm as well.

2. The Least Common Ancestor (LCA) problem can be defined as follows. Given a rooted tree T with n nodes, we want to preprocess T so that for any two nodes u and v of tree T, we can answer quickly the query LCA_T(u, v) which returns the least common ancestor of u and v in T. i.e. the node furthest from the root that is an ancestor of both u and v.
   
   The range minimum query (RMQ) can be defined as follows. Given an array A[1:n] of n real numbers, we want to preprocess A so that for any two indices i and j between 1 and n , we can answer quickly the query RMQ_A(i, j) which returns the the index of the smallest element in the subarray A[i:j].
   
   To solve the LCA problem, we observe that the LCA of nodes u and v is the shallowest node encountered between the visits to u and to v during a depth first search traversal of T and the depth between any two adjacent nodes in the depth first search traversal differ by +1 or -1. (Or consider traversing the tree to form an Euler tour by visiting each edge exactly twice. The depth of the root node is 0. Each time when you visit from a parent node to a child node, the depth of the child node is incremented by 1, and when you visit from a child node to its parent node, the depth of the parent node is decremented by 1.) Therefore, if we can solve the ±1 RMQ problem which is a RMQ problem such that the adjacent elements of input array A differ by +1 or -1, we can solve the LCA problem as well. You should first give an (S(n), Q(n)) = (O(n log n), O(1)) algorithm for the general RMQ problem and then give an (O(n), O(1)) algorithm for the ±1 RMQ problem by using the (O(n log n), O(1)) algorithm for the general RMQ problem. You can try to give the algorithms for the RMQ problem and ±1 RMQ problem by yourself or refer the Bender and Farach's paper to see whether you can modify their idea to come up the algorithms or not.

3. This assignment will consist of two parts: the first part is to solve the LCA problem by ±1 RMQ and the second part is to solve the RMQ by LCA using the programming assignment 1 as a subroutine.
   You may want to proceed as follows:

   1. Given an array A[1:n], convert it into a Cartesian Tree (programming assignment 1)

   2. Given a Cartesian Tree, convert into an array B[1:x] for some x such that the entries satisfy the ±1 property.

   3. Given an instance of RMQ problem, convert it into a corresponding instance of LCA problem.

   4. Given an instance of LCA problem, convert it into a corresponding instance of ±1 RMQ problem.

   5. Solve the instance of ±1 RMQ problem.

4. Minimum Requirements:

   Part A) Solving ±1 RMQ
   
   Input: Allow the user to enter a point list p₁, p₂, ..., p_n , where p_i = (x_i, y_i) such that x₁ £ x₂ £ ... £ x_n and y_i and y_i+1 differ by +1 or -1 (for visualization convenience, you may input p₁, p₂, ..., p_n such that y_i and y_i+1 differ by +10 or -10), and then you need to pre-process the input point list such that the input array A is the y-coordinates of the point list, y₁, y₂, ..., y_n.
   
   Output: You must highlight the point p_k such that k = ±1 RMQ_A(i, j) whenever the user choose points p_i and p_j and hit return.
   
   Part B) Transferring the RMQ to the LCA and solving the LCA by ±1 RMQ
   
   Input: Allow the user to enter a point list p₁, p₂, ..., p_n, where p_i = (x_i, y_i) and then you need to pre-process the input point list such that the input array A[1:n] is the y-coordinates of the point list, y₁, y₂, ..., y_n.
   
   Output: You must produce the Cartesian tree T = Cart(y₁, y₂, ..., y_i) by using the programming assignment 1 as a subroutine. You must highlight the node w and return its label such that w is LCA_T(u, v) in T whenever the user enters a query of two integers i and j, corresponding to the indexes of the input array A[1:n]

5. Your program should be written in C/C++ using object classes available in the library or new objects developed on your own. Documentation of your code is necessary.