Microsoft Word - Programming Assignment 3.docx
Programming Assignment 3, COP 3502
For this assignment you have to write a c program that will utilize the merge sort, insertion sort, and binary
search algorithm.
Please include the following lines in the beginning of your code to declare that the code was written by you:
* COP 3502C Programming Assignment 3
This program is written by: Your Full Name */
Sharing this assignment description (fully or partly) as well as your code (fully or partly) to anyone/anywhere is
a violation of the policy. I may report such incidence to office of student conduct and an investigation can easily
trace the student who shared/posted it. Also, getting a part of code from anywhere will be considered as
cheating.
Any coding help/debugging help should be taken during office hours.
For sending email, you can send the email to both TAs and cc the instructor. We will try to reply as soon as
possible.
Problem Scenario
You are spending most of your time at home in this pandemic. It is of most importance for people to be aware
of where other people, who are infected with COVID-19 are, and who they've been near. Keeping track of this
information is known as "contact tracing".
Your area can be modeled on the Cartesian plane. You are located at the point (x, y). In addition, you have the
Cartesian coordinates of all people cu
ently infected with COVID-19. What you would like to do is write a
program that sorts these locations based on their distance from you, followed by handling queries. The queries
are of the form of a point you are thinking of visiting. Your program should identify if someone who is infected
is at that location, and if so, what their rank is on the sorted list of infected people. If no one is infected at that
location, you should co
ectly identify this.
Implementation Restrictions
1. You must use a specified combination of Merge Sort and Insertion Sort to sort the point data. Specifically, for
each input case, a threshold value, t, will be given. If the subsection of the a
ay to sort has t or fewer values to
sort, Insertion Sort should be used. Otherwise, Merge Sort should be used. Further details about the comparison
used for the sorting are below.
2. You must store your coordinates in a struct that contains two integer fields. You can add more fields if
needed.
3. You must implement a ReadData() function that reads the required data from the assignment3input.txt file
and return the points to be sorted.
4. You must write a function compareTo which takes in two pointers, ptrPt1 and ptrPt2, to coordinate structs
and returns a negative integer if the point pointed to by ptrPt1 is closer to you than the point pointed
to by ptrPt2, 0 if the two locations pointed to by both are identical locations, and a positive integer if the point
pointed to by ptrPt1 is farther from you than the point pointed to by ptrPt2. Exceptions to this will be when the
two pointers are pointing to points that are the same distance from you, but are distinct points. In these cases, if
ptrPt1's x coordinate is lower than ptrPt2's x coordinate, a negative integer must be returned. Alternatively, if
ptrPt1's x coordinate is greater than ptrPt2's x coordinate a positive integer must be returned. Finally, if the x
coordinate of both points is the same, if ptrPt1's y coordinate is lower than ptrPt2's y coordinate, a negative
integer must be returned. If ptrPt1's y coordinate is greater than ptrPt2's y coordinate, a positive integer must be
eturned.
5. Since your location must be used for sorting, please make the variable that stores your x and y coordinates
global. Your program should have no other global variables.
6. A Binary Search function must be used when answering queries.
7. Your sort function should take in the a
ay to be sorted, the length of the a
ay as well as the threshold value,
t, previously mentioned. This function should NOT be recursive. It should be a wrapper function. It means it
will call necessary sorting function from here.
8. The recursive sort function (you can call this mergeSort) should take in the a
ay, a starting index into the
a
ay, an ending index into the a
ay and the threshold value t. In this function, either recursive calls should be
made OR a call to an insertion sort function should be made.
The Problem
Given your location, and the location of each person who has COVID-19, sort the list by distance from you
from shortest to longest,
eaking ties by x-coordinate (lower comes first), and then
eaking those ties by y
coordinate (lower comes first).
After sorting, answer several queries about points in the coordinate plane. Specifically, determine if a query
point contains someone who is infected or not. If so, determine that person's ranking on the sorted list in
distance from you.
The Input
The first line of the input contains 5 integers separated by spaces. The first two of these values are x and y (|x|,
|y| ≤ 10000), representing your location. The third integer is n (2 ≤ n ≤ 106), representing the number of infected
people. The fourth integer is s (1 ≤ s ≤ 2x105), representing the number of points to search for. The last integer,
t (1 ≤ t ≤ 30), represents the threshold to be used for determining whether you run Merge Sort of Insertion Sort.
The next n lines of the input contain x and y coordinate values, respectively, separated by spaces, representing
the locations of infected people. Each of these values will be integers and the points will be distinct (and also
different from your location) and the absolute value of x and y for all of these coordinates will not exceed
10,000.
Then the next s lines of the file contain x and y coordinate values for searching. Both values on each line will be
integers with an absolute value less than or equal to 10,000.
The Output (to be printed to out.txt file)
The first n lines of output should contain the coordinates of the people infected, sorted as previously mentioned.
These lines should have the x-coordinate, followed by a space, followed by the y-coordinate.
The last s lines of output will contain the answers to each of the s queries in the input. The answer for a single
query will be on a line by itself. If the point queried contains an infected person, output a line with the following
format:
x y found at rank R
where (x, y) is the query point, and R is the one-based rank of that infected person in the sorted list. (Thus, R
will be 1 more than the a
ay index in which (x, y) is located, after sorting.)
If the point queried does NOT contain an infected person, output a line with the following format:
x y not found
Sample Input data in assignment3input.txt file (Note: Query points in blue for clarity.)
XXXXXXXXXX
3 1
-6 -2
-4 3
4 -4
2 4
-1 3
2 2
0 -5
-4 -2
-6 6
4 4
-2 4
0 5
-4 6
2 -1
3 1
0 -5
0 5
-6 7
Sample Output (out.txt)
2 2
-1 3
3 1
-4 -2
-2 4
2 4
-4 3
0 -5
0 5
4 -4
4 4
-6 -2
-4 6
-6 6
2 -1 not found
3 1 found at rank 3
0 -5 found at rank 8
0 5 found at rank 9
-6 7 not found
Additional Requirement:
You must have to use read data from assignment3input.txt file and write the result to out.txt file. file IO, Merge
sort, insertion sort, and binary search for your solution based on the requirement. Without using them, you will
get zero. The output must have to match with the sample output format.
There will be a deduction of 10% points if the code is not well indented and 5% for not commenting
important blocks.
As always, all the programming submission will be graded base on the result from Eustis. If your code does not
work in Eustis we will conclude that your code has an e
or even if it works in your computer.
Note that you can use
li
ary if you need. In that case you have to use –lm option while compiling
your code.
For example: $gcc filename.c -lm
Please see the lecture slides and uploaded codes for learning merge sort
and binary search and File I/O.
You can take help from the codes that I have uploaded. However, they should be typed by you and should be
modified as needed
XXXXXXXXXX
3 1
-6 -2
-4 3
4 -4
2 4
-1 3
2 2
0 -5
-4 -2
-6 6
4 4
-2 4
0 5
-4 6
2 -1
3 1
0 -5
0 5
-6 7