使用二叉搜索树的出租车和出租车辆出行数据集信息检索

Purpose
COMP20003 Algorithms and Data Structures Second (Spring) Semester 2019
[Assignment 1]
Taxi & For-Hire Vehicle Trip Dataset Information Retrieval using Binary Search Trees
Handed out: Friday, 23 of August Due: 8:00 AM, Monday, 9 of September
The purpose of this assignment is for you to:
• Increase your proficiency in C programming, your dexterity with dynamic memory allocation and your understanding of linked data structures, through programming a dictionary.
• Increase your understanding of how computational complexity can affect the performance of an algorithm by conducting orderly experiments with your program and comparing the results of your experimentation with theory.
• Increase your proficiency in using UNIX utilities.
Background
A dictionary is an abstract data type that stores and supports lookup of key, value pairs. For example, in a telephone directory, the (string) key is a person or company name, and the value is the phone number. In a student record lookup, the key would be a student ID number and the value would be a complex structure containing all the other information about the student.
A dictionary can be implemented in C using a number of underlying data structures. Any implemen- tation must support the operations: makedict a new dictionary; insert a new item (key, value pair) into a dictionary; search for a key in the dictionary, and return the associated value. Most dictionaries will also support the operation delete an item.
Your task
In this assignment, you will create a simple instance of a dictionary, and we’ll use it to look up infor- mation about for-hire vehicle trips in New York City.
There are two stages in this project. In the first stage you will code a dictionary in the C programming language, using a binary search tree as the underlying data structure. You will insert records into this dictionary from a file, and look up records by key. In the second stage, you will code additional func- tions to retrieve information from this dictionary. You will use a Makefile to direct the compilation of two separate executable programs, one for Stage 1 and one for Stage 2.
In both stages of the assignment, you will report on the number of key comparisons used for search and analyse what would have been expected theoretically. The report should cover each file used to initialize the dictionary.
You are not required to implement the delete functionality.
1

Stage 1 (7 marks)
In Stage 1 of this assignment, your Makefile will direct the compilation to produce an executable program called dict1. The program dict1 takes two command line arguments: the first argument is the name of the data file used to build the dictionary; the second argument is the name of the output file, containing the data located in the searches. The data file consists of an unspecified number of records, one per line, with the following information:
VendorID – Code to indicate the vendor which produced the record passenger count – Number of passengers
trip distance – Length of the trip in miles
RatecodeID – Code to represent the fare rate for the trip
store and fwd flag – Indicates whether trip records were stored locally PULocationID – TLC Taxi Zone where passengers were picked up DOLocationID – TLC Taxi Zone where passengers were dropped off
payment type – Code to indicate payment type (e.g., cash)
fare amount – Fare for the trip in USD extra – Extra charges in USD
mta tax – MTA tax in USD
tip amount – Tip in USD
tolls amount – Tolls in USD
improvement surcharge – Improvement surcharge in USD total amount – Total cost of the trip in USD PUdatetime – Date/time passengers were picked up DOdatetime – Date/time passengers were dropped off trip duration – Duration of the trip in minutes
This data comes from a publicly-available dataset released by the New York City Taxi & Limousine Commission. More information about the dataset can be found at: https://www1.nyc.gov/site/tlc/about/tlc-trip-record-data.page
The field <PUdatetime> is an alphabetic string representing the date and time of the taxi trip in the format YYYY-MM-DD HH:mm:ss (year-month-day hour:minute:second). The other columns can be treated simply as the associated <data> field. Build a data structure of strings to save the associated data collected about each taxi trip. The maximum size that any string can be is 128 characters. Each string is separated by a comma “,”. This is a standard csv format where the delimiter used is a comma.
The <PUdatetime> field will serve as the dictionary key, so the records will be sorted in temporal order. Note that because the datetime information is stored in lexicographical order, the values can be compared as strings (e.g., with strcmp()) to determine which trip is earlier/later. The <data> is the information sought during lookup.
In this assignment the search keys are not guaranteed to be unique – there are instances where mul- tiple taxis pick up passengers at exactly the same day and time. You should handle duplicates by implementing a linked list for items with same key.
For the purposes of this assignment, you may assume that the input data is well-formatted, that the input file is not empty, and that the maximum length of an input record (a single full line of the csv file) is 256 characters. This number could help you to determine the buffer size to use when reading the file.
In this first stage of the assignment, you will:
• Construct a binary search tree to store the information contained in the file specified in the
2

command line argument. Each record should be stored in a separate Node.
• Search the binary search tree for records, based on their keys. The keys are read in from stdin, i.e. from the screen.
For testing, it is often convenient to create a file of keys to be searched, one per line, and redirect the input from this file. Use the UNIX operator < to redirect input from a file.
• Examples of use:
– dict1 datafile outputfile then type in keys; or
– dict1 datafile outputfile < keyfile
• Your program will look up each key and output the information (the data found) to the output file specified by the second command line parameter. If the key is not found in the tree, you must output the word NOTFOUND.
The number of key comparisons performed during both successful and unsuccessful lookups should be written to stdout.
• Remember that the entries in the file do not necessarily have unique keys. Your search must locate and output all the data found for a matching key.
• Example output:
– output file (information):
2018-12-15 01:49:13 –> VendorID: 1 || passenger count: 1 || trip distance: 1.9 || RatecodeID: 1.0 || store and fwd flag: 0 || PULocationID: 79 || DOLocationID: 234 ||
payment type: 1 || fare amount: 9.5 || extra:
|| tolls amount: 0.0 || improvement surcharge:
2018-12-15 02:00:00 || trip duration: 10 ||
2018-12-15 01:49:13 –> VendorID: 1 ||
|| RatecodeID: 1.0 || store and fwd flag: 0 || PULocationID: 79 || DOLocationID: 114 ||
0.5 || mta tax: 0.5 || tip amount: 2.15 0.3 || total amount: 12.95 || DOdatetime:
passenger count: 1 || trip distance: 0.6
payment type: 1 || fare amount: 5.0 || extra: || tolls amount: 0.0 || improvement surcharge: 2018-12-02 01:53:38 || trip duration: 4 || 1901-11-06 12:03:14 –> NOTFOUND
– stdout (comparisons): 2018-12-15 01:49:13 –> 423
1901-11-06 12:03:14 –> 401
0.5 || mta tax: 0.5 || tip amount: 1.00 0.3 || total amount: 7.35 || DOdatetime:
Note that the key is output to both the file and to stdout, for identification purposes. Also note that the number of comparisons is only output at the end of the search, so there is only one number for key comparisons per key, even when multiple records have been located for that key.
The format need not be exactly as above. Variations in whitespace/tabs are permitted. The number of comparisons shown above was made up; do not take it as an example of a correct result.
3

Stage 2 (2 marks)
In Stage 2, you will code a function which takes a taxi zone ID number as as input and returns to the output file all of the <PUdatetime> keys from records which match the <PUlocationID>, using in-order tree traversal. The keys should be output in sorted temporal order (that is, earlier records should be printed first). If no records with the requested <PUlocationID> exist in the database, this function should write the string NOTFOUND to the output file. As in Stage 1, the the number of comparisons made during the search should be written to stdout.
The <PUlocationID> is an unsigned integer between 1 and 265 which indicates where the taxi picked up passengers. You can find maps of the zones at the dataset website linked above, but you do not need these maps for the assignment – you can treat the zone as simply an integer. You may store the <PUlocationID> as a separate field in your struct, or you can check for the matching <PUlocationID> inside the <data> field. As in Stage 1, you should handle duplicate keys by im- plementing a linked list for items with same key. Note that this means there may be more than one matching <PUlocationID> for a single key. If this is the case, the key should be output multiple times to reflect the number of matches.
You should compile your code using a Makefile to produce an executable program called dict2. The program dict2 takes two command line arguments: the first argument is the name of the data file used to build the dictionary; the second argument is the name of the output file, containing the data located in the searches. You may reuse your record insertion code from Stage 1 to build the dictionary from the datafile in Stage 2.
• Examples of use:
– dict2 datafile outputfile then type in location IDs; or
– dict2 datafile outputfile < idsfile • Example output:
– output file (information):
79 –> 2018-12-08 19:36:57 79 –> 2018-12-08 21:22:08 79 –> 2018-12-15 01:49:13 79 –> 2018-12-15 01:49:13 79 –> 2018-12-23 17:26:42
– stdout (comparisons): 79 –> 1528
The number of comparisons shown above was made up; do not take it as an example of a correct result.
Experimentation (4 marks)
You will run various files through your program to test its accuracy and also to examine the number of key comparisons used when searching different files. You will report on the key comparisons used by your Stage 1 dictionary dict1 for various data inputs and the key comparisons used by your Stage 2 dictionary dict2 for various data inputs too. You will compare these results with what you expected based on theory (big-O) for these algorithms and data structure.
4

Your experimentation should be systematic, varying the size and characteristics of the dataset files you use (e.g. sorted or random), and observing how the number of key comparisons varies. Repeating a test case with different keys and taking the average can be useful.
SomeusefulUNIXcommandsforcreatingtestfileswithdifferentcharacteristicsincludesort, sort -R (man sort for more information on the -R option), and shuf. You can randomize your input data and pick the first x keys as the lookup keywords.
If you use only keyboard input for searches, it is unlikely that you will be able to generate enough data to analyze your results. You should familiarize yourself with the powerful UNIX facilities for redirecting standard input (stdin) and standard output (stdout). You might also find it useful to familiarize yourself with UNIX pipes ‘|’ and possibly also the UNIX program awk for processing structured output. For example, if you pipe your output into echo ‘‘abc:def’’ | awk -F ’:’ ’{print $1}’, you will output only the first column (abc). In the example, -F specifies the de- limiter. Instead of using echo you can use cat filename.csv | awk -F ’;’ ’{print $1}’ which will print only the first column of the filename.csv file. You can build up a file of numbers of key comparisons using the shell append operator >>, e.x. your command >> file to append to.
You will write up your findings and submit your results separately through the Turnitin system. You will describe your results from each stage and also compare these to what you know about the theory of binary search trees.
Tables and graphs are useful presentation methods. Select only informative data; more is not always better.
You should present your findings clearly, in light of what you know about the data structures used in your programs and in light of their known computational complexity. You may find that your results are what you expected, based on theory. Alternatively, you may find your results do not agree with theory. In either case, you should state what you expected from the theory, and if there is a discrep- ancy you should suggest possible reasons. You might want to discuss space-time trade-offs, if this is appropriate to your code and data.
You are not constrained to any particular structure in this report, but a useful way to present your findings might be:
• Introduction: Summary of data structures and inputs. • Stage 1:
– Data (number of key comparisons) – Comparison with theory
• Stage 2:
– Data (number of key comparisons)
– Comparison with theory • Discussion
Implementation Requirements
The following implementation requirements must be adhered to:
• You must code your dictionary in the C programming language.
5

• Youmustcodeyourdictionaryinamodularway,sothatyourdictionaryimplementationcouldbe used in another program without extensive rewriting or copying. This means that the dictionary operations are kept together in a separate .c file, with its own header (.h) file, separate from the main program.
• Your code should be easily extensible to allow for multiple dictionaries. This means that the func- tions for insertion, search, and deletion take as arguments not only the item being inserted or a key for searching and deleting, but also a pointer to a particular dictionary, e.g. insert(dict, item).
• Your program should store strings in a space-efficient manner. If you are using malloc() to createthespaceforastring,remembertoallowspaceforthefinalendofstring‘\0’ (NULL).
• A Makefile is not provided for you. The Makefile should direct the compilation of two separate programs: dict1 and dict2. To use the Makefile, make sure it is in the same directory of your code, and type make dict1 to make the dictionary for Stage 1 and make dict2 to make the dictionary for Stage 2. You must submit your makefile with your assignment. Hint: If you havent used make before, try it on simple programs first. If it doesn’t work, read the error messages carefully. A common problem in compiling multifile executables is in the included header files. Note also that the whitespace before the command is a tab, and not multiple spaces. It is not a good idea to code your program as a single file and then try to break it down into multiple files. Start by using multiple files, with minimal content, and make sure they are communicating with each other before starting more serious coding.
Data
The data files are provided at /home/shared/assg1/datafiles/ on JupyterHub. The data for- mat is as specified above in Stage 1.
No attempt has been made to remove or prevent duplicate keys in the original files, so you should expect duplicate keys. Our script only formatted the data correctly making sure it complies with a csv standard specification.
Resources: Programming Style (2 Marks)
Two locally-written papers containing useful guidelines on coding style and structure can be found on the LMS Resources → Project Coding Guidelines, by Peter Schachte, and below and adapted version of the LMS Resources → C Programming Style, written for Engineering Computation COMP20005 by Aidan Nagorcka-Smith. Be aware that your programming style will be judged with 2 marks.
1 2 3 4 5 6 7 8 9
10 11 12 13 14 15
/** ***********************
* * * * * * * * * * * * */
C Programming Style for Engineering Computation
Created by Aidan Nagorcka−Smith ([email protected]) 13/03/2011 Definitions and includes
Definitions are in UPPER CASE
Includes go before definitions
Space between includes , definitions and the main function .
Use definitions for any constants in your program, do not just write them in.
Tabs may be set to 4−spaces or 8−spaces , depending on your editor . The code Below is “gnu ‘ ‘ style . If your editor has “bsd ‘ ‘ it will follow the 8−space
style . Both are very standard .
6

/**
* GOOD:
*/
#include <stdio.h>
#include <stdlib .h>
#define MAX STRING SIZE 1000 #define DEBUG 0
int main( int argc, char …
/**
* BAD:
*/
**argv) {
/* Definitions and includes are mixed up */
#include <stdlib .h>
#define MAX STING SIZE 1000
/* Definitions are given names like variables */
#define debug 0 #include <stdio.h>
/* No spacing between includes , definitions and main function*/
int main( int argc, char **argv) { …
/** ***************************** * Variables
* Give them useful lower case names or camelCase . Either is fine , * as long as you are consistent and apply always the same style. * Initialise them to something that makes sense.
*/
/**
* GOOD: lower case
*/
int main( int argc, char
int i = 0;
int num_fifties = 0 ; int num_twenties = 0 ; int num_tens = 0;
…
/**
* GOOD: camelCase
*/
int main( int argc, char
int i = 0;
int numFifties = 0; int numTwenties = 0 ; int numTens = 0;
…
/**
* BAD:
*/
int main( int argc, char
**argv) {
**argv) {
**argv) {
/* Variable not initialised − causes a bug because we didn’t remember to * set it before the loop */
int i;
/* Variable in all caps − we’ ll get confused between this and constants
16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81
7

*/
i n t NUM_FIFTIES = 0 ;
/* Overly abbreviated variable names make things hard. */ int nt = 0
while (i < 10) { …
i++; }
…
/** ********************
* * * * * * * * * * * * */
Spacing :
Space intelligently , vertically to group blocks of code that are doing a specific operation , or to separate variable declarations from other code . One tab of indentation within either a function or a loop.
Spaces after commas.
Space between ) and { .
No space between the ** and the argv in the definition of the main function .
When declaring a pointer variable or argument, you may place the asterisk adjacent to either the type or to the variable name.
Lines at most 80 characters long.
Closing brace goes on its own line
/**
* GOOD:
*/
int main( int
int i = 0;
argc, char
**argv) {
for(i = 100; i >= 0; i−−) {
if (i > 0) {
printf(”%d bottles of beer, take one down and pass it around,” ” %d b o t t l e s o f b e e r . \ n ” , i , i − 1 ) ;
}else{
printf(”%d bottles of beer, take one down and pass it around.” ” We’re empty.\n”, i);
} }
return 0; }
/**
* BAD:
*/
/* No space after commas
* Space between the ** and argv in the main function definition * No space between the ) and { at the start of a function */ int main( int argc, char ** argv){
int i = 0;
/* No space between variable declarations and the rest of the function. * No spaces around the boolean operators */
for(i=100;i>=0;i−−) {
/* No indentation */
if (i > 0) {
/* Line too long */
printf(”%d bottles of beer, take one down and pass it around, %d
bottles of beer.\n”, i, i − 1); }else{
82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99
100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147
8

/* Spacing for no good reason. */
printf(”%d bottles of beer, take one down and pass it around.” ” We’re empty.\n”, i);
}
}
/* Closing brace not on its own line */ return 0;}
/** **************** * Braces :
* Opening
* Closing
* Closing
* closing */
/**
* GOOD:
*/
int main( int …
for (…) { …
}
return 0; }
/**
* BAD:
*/
int main( int …
braces go on the same line as the loop or function name braces go on their own line
braces go at the same indentation level as the thing they are
argc, char
**argv) {
argc, char
**argv) {
/* Opening brace on a different line to the for loop open */
for (…) {
…
/* Closing brace at a different indentation to the thing it ‘s
closing
*/
/* Closing brace not on its own line. */
return 0;} /** **************
* Commenting:
* Each program should have a comment explaining what it does and who created *it.
* Also comment how to run the program, including optional command line
* parameters .
* Any interesting code should have a comment to explain itself.
* We should not comment obvious things − write code that documents i t s e l f
*/
/**
* GOOD:
*/
}
148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213
9

/* change . c *
* Created by Aidan Nagorcka−Smith ([email protected]) 13/03/2011
*
* Print the number of each coin that would be needed to make up some
change
* that is input by the user
*
* To run the program type :
* ./ coins −−num coins 5 −−shape coins trapezoid −−output blabla . txt *
* To see all the input parameters, type: * ./coins −−help
* Options::
−−help
−−num coins arg −−shape coins arg −−bound arg (=1) −−output arg
int
i n t input_change = 0 ;
Show help message Input number of coins Input coins shape
Max bound on xxx, default value 1 Output solution file
* * * * * * */
main( int argc, char
**argv)
{
printf( ” Please input inclusive ) :\n” ) ;
of the
change
(0−99 cents
the value scanf(”%d”, &input_change);
printf(”\n”);
// Valid change values are 0−99 inclusive.
i f (input_change < 0 | | input_change > 99) {
printf( ” Input …
/**
* BAD:
not in the
range
0−99.\n” )
}
*/
/* No explanation of what the program is doing */
int main( int argc, char **argv) {
/* Commenting obvious things */
/* Create a int variable called input change to store the input from the
* user. */
i n t input_change ;
…
/** **************** * Code structure:
* Fail fast − input checks should happen first , then do the computation .
* Structure the code so that all error handling happens in an easy to read * location
*/
/**
* GOOD:
*/
i f ( input_is_bad ) {
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279
10

printf(”Error: Input was not valid. Exiting.\n”);
exit(EXIT_FAILURE) ; }
/* Do computations here */
…
/**
* BAD:
*/
i f ( input_is_good ) {
/* lots of computation here, pushing the else part off the screen.
*/
…
}else{
fprintf(stderr, ”Error: Input was not valid. Exiting.\n”); exit(EXIT_FAILURE) ;
}
280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298
Additional Support
Your tutors will be available to help with your assignment during the scheduled workshop times. Ques- tions related to the assignment may be posted on the Piazza forum, using the folder tag assignment1 for new posts. You should feel free to answer other students’ questions if you are confident of your skills.
A tutor will check the Discussion Forum regularly, and answer some questions, but be aware that for some questions you will just need to use your judgment and document your thinking. For example, a question like, How much data should I use for the experiments?, will not be answered; you must try out different data and see what makes sense.
In this subject, we’ll be supporting the shared JupyterHub system, its terminal and file editor. Your final program must compile and run on the shared JupyterHub instance.
Submission
You will need to make two submissions for this assignment:
• Your C code files (including your Makefile) will be submitted through the LMS page for this
subject: Assignments → Assignment 1 → Assignment 1: Code.
• Your experiments report file will be submitted through the LMS page for this subject: Assignments → Assignment 1 → Assignment 1: Experimentation. This file can be of any format, e.g. .pdf, text or other.
Program files submitted (Code)
Submit the program files for your assignment and your Makefile.
If you wish to submit any scripts or code used to generate input data, you may, although this is not
required. Just be sure to submit all your files at the same time.
Your programs must compile and run correctly on the shared JupyterHub instance. You may have de-
veloped your program in another environment, but it still must run on the JupyterHub at submission
11

time. For this reason, and because there are often small, but significant, differences between compil- ers, it is suggested that if you are working in a different environment, you upload and test your code on the shared JupyterHub instance at reasonably frequent intervals.
A common reason for programs not to compile is that a file has been inadvertently omitted from the submission. Please check your submission, and resubmit all files if necessary.
Experiment file submitted using Turnitin
As noted above, your experimental work will be submitted through the LMS, via the Turnitin system. Go to the LMS page for this subject: Assignments → Assignment 1 → Assignment 1: Experimentation and follow the prompts.
Your file can be in any format. Plain text or .pdf are recommended, but other formats will be ac- cepted. It is expected that your experimental work will be in a single file, but multiple files can be accepted. Add your username to the top of your experiments file.
Please do not submit large data files. There is no need to query every key on the dictionary. Assessment
There are a total of 15 marks given for this assignment, 7 marks for Stage 1, 2 marks for Stage 2, and 4 marks for the separately submitted Experimentation Stage. 2 marks will be given based on your C programming style.
Your C program will be marked on the basis of accuracy, readability, and good C programming struc- ture, safety and style, including documentation. Safety refers to checking whether opening a file returns something, whether mallocs do their job, etc. The documentation should explain all major design decisions, and should be formatted so that it does not interfere with reading the code. As much as possible, try to make your code self-documenting, by choosing descriptive variable names.
Your experimentation will be marked on the basis of orderliness and thoroughness of experimentation, comparison of your results with theory, and thoughtful discussion.
Plagiarism
This is an individual assignment. The work must be your own.
While you may discuss your program development, coding problems and experimentation with your classmates, you must not share files, as this is considered plagiarism.
If you refer to published work in the discussion of your experiments, be sure to include a citation to the publication or the web link.
Borrowing of someone elses code without acknowledgment is plagiarism. Plagiarism is considered a serious offense at the University of Melbourne. You should read the University code on Academic honesty and details on plagiarism. Make sure you are not plagiarizing, intentionally or unintentionally.
You are also advised that there will be a C programming component (on paper, not on a computer) in the final examination. Students who do not program their own assignments will be at a disadvantage for this part of the examination.
12

Administrative issues
When is late? What do I do if I am late? The due date and time are printed on the front of this document. The lateness policy is on the handout provided at the first lecture and also available on the subject LMS page. If you decide to make a late submission, you should send an email directly to the lecturer as soon as possible and he will provide instructions for making a late submission.
What are the marks and the marking criteria Recall that this project is worth 15% of your final score. There is also a hurdle requirement: you must earn at least 15 marks out of a subtotal of 30 for the projects to pass this subject.
Finally Despite all these stern words, we are here to help! There is information about getting help in this subject on the LMS pages. Frequently asked questions about the project will be answered in the LMS discussion group.
13