COMP9024 25T0 Prof Michael Thielscher Large Assignment Number Trails 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 24 January 2025 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) 3 marks for stage 2 (correctness) 2 marks for stage 3 (correctness) 3 marks for stage 4 (correctness) 1 mark for complexity analysis 1 mark for style ——————— Total: 12 marks Due 4:00:00pm on Friday 7 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 A number trail is a series of k ≥ 1 numbers: χ1 → χ2 → χ3 → … → χk-1 → χk in which numbers are in ascending order, and two consecutive numbers χi and χi+1 differ by only one digit: 1. either they are of the same length and are identical except in one position, e.g.

9024 → 9324 2. or one digit is added, e.g.

1234 → 12345

or

314 → 3014. An example is the following number trail of length k = 8: 123 → 1234 → 1434 → 1444 → 10444 → 16444 → 76444 → 76544 Your task is to develop a program to compute the longest number trails that can be built from a collection of numbers. 2025/1/31 15:59 COMP9024 25T0 - Large Assignment https://cgi.cse.unsw.edu.au/~cs9024/assn/index.php 1/6 Input Your program should start by prompting the user to input a positive number n, then prompt for n numbers. Hint: You may assume that the input is syntactically correct (a positive number n ≥1 followed by n positive numbers); no number is larger than INT_MAX on a CSE computer (= 2147483647, defined in the standard library limits.h ); there will be no more than 100 numbers (i.e., n ≤ 100). You can also assume that the number are input in ascending order (so you don't have to sort them yourself). Output Task 1: For each number χ, compute and output all the numbers that could be used as the next number after χ in a trail. Task 2: Compute and output a. the length of the longest trail that can be built from the numbers in the input, b. all number trails of maximum length that can be built from the set of numbers in the input. Stage 1 (2 marks) For stage 1, you need to demonstrate that you can build the underlying graph under the assumption that all numbers from the input have the same number of digits. Any test for this stage will have only numbers of the same length and will be such that they all together form a trail. Hence, this stage focuses on Task 1, and for Task 2 you can just output n (= maximum length of a trail) and a trail containing all the numbers (= the only longest trail). Here is an example to show the desired behaviour of your program for a stage 1 test: prompt$ ./trails Enter a number: 6 Enter a number: 9020 Enter a number: 9021 Enter a number: 9024 Enter a number: 9324 Enter a number: 9334 Enter a number: 9344 9020: 9021 9024 9021: 9024 9024: 9324 9324: 9334 9344 9334: 9344 9344: Maximum trail length: 6 2025/1/31 15:59 COMP9024 25T0 - Large Assignment https://cgi.cse.unsw.edu.au/~cs9024/assn/index.php 2/6 Longest trail(s): 9020 -> 9021 -> 9024 -> 9324 -> 9334 -> 9344 Stage 2 (3 marks) For stage 2, you should demonstrate that you can find one maximal trail under the assumption that all numbers have the same number of digits. Any test for this stage will be such that all numbers are of equal length and there is only one longest number trail. Here is an example to show the desired behaviour of your program for a stage 2 test: prompt$ ./trails Enter a number: 8 Enter a number: 214 Enter a number: 217 Enter a number: 414 Enter a number: 417 Enter a number: 514 Enter a number: 518 Enter a number: 614 Enter a number: 918 214: 217 414 514 614 217: 417 414: 417 514 614 417: 514: 518 614 518: 918 614: 918: Maximum trail length: 5 Longest trail(s): 214 -> 414 -> 514 -> 518 -> 918 Stage 3 (2 marks) For stage 3, you should extend your program for stage 2 such that numbers can be of different magnitude, that is, with different numbers of digits. Tests for this stage are also guaranteed to have just one number trail of maximum length. Here is an example to show the desired behaviour of your program for a stage 3 test: prompt$ ./trails Enter a number: 6 Enter a number: 314 Enter a number: 3104 Enter a number: 3154 Enter a number: 5314 Enter a number: 5324 Enter a number: 53024 314: 3104 3154 5314 3104: 3154 3154: 2025/1/31 15:59 COMP9024 25T0 - Large Assignment https://cgi.cse.unsw.edu.au/~cs9024/assn/index.php 3/6 5314: 5324 5324: 53024 53024: Maximum trail length: 4 Longest trail(s): 314 -> 5314 -> 5324 -> 53024 Stage 4 (3 marks) For stage 4, you should extend your stage 3 program such that it outputs all number trails of maximal length in ascending order, that is, starting with the trail whose first number is the smallest of all trails. For trails that start with the same number, the trail whose second number is the smallest should come first, etc. Here is an example to show the desired behaviour of your program for a stage 4 test: prompt$ ./trails Enter a number: 5 Enter a number: 314 Enter a number: 3104 Enter a number: 3154 Enter a number: 5314 Enter a number: 5324 314: 3104 3154 5314 3104: 3154 3154: 5314: 5324 5324: Maximum trail length: 3 Longest trail(s): 314 -> 3104 -> 3154 314 -> 5314 -> 5324 Note: It is a requirement that the trails are output in ascending order. 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. your implementation for Task 1, depending on the number n of numbers; 2. your implementation for Task 2, depending on the number n of numbers. Your main program file trails.c should start with a comment: /* … */ that contains the time complexity of your program in Big-Oh notation, together with a short explanation. Hints 2025/1/31 15:59 COMP9024 25T0 - Large Assignment https://cgi.cse.unsw.edu.au/~cs9024/assn/index.php 4/6 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 graph ADT :

Graph.h, Graph.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 should submit both the header and implementation file, even if you have not changed them. Your main program file trails.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 trails.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: prompt$ 9024 dryrun trails 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 trails.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 trails.c Graph.h Graph.c Queue.h Queue.c Do not forget to add the time complexity to your main source code file trails.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 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 multiple compilation or runtime errors. 2025/1/31 15:59 COMP9024 25T0 - Large Assignment https://cgi.cse.unsw.edu.au/~cs9024/assn/index.php 5/6 Style considerations include: Readability Structured programming Good commenting Plagiarism Group submissions will not be allowed. Your programs 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, GitHub Copilot, Gemini 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, Gemini 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: Academic Integrity and Plagiarism UNSW Plagiarism Policy 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. 2025/1/31 15:59 COMP9024 25T0 - Large Assignment https://cgi.cse.unsw.edu.au/~cs9024/assn/index.php 6/6 51作业君版权所有