Spring 2006 CSIE 922 U0110

Spring 2006 CSIE 922 U0110, Programming Assignment #1

Assigned	Mar 7, 2006
Due Date	Mar 20, 2006 by 24:00PM

1.

lConstruct the Cartesian tree of an array A of integers.

Definition of Cartesian tree of an array: The root of a Cartesian tree contains the index of the element which is the maximum of all the entries in the array.

The left and right children of the root are the roots of recursively constructed Cartesian trees of the left and right subarrays respectively.

2.

Minimum Requirements:

Input: Allow the user to enter a point list P= p₁, p₂, ..., p_n , where p_i= (x_i,y_i).

Preprocessing step: pre-process the input point list p₁, p₂, ..., p_n , where p_i= (x_i,y_i), such that the input array is y₁, y₂, ..., y_n and x_i is converted into integer i for index i, which reflects the order in which the points are entered.

Initial Output: After the preprocessing step, display the input as a list of points q₁, q₂, ..., q_n, where q_i= (i,y_i)

Final Output: Cartesian Tree of P, as a labelled graph, in which each node v has a label, (i,y_i) if v corresponds to point q_i.

Output: You must produce the Cartesuan tree Cart(y₁, y₂, ..., y_n).

Intermediate Results Output: To show how your algorithm behaves, you may want to show the intermediate results step by step by producing the Cartesian tree Cart(y₁, y₂, ..., y_i) at each step i, using the dialog box. For instance, if you return "yes", it will output Cart(y₁, y₂, ..., y_i+1), otherwise it will output Cart(y₁, y₂, ..., y_n).

3.

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. In addition to the running code, you must include the pseudo-code, and give the timing analysis of your algorithm. Note that the brute force algorithm is not allowed.

4.

Any effort that is beyond the minimum requirement will be recorded for extra credit consideration at the end of this semester. For instance, use the Cartesian tree to solve the least common ancestor (LCA) problem of any two nodes of Cart(y₁, y₂, ..., y_n), where the input to the LCA problem is a pair of integers, representing the indices of the array.