Reference no: EM133684353

Foundations of Algorithms

Learning Outcomes
In this assignment, you will demonstrate your understanding of arrays, pointers, input processing, and functions. You will also extend your skills in terms of code reading, program design, testing, and debugging.

The Story...
Given an array of n 1-dimensional values, we have learned that sorting the array will enable a fast O(log2 n)- time search to look up for a search key (that is, a number to be located in the array). In this assignment, we will extend our search capability to an array of 2-dimension values, where the ordering is less obvious.

Your Task

You will be given a skeleton code file named program.c for this assign- ment. The skeleton code file contains a main function that has been completed (which you do not have to modify unless you want to). There are a few other functions which are incomplete. You need to add code to complete the functions for the following tasks.

The given input to the program consists of 15 lines of numbers as follows:

The first 10 lines contains the IDs (unique integers) and coordinates (real numbers) of 50 POI records separated by ‘;', to run our query algorithms upon. The POI records are sorted by their IDs in ascending order, and their IDs are always from 0 to 49 to simplify the assignment. Each line contains five POI records. For the sample input shown below, the first record has ID 0, and its coordinates in the x- and y-dimensions are 16.4 and 69.4, respectively.

The next five lines represent the queries. Each line contains four real numbers representing a query range (xlb, ylb, xub, yub), where xlb and ylb represent the lower bounds in the x- and y-dimensions of the query range, while xub and yub represent the respective upper bounds. Intuitively, each query range is a rectangle whose bottom left corner is at (xlb, ylb) and top right corner is at (xub, yub). You may assume that xlb < xub and ylb < yub always hold.

You may assume that the test data always follow the format above, and that each coordinate value and query range bound is in the range of (0, 100). No input validity checking is needed. See below for a sample input.

Stage 1: Read the Input and Answer the First Query
Your first task is to understand the skeleton code. Then, you should add code to the stage_one function to
(1) read input POI IDs and coordinates into the arrays ids and coordinates, respectively, and read query ranges into queries, (2) identify all POIs within the first query range using linear search, and (3) print out such POIs (print "none" if no such POIs can be found).
The output for this stage given the above sample input should be (where "mac:" is the command prompt):

Hint: To test if a point at (x, y) is within a query range (xlb, ylb, xub, yub), we test the following inequalities:
xlb ≤ x ≤ xub and ylb ≤ y ≤ yub (1)
In the sample input above, for POI #4 at (15.4, 22.3) and the first query range (11.8, 3.5, 53.5, 28.5), we have:
11.8 ≤ 15.4 ≤ 53.5 and 3.5 ≤ 22.3 ≤ 28.5
Thus, POI #4 is within the first query range and is part of the Stage 1 output. The same applies for POI #18.
As this example illustrates, the best way to get data into your program is to edit it in a text file (with a ".txt" extension, any text editor can do this), and then execute your program from the command line, feeding the data in via input redirection (using <). In the program, we will still use the standard input functions such as scanf to read the data fed in from the text file. Our auto-testing system will feed input data into your submissions in this way as well. You do not need to (and should not ) use any file operation functions such as fopen or fread. To simplify the assessment, your program should not print anything except for the data requested to be output (as shown in the output example).
You should plan carefully, rather than just leaping in and starting to edit the skeleton code. Then, before moving through the rest of the stages, you should test your program thoroughly to ensure its correctness.
You should create sub-functions to complete the tasks. As stated in the marking rubric, you need to create at least two self-defined functions in your final submission for the assignment.

Stage 2: Sort and Query POIs by the x-coordinates
In Stage 1, we have examined all POI records to identify those within a query range. In the following stages, we aim to establish some ordering over the POIs, such that the unpromising POIs can be filtered without being examined, and query processing can be accelerated. For Stage 2, we will start by ordering the POIs by their x-coordinates.
Stage 2.1. Modify the given sort_by_x function, such that it takes the arrays of ids and coordinates as the input, and sorts both arrays based on the x-coordinates of the POIs in ascending order (that is, increasing order) with the insertion sort algorithm. For simplicity, you may assume that the x-coordinates of all input POIs are unique (in reality, if there are repeating x-coordinates, we can further sort by the y-coordinates). The stage_two function calls the modified sort_by_x function and performs the sorting.
Stage 2.2. Now further add code to the stage_two function to process all the input queries. For each query, we start with a linear scan (Scan 1) to find the POI with the smallest x-coordinate that is greater than or equal to xlb of the query range. Let us call this POI the lower bound POI. From this POI, we continue with the linear scan (Scan 2), until we reach a POI whose x-coordinate exceeds xub of the query range. For each POI visited during Scan 2, we examine whether it is within the query range in the y-dimension (we call this a POI-in-query test ), if so, it is part of the query answer and is outputted.
The output for this stage is the IDs of the POIs within each query, and the number of POI-in-query tests run for each query. For example, given the above sample input, the sample output of this stage is:

Stage 2
==========
POIs in Q0: 4 18; No. POI-in-query tests: 17 POIs in Q1: none; No. POI-in-query tests: 11
POIs in Q2: 33 39 26 27 15; No. POI-in-query tests: 24 POIs in Q3: none; No. POI-in-query tests: 1
POIs in Q4: 38 40 9 11 43; No. POI-in-query tests: 16
For example, as shown in Figure 2, for Q0, there are 17 points between xlb and xub (that is, the two vertical edges) of Q0. Thus, 17 POI-in-query tests need to be run to find the two POIs #4 and #18 within the query range. Now the number of POI-in-query tests per query is just up to 24 (for the five input queries), that is, fewer than half of all POIs, rather than examining all POIs for a query as done in Stage 1.

Stage 3: Sort POIs by Coordinates of Both Dimensions

Stage 3 further incorporates the y-coordinates into POI ordering. Figure 3 illustrates the idea. We partition the space with an m m regular grid. In this assignment, m = 8. A curve (the black dotted line in the figure) goes through each cell in the grid exactly once. The order that the curve goes through the cells gives a curve value for each cell. For example, as shown in the figure, the bottom left cell has a curve value of 0. The cell to its right has a curve value of 1, while the cell above it has a curve value of 2. The top right cell has a curve value of 63 (as there are 8 × 8 = 64 cells in total).

In this stage, you will add code to the stage_three function to calculate the curve values for the POIs (by calling the given cal_curve_value function with proper values of col num and row num), and sort the POIs by their curve values in ascending order - if there is a tie in the curve values, the POI with a smaller ID should be listed earlier. You may create another sorting function again based on the insertion sort algorithm. Hint: You may need to use the array curve_values to store the curve values for the POIs.

Stage 4: Query POIs by Curve Values

This stage implements a query algorithm with the curve values, by adding code to the stage_four function.

Our query algorithm is based on the following observation. Consider a query range (xlb, ylb, xub, yub). Let the curve value of the bottom left corner point (xlb, ylb) be vlb, and that of the top right corner point (xub, yub) be vub (these curve values can be calculated in the same way as in Stage 3 using the corner point coordinates). Then, for any POI within the query range, its curve value must be in the range of [vlb, vub]. For example, given query Q0 in Figure 3, vlb = 0 and vub = 24. The curve values of the two POIs in Q0 are 1 and 3, which are both in [0, 24].

Based on the observation, for each query range, the query algorithm runs as follows:

Step 1. First, calculate and output vlb and vub (use %02d for formatting). Then, run a binary search over the curve_values array produced in Stage 3 to locate the curve value greater than or equal to vlb that is ranked the earliest in the array. Let the POI corresponding to this curve value be the curve value lower bound POI.

Step 2. Run a linear scan over the array of POI coordinates (which has been sorted by the curve values in Stage 3) starting from the curve value lower bound POI, until reaching a POI whose curve value exceeds vub. For each POI visited during the scan, we examine whether it is within the query range (that is, to run POI-in-query tests - this time, we need to test the coordinates in both dimensions), and if so, it is part of the query answer and its ID is outputted. At the end of this step, we also output the number of POI-in-query tests run, like we did in Stage 2.

Note: You should adapt the binary_search function included in the skeleton code for Step 1 above, to output the curve_values array elements that have been compared with during the search process. For marking purposes, you are not allowed to use binary search code from other sources, or to create your own binary search functions from scratch. If you are not confident with your binary search implementation, you can replace it with a linear search for the same purpose. This will cost a 2-mark deduction (the full mark of the assignment becomes 18) but will not impact the rest of your assignment implementation.