COMP9024 25T1

Assignment

Trip Planner

Data Structures and Algorithms

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

2 marks for stage 1 (correctness)

2 marks for stage 2 (correctness)

4 marks for stage 3 (correctness)

2 marks for stage 4 (correctness)

1 mark for complexity analysis

1 mark for style.

———————

Total: 12 marks

Due

16:59:59 on Tuesday 22 April (week 10)

Late

Reduction by 5% of maximum mark per day late, capped at 5 days (= 120 hours)

E.g. if you are 25 hours late, your mark will be reduced by 1.2 (= 10% of max mark)

Aim

You're in a new city and would like to plan a walking tour of some of its landmarks. Luckily we’ve seen a number of algorithms in class to help with path planning. Unluckily, the city isn't necessarily connected, at least not on foot. To help, there are ferries to help people get around.

Your objective is to write a program tripPlan.c that generates an optimal trip between landmarks, based on user preferences.

Input

Landmarks

The first input to your program consists of an integer l > 0, indicating the number of landmarks in the city, followed by l lines of the form.

Here is an example:

You may assume that:

The input is syntactically correct.

The maximum length (strlen()) of the name of a landmark is 31 and will not use any spaces.

Names are case sensitive.

No name will be input more than once.

Hint:

To read a single line with a landmark name you should use:

where name is a string, i.e. an array of chars.

Walking Links

The next input to your program is an integer w ≥ 0, indicating the number of walking links between landmarks, followed by w × 3 lines of the form.

where the third line denotes the time, in minutes, it takes to walk between the two landmarks. Note, this link may be walked in either direction, from landmark-1 to landmark-2, or from landmark-2 to landmark-1.

Here is an example:

You may assume that:

The input is syntactically correct.

Only landmarks that have been input earlier will be used.

The walking time will be a strictly positive integer.

Ferry Schedules

The next input to your program is an integer f ≥ 0, indicating the number of ferries on any day, followed by f × 4 lines of the form.

Here is an example:

You may assume that:

The input is syntactically correct.

Only landmarks that have been input earlier will be used.

All times are given as 4 digits in hhmm format (hh – hour, mm – minute), and are valid, ranging from 0000 to 2359.

The arrival time is strictly later than the time of departure.

All ferries reach their destination before midnight.

Trip Plan

The final input to your program are user queries:

You may assume that:

The input is syntactically correct.

Only landmarks that have been input earlier will be used.

Two different landmarks will be given.

No expected plan will roll over into the following day.

Your program should terminate when the user enters "done" when prompted with From:

Stage 1 (2 marks)

Stage 1 requires you to generate a suitable data structure from the input.

Test cases for this stage will only use queries FromLandmark, ToLandmark, DepartureTime such that:

there exists at most one direct connection between FromLandmark and ToLandmark;

should such a connection exist, this connection is the shortest path between FromLandmark and ToLandmark; and

should such a connection not exist, no other path between FromLandmark and ToLandmark will exist.

Here is an example to demonstrate the expected behaviour of your program for a stage 1 test:

If there is no connection that satisfies the requirements, then the output should be: No route.

Stage 2 (2 marks)

Stage 2 requires you to implement a basic path finding algorithm.

Test cases for this stage will only use queries FromLandmark, ToLandmark, DepartureTime such that:

there exists one, and only one, simple path that connects FromLandmark and ToLandmark;

this path does not involve any ferries; and

the DepartureTime is 0000.

Here is an example to demonstrate the expected behaviour of your program for a stage 2 test:

prompt$ ./tripPlan

Stage 3 (4 marks)

For the next stage, your program should find and output a simple path from FromLandmark to ToLandmark that:

may involve one or more ferries; and

the DepartureTime won't necessarily be 0000.

Note that to board a ferry, it is necessary to arrive at the departing landmark no later than the time the ferry departs.

In all test scenarios for this stage there will be at most one simple path that satisfies all requirements.

Here is an example to demonstrate the expected behaviour of your program for stage 3:

Stage 4 (2 marks)

For the final stage, if there are multiple possible routes, your program should take into account the additional user preference that:

of all possible routes, choose the one with the shortest overall travel time.

You may assume that there will never be more than one route with the shortest overall travel time. Note also that travel time includes any time that may be spent waiting for a ferry.

Here is an example to demonstrate the expected behaviour of your program for stage 4:

Complexity Analysis (1 mark)

You should include a time complexity analysis for the asymptotic worst-case running time of your program, in Big-Oh notation, depending on the size of the input:

1. the number of landmarks, l

2. the number of walking links, w

3. the number of ferry schedules, f.

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

priority queue ADT : PQueue.h, PQueue.c

weighted graph ADT : WGraph.h, WGraph.c

You are free to modify any of the six 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 must submit both the header and implementation file, even if you have not changed them.

Your main program file tripPlan.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 tripPlan.c and any of the admissible ADTs (Graph, WGraph, Stack, Queue, PQueue, List) that your program is using, even if you use them unchanged. You can use dryrun as follows:

Please note: Passing dryrun does not guarantee that your program is correct. You should thoroughly test your program with your own test cases.

Submission

For this assignment you will need to submit a file named tripPlan.c and, optionally, any of the ADTs named Graph, WGraph, Stack, Queue, PQueue, List that your program is using, even if you have not changed them. You can either submit through WebCMS3 or use the command line. For example, if your program uses the Graph ADT and the Queue ADT, then you should submit:

Do not forget to add the time complexity to your main source code file tripPlan.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:

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

Collection

Once marking is complete you can collect your marked submission using the following command:

You can also view your marks using the following command:

You can also collect your marked submission directly through WebCMS3 from the "Collect Submission" tab at the top of this page.