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