COMP9024 19T3
Assignment
Sydney Transport Planner
Data Structures and Algorithms
Change Log
We may make minor changes to the spec to addressclarify some outstanding issues. These may require minimal changes in your designcode, if at all. Students are strongly encouraged to check the change log regularly.
Version 1: Released on 30 October 2019
Objectives
The assignment aims to give you more independent, selfdirected practice with
advanced data structures, especially graphs
graph algorithms
asymptotic runtime analysis
Admin
Marks
3 marks for stage 1 correctness
5 marks for stage 2 correctness
2 marks for stage 3 correctness
1 marks for complexity analysis
1 mark for style
Total: 12 marks
Due
11:00:00am on Tuesday 19 November week 10
Late
2 marks 16.67 off the ceiling per day late
e.g. if you are 25 hours late, your maximum possible mark is 8
Aim
Your task is to write a program myTrain.c for finding an optimal train connection that takes into account a given arrival time and user preferences.
Input
Station names
Your program should start by prompting the user to input a positive number n followed by n lines, each containing the name of a train station. An example is:
.myTrain
Enter the number of stations: 3
Central
Parramatta
Chatswood
You may assume that:
The input is syntactically correct.
Station names require no more than 31 characters.
No station name will be input more than once.
Hint:
To read a single line with a station name you may use:
scanfs, station;station is a character arraystring variable
Trains
Next, your program should ask the user for the number m of trains running during a day, followed by m schedules. Each schedule requires the number of stops, k2, followed by k2 lines of the form:
hhmm
stationname
meaning that passengers can get on or off the train at that time hhhour, mmminute at that station. An example is:
Enter the number of trains: 2
Enter the number of stops: 3
0935
Parramatta
1002
Central
1030
Chatswood
Enter the number of stops: 2
1010
Central
1025
Chatswood
You may assume that:
The input is syntactically correct: 4 digits followed by a single space followed by the name of a station.
All times are valid and range from 0000 to 2359.
There are no overnight trains: Each train will reach its final stop before midnight.
Only valid station names that have been input before will be used.
Queries
After reading the network, your program should prompt the user to search for a connection:
From: Parramatta
To: Chatswood
Arrive by: 1230
Again you may assume that the input is correct: Only stations that have been entered before are used and a valid time is given.
If the user inputs done, then your program should terminate:
From: done
Thank you for using myTrain.
Stage 1 3 marks
For stage 1, you should demonstrate that you can read the input and generate a suitable data structure.
For this stage, all test cases will only use queries From, To, ArriveBy for which
there is only one train between From and To; and
this train is guaranteed to arrive on, or before, the requested time, ArriveBy.
Hence, all you need to do for this stage is find and output this train connection, including all stops along the way and the arrivaldeparture times. Here is an example to show the desired behaviour of your program for a stage 1 test:
.myTrain
Enter the number of stations: 7
Burwood
Central
Chatswood
Hornsby
Parramatta
Redfern
Wynyard
Enter the number of trains: 2
Enter the number of stops: 5
0935
Parramatta
0950
Burwood
1005
Redfern
1012
Central
1017
Wynyard
Enter the number of stops: 2
1459
Chatswood
1530
Hornsby
From: Chatswood
To: Hornsby
Arrive by: 1700
1459 Chatswood
1530 Hornsby
From: Burwood
To: Central
Arrive by: 1015
0950 Burwood
1005 Redfern
1012 Central
From: done
Thank you for using myTrain.
Stage 2 5 marks
For stage 2, you should extend your program for stage 1 such that it always finds, and outputs, a connection between From and To that
arrives on, or before, the requested time ArriveBy; and
departs as late as possible.
You should assume that:
Changing trains takes no time: Passengers arriving at a station can get onto any other train that leaves that station at the same time or later.
In all test scenarios there will be at most one connection that satisfies all requirements.
If there is no connection, the output should be:
No connection found.
Here is an example to show the desired behaviour and output of your program for a stage 2 test:
.myTrain
Enter the number of stations: 5
Parramatta
Burwood
Ashfield
Central
Chatswood
Enter the number of trains: 2
Enter the number of stops: 4
0935
Parramatta
0945
Burwood
1002
Central
1030
Chatswood
Enter the number of stops: 3
0940
Parramatta
0950
Ashfield
1000
Central
From: Parramatta
To: Chatswood
Arrive by: 1030
0940 Parramatta
0950 Ashfield
1000 Central
Change at Central
1002 Central
1030 Chatswood
From: Parramatta
To: Central
Arrive by: 0959
No connection found.
From: done
Thank you for using myTrain.
Stage 3 2 marks
For stage 2, you should extend your program for stage 2 such that:
If there are two or more connections with the same latest departure time, choose the one with the earliest arrival time.
Here is an example to show the desired behaviour and output of your program for a stage 3 test:
.myTrain
Enter the number of stations: 3
Central
Parramatta
Chatswood
Enter the number of trains: 2
Enter the number of stops: 3
0935
Parramatta
1002
Central
1030
Chatswood
Enter the number of stops: 2
1010
Central
1025
Chatswood
From: Parramatta
To: Chatswood
Arrive by: 1030
0935 Parramatta
1002 Central
Change at Central
1010 Central
1025 Chatswood
From: done
Thank you for using myTrain.
Complexity Analysis 1 mark
Your program should include a time complexity analysis for the worstcase asymptotic running time of your program, in BigOh notation, depending on the size of the input:
1.the number of stations, n
2.the number of trains, m
3.the maximum number k of stops on a train line.
Hints
If you find any of the following ADTs from the lectures useful, then you can, and indeed are encouraged to, use them with your program:
linked list ADT :list.h, list.c
stack ADT :stack.h, stack.c
queue ADT :queue.h, queue.c
graph ADT :Graph.h, Graph.c
weighted graph ADT :WGraph.h, WGraph.c
You are free to modify any of the five ADTs for the purpose of the assignment but without changing the file names. If your program is using one or more of these ADTs, you should submit both the header and implementation file, even if you have not changed them.
Your main program file myTrain.c should start with a comment:that contains the time complexity of your program in BigOh notation, together with a short explanation.
Testing
We have created a script that can automatically test your program. To run this test you can execute the dryrun program that corresponds to this assignment. It expects to find, in the current directory, the program myTrain.c and any of the admissible ADTs Graph,WGraph,stack,queue,list that your program is using, even if you use them unchanged. You can use dryrun as follows:
9024 dryrun myTrain
Please note: Passing dryrun does not guarantee that your program is correct. You should thoroughly test your program with your own test cases.
Submit
For this project you will need to submit a file named myTrain.c and, optionally, any of the ADTs named Graph,WGraph,stack,queue,list that your program is using, even if you have not changed them. You can either submit through WebCMS3 or use a command line. For example, if your program uses the Graph ADT and the queue ADT, then you should submit:
give cs9024 assn myTrain.c Graph.h Graph.c queue.h queue.c
Do not forget to add the time complexity to your main source code file myTrain.c.
You can submit as many times as you likelater submissions will overwrite earlier ones. You can check that your submission has been received on WebCMS3 or by using the following command:
9024 classrun check assn
Marking
This project will be marked on functionality in the first instance, so it is very important that the output of your program be exactly correct as shown in the examples above. Submissions which score very low on the automarking will be looked at by a human and may receive a few marks, provided the code is wellstructured and commented.
Programs that generate compilation errors will receive a very low mark, no matter what other virtues they may have. In general, a program that attempts a substantial part of the job and does that part correctly will receive more marks than one attempting to do the entire job but with many errors.
Style considerations include:
Readability
Structured programming
Good commenting
Plagiarism
Group submissions will not be allowed. Your program must be entirely your own work. Plagiarism detection software will be used to compare all submissions pairwise including submissions for similar projects in previous years, if applicable and serious penalties will be applied, particularly in the case of repeat offences.
Do not copy ideas or code from others
Do not use a publicly accessible repository or allow anyone to see your code, not even after the deadline
Please refer to the online sources to help you understand what plagiarism is and how it is dealt with at UNSW:
Plagiarism and Academic Integrity
UNSW Plagiarism Policy Statement
UNSW Plagiarism Procedure
Help
See FAQ for some additional hints.
Finally
Have fun! Michael
Reviews
There are no reviews yet.