[15 marks] Background: A point (x1, y1) is said to dominate another point (x2, y2) in the plane if both x1 x2 and y1 y2 hold. For example, (5, 2) dominates (3, 1), but neither of the two points (3, 2) or (2, 5) dominates the other. A point p is a maximal point of a point set S if there does not exist another point in S that dominates p.

The problem: In this question, you are asked to write a program based on sorting that reports all the maximal points in a given point set. Note that this problem is useful for the support of certain new features of SQL (structured query language) for database systems.

How do we solve this problem? One of the most efficient solutions makes use of an algorithm design paradigm called reducing to known problems. Informally speaking, this paradigm means that when we encounter a new problem, we can try to solve it by making use of solutions to other problems that we already know how to solve.

The problem of finding all the maximal points can be solved by making use of solutions to the sorting problem. To see this, first sort all the points by x-coordinates in ascending order. Then, check all the points from right to left. Think of this question: What points should you report? I will state the answer in the next paragraph; I would however suggest you to try to figure out how by yourself first and then read the next paragraph to confirm whether your own solution is correct.

Here is the solution: sort all the points in ascending order by x-coordinate. Then check the points one by one from right to left, recording the largest y-coordinate seen so far. For each point, if its y-coordinate is larger than the largest y-coordinate of all the points to its right, report it as a maximal point. Note that the rightmost point is always a maximal point. Draw a figure yourself to see the correctness. To simplify your work, you can assume that x-coordinates are distinct.

You are asked to implement this solution. In your implementation, you can use any rea- sonable sorting algorithm including insertion sort and bubble sort (though you should know why they are not as efficient as better solutions), and you will not lose any marks if you do not implement the most efficient sorting algorithms. You are forbidden to use any existing C library functions that can be used to sort an array, such as qsort. You will lose a lot of marks if you do so.

No marks will be given if your solution is not based on sorting as specified above.

General Requirements: Use a5q2.c as the name of your C source code file. We will use the following command on bluenose to compile your program:

gcc -std=c99 -o max a5q2.c 

As many numbers have to be read from stdin to test your program, you are expected to use input redirection to read the input from a file. More precisely, you can run your program using the following command:

./max < max.in.0 In the above command, the file max.in.0 is a plain text file that contains the coordi-

nates of exactly ten points. This file has exactly ten lines, and each line contains two 4

integers. The first integer is the x-coordinate of a point, and the second integer is its y-coordinate. Hence, in this question, you just have to handle point sets of size 10 and you can assume that coordinates are int values.

For example, the following file max.in.0 contains coordinates of 10 points:

12 5 29 7 0 13 55 9 47 2 23 -5 -7 90 11 33 25 -24 21 7 

Your program should then find the maximal points among these 10 points, and report the maximal points in decreasing order of x-coordinates. To report a point, print its x-coordinate and y-coordinate in a single line, use exactly one space between these two values (this is the only space character in this line), and terminate this line with a newline character. For example, the output of the above example is expected to be

55 9 11 33 -7 90

Error Handling: No error handling is required. Testing: To test your program automatically, we will use it as a UNIX filter.

For the example above, we will test it using the following command in the directory containing the executable program:

./max < max.in.0 

To help you make sure that the output format of your program is exactly what this question asks for, several files are provided in the following folder on bluenose to show how exactly your program will be automatically tested:

/users/faculty/prof2132/public/a5test/ 

5

In this folder, open the file a5q2test to see the commands used to test the program with two test cases. The output files, generated using output redirection, are also given.

To check whether the output of your program on any test case is correct, redirect your output into a file, and use the UNIX utility diff (learned in Lab 3) to compare your output file with the output files in the above folder, to see whether they are identical.

Since these output files are given, we will apply a penalty to any program that does not strictly meet the requirement on output format. This includes the case in which your output has extra spaces, or has a missing newline at the end. Note that it is extremely important to use diff here, as the number of values in the output file is large.

We will use different test cases to test your program thoroughly. Therefore, construct a number of test cases to test your program thoroughly before submitting it.

Note: Since after sorting, all that is required to compute maximal points is essentially a linear scan, this means that our solution is as efficient as the sorting algorithm used in our implementation. As sorting is very well studied, this means that computing maximal points in this way is very efficient. As you may already know, the number of comparisons required of the best sorting algorithms is proportional to only n lg n.

This type of questions are typical technical interview questions for software developers (and your interviewer will not simply tell you the solution)