首页 > > 详细

Sydney Transport Planner

 Assignment

Sydney Transport Planner
Change Log
We may make minor changes to the spec to address/clarify some outstanding 
issues. These may require minimal changes in your design/code, if at all. Students 
are strongly encouraged to check the change log regularly.
4 November
 Clarified that station names will have no spaces and that train schedules will 
list stops in the right order.
Version 1: Released on 30 October 2019
Objectives
The assignment aims to give you more independent, self-directed 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 and will not use any 
spaces.
 No station name will be input more than once.
Hint:
To read a single line with a station name you may use:
scanf("%s", station); // station is a character array (= string 
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, k≥2, 
followed by k*2 lines of the form:
hhmm
station-name
meaning that passengers can get on or off the train at that time (hh – hour, mm –
minute) 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.
 Stops are input in the right (temporal) order.
 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 arrival/departure 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 worst-case 
asymptotic running time of your program, in Big-Oh 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 Big-Oh 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 like — later 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 well-structured 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 on-line 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
联系我们 - QQ: 99515681 微信:codinghelp
程序辅导网!