COMP9024 Data Structures and Algorithms

COMP9024 24T0

Assignment

Warehouses

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.

Version 1: Released on 19 January 2024

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)

4 marks for stage 2 (correctness)

3 marks for stage 3 (correctness)

1 mark for complexity analysis

1 mark for style

Total: 12 marks

Due 12:00:00noon on Friday 2 February (week 5)

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

Your task is to write a program warehouses.c to help a company find the minimum number of warehouses so that all its retail stores are within a maximum distance from a warehouse.

Input

Store locations

Your program should start by prompting the user for a positive integer followed by n lines, each containing the name of a location. An example is:

prompt$ ./warehouses

Enter the number of locations: 3

Adelaide

Brisbane

Canberra

You may assume that:

· The input is syntactically correct.

 Names require no more than 31 characters and will not use any spaces.

 The locations will be input in alphabetical order, with no name repeated.

HintTo read a single line with a location you may use:

scanf("%31s", loc);   // loc is a character array (= string variable)

Roads

Next, your program should ask for the number of roads, m, then prompt the user to input m roads, each requiring the name of two locations and the distance (in km). An example is:

Enter the number of roads: 2

Enter a location (from): Canberra

Enter a location (to): Brisbane

Enter the distance: 1175

Enter a location (from): Adelaide

Enter a location (to): Canberra

Enter the distance: 1160

Note that all roads with distances are directional, that is, from one location to another location. You may assume that:

 The input is syntactically correct: Each road will use two different locations that have been input earlier, followed by a positive number.

 There will be no two roads that have the same start and end point.

Maximum distance

Finally, your program should ask the user for the required maximum distance to a warehouse:

Enter the maximum distance: 1200

Again, you may assume that the input is correct (a non-negative integer).

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 are guaranteed to satisfy the following conditions:

 There is only one route that:

 starts in the (alphabetically) first location,

 travels through all other locations (not necessarily in alphabetical order).

Which means that in each scenario, if n is the number of cities, then there will be exactly n - 1 roads.

 The unique optimal solution is to have one warehouse only, which has to be in the first location.

All you need to do for this stage, therefore, is to

1. print  Warehouses: followed by the name of the alphabetically first location

2. print  Routes: then find and output, for each other location in alphabetical order, the unique route from the first city, along with the distance.

An example showing the desired behaviour of your program for a stage 1 test is:

prompt$ ./warehouses

Enter the number of locations: 3

Adelaide

Brisbane

Canberra

Enter the number of roads: 2

Enter a location (from): Canberra

Enter a location (to): Brisbane

Enter the distance: 1175

Enter a location (from): Adelaide

Enter a location (to): Canberra

Enter the distance: 1160

Enter the maximum distance: 2400

Warehouses: Adelaide

Routes:

Brisbane: Adelaide - Canberra - Brisbane 2335

Canberra: Adelaide - Canberra 1160

prompt$

Stage 2 (4 marks)

For stage 2, you should extend your stage 1 program to find an optimal solution, that is, a smallest

collection of warehouse locations so that each other location is within the maximum required distance from one of the locations.

For this stage, all test cases will satisfy the following condition:

 The solution is unique, that is, there is always only one smallest set of warehouse locations that satisfies the requirements.

Therefore, for this stage you need to:

1. print  Warehouses: then find and output an optimal set of locations for warehouses

2. print  Routes: then output, for each other location in alphabetical order, the best way to reach it from the closest warehouse.

Here is an example to show the desired behaviour and output of your program for a stage 2 test:

prompt$ ./warehouses

Enter the number of locations: 3

Adelaide

Brisbane

Canberra

Enter the number of roads: 2

Enter a location (from): Canberra

Enter a location (to): Brisbane

Enter the distance: 1175

Enter a location (from): Adelaide

Enter a location (to): Canberra

Enter the distance: 1160

Enter the maximum distance: 1200

Warehouses: Adelaide, Brisbane

Routes:

Canberra: Adelaide - Canberra 1160

prompt$

Stage 3 (3 marks)

For stage 3, you should extend your program for stage 2 such that:

If there is more than one solution with the same smallest number of warehouses, you should find and output the solution with the shortest overall travel distance between all locations

and the nearest warehouse.

An example showing the desired behaviour and output of your program for a stage 3 test is:

prompt$ ./warehouses

Enter the number of locations: 3

Adelaide

Brisbane

Canberra

Enter the number of roads: 3

Enter a location (from): Canberra

Enter a location (to): Brisbane

Enter the distance: 1175

Enter a location (from): Adelaide

Enter a location (to): Canberra

Enter the distance: 1160

Enter a location (from): Brisbane

Enter a location (to): Adelaide

Enter the distance: 2032

Enter the maximum distance: 3600

Warehouses: Adelaide

Routes:

Brisbane: Adelaide - Canberra - Brisbane 2335

Canberra: Adelaide - Canberra 1160

prompt$

Note that the total travel distance in this solution is 1160 + 2335 = 3495, which is shorter than the total travel distance if the (only) warehouse was in Canberra ( 1175 + ( 1175 + 2032) = 4382) or in Brisbane  (2032 + (2032 + 1160) = 5224).

Hint: You only need to output one shortest route for each non-warehouse location. There will be no test cases in which a location is at equal distance from two warehouses, or where there are two different shortest routes from a warehouse to another location.

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 number of locations, n.

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 listADT : List.hList.c

 stack ADT : Stack.hStack.c

 queue ADT : Queue.hQueue.c

 priority queue ADT : QPueue.hPQueue.c

 graph ADT : Graph.hGraph.c

 weighted graph ADT : WGraph.hWGraph.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 should submit both the header and implementation file, even if you have not changed them.

Your main program file warehouses.c should start with a comment: /* … */ that contains the time complexity of your program in Big-Oh notation, along with a short explanation.

Testing

We have created a script that can automatically test your program. To run this test you can execute the dry run program that corresponds to this assignment. It expects to find, in the current directory, the program warehouses.c and any of the admissible ADTs

(Graph,WGraph,Stack,Queue,PQueue,Listthat your program is usingeven if you use them unchanged. You can use dryrun as follows:

prompt$ 9024 dry run warehouses

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 warehouses.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 a command line. For example, if your program uses the Graph ADT and the Queue ADT, then you should submit:

prompt$ give cs9024 assn warehouses .c Graph .h Graph .c Queue .h Queue .c

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

prompt$ 9024 class run -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 multiple compilation or runtime   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 assessments in previous years, if applicable) and serious penalties will be applied, including an entry on UNSW's plagiarism register.

You are also not allowed to submit code obtained with the help of ChatGPT, Git Hub Copilot, Goole Bard or similar automatic tools.

· Do not copy ideas or code from others

· Do not use a publicly accessible repository or allow anyone to see your code

· Code generated by ChatGPT, GitHub Copilot, Google Bard and similar tools will be treated as plagiarism.

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

Reproducing, publishing, posting, distributing or translating this assignment is an infringement of copyright and will be referred to UNSW Conduct and Integrity for action.


发表评论

电子邮件地址不会被公开。 必填项已用*标注