Programming Homework Help

Let x, y, and z denote the three coordinate axes in the three dimensional space R3 . A point p ∈ R3 is specified by its coordinates along the three axes: p = (x(p), y(p), z(p)). For p, q ∈ R3 , we say that p is dominated by q, if x(p) ≤ x(q), y(p) ≤ y(q) and z(p) ≤ z(q). Let S = {p0, p1, . . . , pn−1} be a set of n points in R3 . pi ∈ S is called a maximal element of S, if pi is not dominated by any other element of S. The set of all maximal elements of S is denoted by maxima(S). The maxima problem is: Given S, find maxima(S). You will write an efficient program to solve this problem, using the C++ or Java Standard Library functions. One brute-force algorithm to solve this problem is as follows: Compare each point pi ∈ S against all the other points in S to determine if pi is dominated by any of those points; if pi is not dominated by any of them, add it to the output set maxima(S). This algorithm takes Θ(n) time for each point pi , for a total of Θ(n 2 ) time. You will implement an efficient algorithm that is expected to run in Θ(n log n) time. The program must be in C++ or Java only. This handout discusses the implementation in C++, using the Standard Template Library (STL). The algorithm consists of three steps. I. Input: The point set S is in an input file. The first line contains the value of n (the number of points). Following that, there will be n lines, each line containing the x, y and z coordinates of one point. The points must be read and stored in an array P OINT S[0..(n − 1)] of POINT objects. The P OINT S[i] object corresponds to point pi , and has four fields: the x, y and z-coordinates (all double); the boolean field maximal indicating whether or not the point is maximal. II. Sorting: Sort the points (i.e., the array P OINT S) according to their z-coordinates, and reindex them such that z(p0) ≤ z(p1) ≤ . . . ≤ z(pn−1). The sorting must be done using the sort library function: sort(POINTS, POINTS+n); this requires that you implement the operator x(q). If x(pi) > x(q), add pi to maxima(S); also, we need to update the BST so that it represents maxima2[i..n]. The update of the BST is done as follows: First, consider the nodes in the BST whose y-coordinates are less than y(pi), in decreasing order of their y-coordinates; delete them one-by-one, until you come across a point p with x(p) > x(pi). Finally, insert pi into the BST. Each insertion or deletion in a BST takes time Θ(height of the tree). To achieve the Θ(n log n) runtime, the above BST must be a height-balanced binary search tree: At any istant, the height of the tree is Θ(log of number nodes in the tree). One example of such a tree is Red-Black Tree (see Chapter 13 in the text book). You will use the STL data structure map. It is implemented as a Red-Black Tree. In the class, I will explain how to use map. Variable M axNum has the number of elements in M axima(S). Print out M axNum and M axima(S). For each point in M axima(S), also print out its array index (i.e., the index of the point in P OINT S array). Your program should be modular, and contain appropriate procedures/functions. No comments or other documentation is needed. Use meaningful names for all variables. You will run your program on 10 different sets of points; your program should have a loop for this. All the point sets are in the input file infile.txt. The name of your program file must be maxima.[cpp or java] (corresponding to C++ or Java programs, respectively); the name of your output file must be outfile.txt.