The University of Melbourne
School of Computing and Information Systems COMP20005 Engineering Computation Semester 2, 2018
Assignment 1
Due: 4:00pm Wednesday 19th September 2018
1 Learning Outcomes
In this assignment you will demonstrate your understanding of loops and if statements by writing a program that sequentially processes input data. You are also expected to make use of functions and arrays (strings).
2 The Story…
Vehicle trajectories provide insights for improving the transport system, such as understanding people’s commute patters, identifying traffic congestions, detecting bottlenecks of the road network, etc. Figure 1 below illustrates trajectories of 50 trucks delivering concrete to several construction sites around Athens, Greece, where each tra- jectory is illustrated with a line of a different colour.
Figure 1: Truck trajectories
A truck trajectory is represented by a sequence of location points of the truck reported at different time. Here, we show an example trajectory that consists of location points reported at a 30-second interval. Every location point (a line) has five columns, which represent the date (day/month/year), time (hour:minute:second), latitude, longitude, and unique id (6 characters) of the location point, respectively.
10/9/02 9:15:59 23.845089 38.018470 DXUYHu 10/9/02 9:16:29 23.845179 38.018069 tKoPTx 10/9/02 9:16:59 23.845530 38.018241 JPQbNb 10/9/02 9:17:29 23.845499 38.017440 aEWdXS 10/9/02 9:17:59 23.844780 38.015609 gqeEjx 10/9/02 9:18:29 23.844780 38.014018 aQArkX 10/9/02 9:18:59 23.844869 38.012569 fhQIAS 10/9/02 9:19:29 23.845360 38.011600 BhngfQ 10/9/02 9:19:59 23.845550 38.010650 rgwehm 10/9/02 9:20:29 23.845100 38.010478 jdBgpN
For example, the first line of the sequence represents a location point reported at 9:15:59 on 10/9/02 with a coordinate of ⟨23.845089, 38.018470⟩. This data point has a unique id of “DXUYHu”.
1
3 Your Task
In this assignment, your task is to analyse properties such as length and vehicle speed of a trajectory. You will be given a sequence of location points that represent a trajectory like the one shown above. Particularly, each line of the sequence contains the information of a location point separated by spaces (‘ ’), including the date (three integers in the format of day/month/year, between 1/1/02 and 1/9/18), time (three integers in the format of hour:minute:second, between 0:0:0 and 23:59:59), latitude (a real number with 6 digits after the decimal point), longitude (a real number with 6 digits after the decimal point), and the unique id (a 6-character string containing only English letters) of the location point.
You may assume that the sequence will always be correctly formatted and contain at least 2 and at most 99 location points.
Your task is to write a program that reads the sequence and outputs statistics calculated on it. The assignment consists of the following four stages (Stage 4 is for a challenge and is optional).
3.1 Stage 1 – Processing the First Location Point (Marks up to 3/10)
You can complete this stage without using strings. However, you may also use strings if you are confident that you will be proceeding to Stage 3.
Write a program that reads the first line of the input data and prints out for the first location point: the latitude, the longitude, the date, and the time.
The output of this stage given the above sample input should be (where “mac:” is the command prompt):
mac: ./assmt1 < test0.txt Stage 1 ========== Trajectory starting point: <23.845089, 38.018470> Trajectory starting time: 09:15:59
Trajectory starting date: 10/09/02
Your program output should follow the format of the above sample output. Here, the leading 0’s in the output integers can be achieved using “%02d” in the formating string of the printf() function call.
As this example illustrates, the best way to get data into your program is to save it in a text file (with a “.txt” extension, jEdit can do this), and then execute your program from the command line, feeding the data in via input redirection (using <).
In your program, you will still use the standard input functions such as scanf() or getchar() to read the data. Input redirection will direct these functions to read the data from the file, instead of asking you to type it in by hand. This will be more convenient than typing in the test cases manually every time you test your program. Our auto-testing system will feed input data into your submissions in this way as well. To simplify the assessment, your program should not print anything except for the data requested to be output (as shown in the output example).
Note that we will provide a sample test file “test0.txt” in LMS. You may download this file directly and use it to test your code before submission. This file is created under MacOS. Under Windows systems, the entire file may be displayed in one line if opened in the Notepad app. You do not need to edit this file to add line breaks. The ‘\n’ characters are already contained in the file. They are not displayed properly but the scanf() and getchar() functions in C can still recognise them correctly.
3.2 Stage 2 – Processing the Rest of the Location Points (Marks up to 7/10)
You can complete this stage without using strings. However, you may also use strings if you are confident that you will be proceeding to Stage 3.
Now modify your program so that it prints out the length (in metres) and the average travel speed (in metres per second, assuming 30 seconds per segment) between every two consecutive location points (that is, a trajectory segment). On the same sample input data, the additional output for this stage should be as follows (your program output should follow the same format).
2
Stage 2 ========== Trajectory segment 01: length: 041.99, speed: 01.40 Trajectory segment 02: length: 042.77, speed: 01.43 Trajectory segment 03: length: 081.54, speed: 02.72 Trajectory segment 04: length: 202.66, speed: 06.76 Trajectory segment 05: length: 161.81, speed: 05.39 Trajectory segment 06: length: 147.70, speed: 04.92 Trajectory segment 07: length: 112.66, speed: 03.76 Trajectory segment 08: length: 098.90, speed: 03.30 Trajectory segment 09: length: 053.01, speed: 01.77
Here, trajectory segment 01 is the segment between the 1st and the 2nd location points in the input sequence; trajectory segment 02 is the segment between the 2nd and the 3rd location points in the input sequence; …; tra- jectory segment 09 is the segment between the 9th and the 10th location points in the input sequence.
You may assume that the length is between 0 and 1000 (exclusive). You should print three and two digits before and after the decimal point for the length, respectively. You should print two digits both before and after the decimal point for the average travel speed.
To calculate the length of a trajectory segment, you need to calculate the distance between two location points. Given the coordinates of two points p1 = ⟨lat1,long1⟩ and p2 = ⟨lat2,long2⟩, where lati and longi (i = 1,2) represent the latitude and the longitude, the distance (in metres) between p1 and p2, represented by dist(p1,p2), is calculated based on the haversine formula as follows.
dist(p1, p2) = 6371000 · angle distance, where
angle distance = 2 · atan2(sqrt(chord length), sqrt(1 − chord length)), chord length = sin2(to radian(lat2 − lat1)/2)+
cos(to radian(lat1)) · cos(to radian(lat2)) · sin2(to radian(long2 − long1)/2)
(1)
In the equation above, to radian(x) = x · (3.14159/180) is a function that converts a latitude or longitude co- ordinate x to its radian value. You need to implement this function and define the constants properly in your code. Note that you should not use the constant M_PI provided by the math.h library as it is not supported by the assignment submission server under the assignment compilation settings.
The functions atan2(), sqrt() sin(), and cos() are provided by the math.h library. If you use this library, make sure to add the “-lm” flag to the “gcc” command at compilation.
Given the length of a trajectory segment as calculated by dist(p1,p2), the average travel speed of the segment, speed(p1,p2), is calculated as follows, where 30 (seconds) is the travel time of every trajectory segment.
speed(p1, p2) = dist(p1, p2)/30 (2)
In the example output above, 041.99 is the distance between the first two location points, ⟨23.845089, 38.018470⟩ and ⟨23.845179, 38.018069⟩, as calculated using the haversine formula above, and 01.40 is the corresponding average travel speed calculated by 041.99/30.
Note that you should write functions to process this stage where appropriate. 3.3 Stage 3 – Overall Reporting (Marks up to 10/10)
To complete this stage, you will need to use strings to store location point ids. If you have completed Stages 1 and 2 without strings, you should save a copy of that version of your program into a separate file, as an insurance policy that can be submitted again later if you are unable to get your Stage 3 solution operational.
The output from this stage is the total number of trajectory segments and the trajectory segment with the longest length. In the case of ties, the segment appearing earlier in the trajectory should be output.
Stage 3 ========== Number of trajectory segments: 9 Trajectory segment with longest length: [aEWdXS, gqeEjx]
3
In the example input above, trajectory segment 04 has the longest length. This trajectory segment is formed by the 4th and 5th location points with ids “aEWdXS” and “gqeEjx”. Note that there is a final newline (‘\n’) at the end of Stage 3 output.
Hint: You may need to use strings to keep track of the location point ids.
Wherever appropriate, code should be shared between the stages through the use of functions. In particular, there should not be long stretches of repeated code appearing in different places in your program. Further examples showing the full output that is required are provided on the LMS.
3.4 Stage 4 – For a Challenge (and Not for Submission)
For a challenge, try printing out the trajectory location points sorted in the ascending order of their latitude values (if there is a tie, break the tie by the location point id). But please don’t submit these programs.
4 Submission and Assessment
This assignment is worth 10% of the final mark. A detailed marking scheme will be provided on the LMS.
You need to submit all your code in one file named assmt1.c for assessment; detailed instructions on how to submit will be posted on the LMS once submissions are opened. Submission will NOT be done via the LMS; instead you will need to log in to a Unix server and submit your files to a software system known as submit. You can (and should) use submit both early and often – to get used to the way it works, and also to check that your program compiles correctly on our test system, which has some different characteristics to the lab machines. Only the last submission made before the deadline will be marked.
You will be given a sample test file test0.txt and the sample output test0-output.txt. You can test your code on your own machine with the following command and compare the output with test0-output.txt:
mac: ./assmt1 < test0.txt /* Here ‘<’ feeds the data from test0.txt into assmt1 */
Note that we are using the following command to compile your code on the submission server.
gcc -Wall -lm -std=c99 -o assmt1 assmt1.c
The flag “-std=c99” enables the compiler to use a more modern standard of the C language – C99. To ensure that your submission works properly on the submission server, you should use this command to compile your code on your local machine as well.
You may discuss your work with others, but what gets typed into your program must be individual work, not copied from anyone else. Do not give hard copy or soft copy of your work to anyone else; do not “lend” your memory stick to others; and do not ask others to give you their programs “just so that I can take a look and get some ideas, I won’t copy, honest”. The best way to help your friends in this regard is to say a very firm “no” when they ask for a copy of, or to see, your program, pointing out that your “no”, and their acceptance of that decision, is the only thing that will preserve your friendship. A sophisticated program that undertakes deep structural analysis of C code identifying regions of similarity will be run over all submissions in “compare every pair” mode. See https://academichonesty.unimelb.edu.au for more information.
Deadline: Programs not submitted by 4:00pm Wednesday 19th September 2018 will lose penalty marks at the rate of 1.5 marks per day or part day late. Late submissions after 4:00pm Friday 21st September 2018 will not be accepted. Students seeking extensions for medical or other “outside my control” reasons should email the lecturer at jianzhong.qi@unimelb.edu.au. If you attend a GP or other health care professional as a result of illness, be sure to take a Health Professional Report form with you (get it from the Special Consideration section of the Student Portal), you will need this form to be filled out if your illness develops into something that later requires a Special Consideration application to be lodged. You should scan the HPR form and send it in connection with any non-Special Consideration assignment extension requests.
And remember, C programming is fun!
⃝c 2018 The University of Melbourne Prepared by Jianzhong Qi
4