Supplementary Exam
Tu e s d a y 2 4 t h M a y 2 0 2 2
Changelog
All changes to the exam paper and files will be listed here.
Exam Rules and Conditions
Please read these rules carefully. Note that deliberate violation of exam conditions will be referred to Student
Integrity as serious misconduct.
Duration
You can star t reading the exam at 2pm Tuesday 24 May 2022 (Sydney time).
You can star t typing at 2pm Tuesday 24 May 2022 (Sydney time).
You have until 5pm Tuesday 24 May 2022 (Sydney time) to complete this exam.
Only submissions before 5pm Tuesday 24 May 2022 (Sydney time) will be marked.
* Students with extra exam time approved by Equitable Learning Services (ELS) can make submissions after 5pm
Tuesday 24 May 2022 (Sydney time) within their approved extra time.
Communication
You are not per mitted to communicate (email, phone, message, talk, social networks, etc.) with anyone during this
exam except COMP2521 staff.
If you have any questions during the exam, make a private post on the Ed forum (the same one we've been using all
term)
Even after you finish the exam, on the day of the exam, do not communicate your exam answers to anyone. Some
students have extended time to complete the exam.
Resources
Yo u a r e not permitted to access any resources on the Internet, except for the following:
this exam paper
the course material available on the course webpage
You are not per mitted to access any other papers, books or computer files, except for the following: this exam, your
tut/lab solutions and assignment work for this course.
You are not per mitted to use code-synthesis tools such as GitHub Copilot and other similar tools.
Importantly, please make sure that you submit your original work and don't copy! We will use sophisticated
plagiarism software/techniques to detect any possible breaches.
Privacy
Do not place your exam work in any location, including file sharing services such as Dropbox or GitHub, accessible to
any other person.
Ensure during the exam no other person in your household can access your work.
Your zpass should not be disclosed to any other person. If you have disclosed your zpass, you should change it
immediately.
Special Consideration
By completing the acknowledgement and starting this exam you have acknowledged that you are fit to sit the
exam and cannot apply for Special Consideration for issues that existed prior to the exam.
If a circumstance arises during the exam that prevents you from completing the exam, please email
[email protected] immediately and apply for special consideration within 3 days of the exam, preferably as
soon as possible.
Before your final exam, you should read the section "Important Information for Online Assessments" on the Special
Consideration webpage. It contains information on what you should do if you experience a technical issue that is
beyond your control and impacts your ability to complete an assessment - in particular, how and what to document
for a special consideration application.
Submission
All submissions must be done via give.
See the submission instructions under each question.
You can submit multiple times. Only your last submission will be marked.
Do not wait until just before the deadline to submit all your answers. Submit each question as soon as you
finish working on it or submit incrementally throughout the exam.
There will be a 5 minute buffer after the deadline (5pm) to allow students to resolve last-minute submission issues.
Do not use this buffer as an excuse to continue working on the exam until 5:05pm. You must attempt all
submissions before 5pm. Submissions will be disabled after 5:05pm (except for ELS students), and requests
for leniency with respect to this deadline will be ignored. You have been warned.
To c h e c k yo u r s u b m i s s i o n s t a t u s fo r a p a r t i c u l a r q u e s t i o n , u s e t h e c o m m a n d 2521 classrun check question,
where question is the name of a particular submission. For example:
$ 2521 classrun check supp_q1
Short-Answer Questions
Justifications/explanations are only required when asked by the question.
Programming Questions
General Assumptions and Constraints
All inputs will be valid.
No error checking is necessary.
You may add your own #defines and define your own structs/enums.
You may define your own helper func tions in the files to be submitted.
You may use any func tions provided by the #included libraries.
You must not #include any additional libraries.
You must not use global variables or static variables. Solutions that do so will receive zero marks.
You must not star t any new programs or communicate with exter nal programs. Solutions that do so will be heavily
penalised.
Marking
Yo u s h o u l d e n s u r e t h a t yo u r c o d e wo r ks o n C S E m a c h i n e s .
Solutions which do not attempt to solve the question generally but instead only hardcode return values for specific
tests will receive zero marks.
Code style is not marked (except that global variables and static variables are strictly forbidden). However, good
style may help a marker understand your code better, which will give you a greater chance of being awarded partial
marks if your code does not work.
Memory leaks/errors will not be penalised. However, we advise that you ensure there are no memory errors in your
code, as programs containing memory errors are not guaranteed to behave correctly or consistently. A program that
works when you test it during the exam but contains memory errors may not work during autotesting. There will be
no chances to fix memory errors after the exam.
Admin
MarksContributes 50% towards your final mark
SubmitSee the submission instructions for each question
Date and time2pm to 5pm Tuesday 24 May 2022 (Sydney time)
To t a l M a r ks100
To t a l n u m b e r o f q u e s t i o n s11 (not worth equal marks)
Structure
This exam consists of two parts:
Written short-answer questions (50 marks)
Programming questions (50 marks)
Setting Up
Change into the directory you created for the exam and run the following command:
$ unzip /web/cs2521/22T1/exams/supp/downloads/files.zip
If you're working at home, download files.zip by clicking on the above link and then unzip the downloaded file.
Question 1 (12 marks)
Write your answers for this question in q1.txt.
(a) (4 marks)
An algorithm for solving a problem runs in exponential time . Suppose that your computer, running an
implementation of this algorithm, can process an input of size 1000 in one day. What is the maximum input size that can
be processed in three days by a computer that is 10,000 times faster if it uses the same implementation? Justify your
answer.
(b) (4 marks)
A business that has 100,000 customers needs to sort their customer names in ascending order based on their
surnames. Assuming that surnames are at most 15 characters long, which one of the following sorting algorithms would
be most efficient for this task? Justify your answer.
Radix sort
Quicksort
Mergesort
Bubble sort
(c) (4 marks)
What are the time complexities (in big O notation) of the following two functions, fnA() and fnB(), in terms of a and
b? Justify your answer.
// Assumption: 0 <= a <= b < size of arr
int fnA(int arr[], int a, int b) {
if (a == b) {
return a;
}
int i = fnA(arr, (a + b + 1) / 2, b);
return (arr[a] < arr[i]) ? a : i;
}
// Assumption: 0 <= a, b < size of arr
void fnB(int arr[], int a, int b) {
if (a >= b) {
return;
}
int i = fnA(arr, a, b);
int temp = arr[a];
arr[a] = arr[i];
arr[i] = temp;
fnB(arr, a + 1, b - 1);
}
Submission
Submit via the give command
$ give cs2521 supp_q1 q1.txt
Question 2 (3 marks)
Write your answers for this question in q2.txt.
Consider the following simple program in prog.c, which uses a stack ADT:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include
#include "Stack.h"
int main(void) {
Stack s = StackNew();
int ch = getchar();
while (ch != EOF) {
StackPush(s, ch);
ch = getchar();
}
while (s->size > 0) {
putchar(StackPop(s));
}
StackFree(s);
}
The program is compiled as follows:
gcc -Wall -Werror -o prog prog.c Stack.c
However, this error is encountered:
prog.c: In function 'main':
prog.c:14:13: error: dereferencing pointer to incomplete type 'struct stack'
while (s->size > 0) {
In your own words, explain why this compilation error occurred and briefly describe how it can be fixed. Note: You are
not required to provide code - only a brief description.
Submission
Submit via the give command
$ give cs2521 supp_q2 q2.txt
Question 3 (10 marks)
Write your answers for this question in q3.txt.
(a) (3 marks)
A post-order traversal of a binary search tree produces the sequence: 2, 6, 4, 8, 10, 7, 16, 21, 35, 19, 13. Identify the
following values and briefly explain how you derived your answers:
i. The value in the root node
ii. The value in the left child of the root node
iii. The value in the right child of the root node
(b) (3 marks)
Consider the following binary search tree and a pointer t which initially points to the node containing the value 20:
Now suppose that the following insert-at-root operation is applied to this tree, as discussed in the lectures:
t = insertAtRoot(t, 22);
Now answer the following questions (no explanations required):
i. How many rotations were required in the above operation?
ii. In the resulting tree, what value will be in the left child of 22?
iii. In the resulting tree, what value will be in the right child of 22?
(c) (4 marks)
Consider the following 2-3-4 tree:
Insert the following values into the above tree in the given order:
60, 71, 62
Answer the following:
i. In the resulting tree, what value(s) would be stored in the root node?
ii. In the resulting tree, what value(s) would be stored in the node that now contains 62?
iii. In the resulting tree, what value(s) would be stored in the node that now contains 71?
iv. In the resulting tree, what value(s) would be stored in the node that now contains 99?
Note: if you need to promote a value, you must promote the smaller of the two middle values.
Submission
Submit via the give command
$ give cs2521 supp_q3 q3.txt
Question 4 (4 marks)
Write your answers for this question in q4.txt.
(a) (2 marks)
Consider the following directed graph:
Run breadth-first search on the graph starting at vertex 5, and give the order in which the vertices are visited. If a vertex
has multiple neighbours, consider them in ascending order. Note: No working is required - just give the order of the
vertices.
(b) (2 marks)
Consider the following weighted graph:
Run Prim's algorithm on the graph starting at vertex A, and give the order in which edges are added to the minimum
spanning tree. Note: No working is required - just give the order of the edges.
Submission
Submit via the give command
$ give cs2521 supp_q4 q4.txt
Question 5 (6 marks)
Write your answers for this question in q5.txt.
Consider the following array:
{ 6, 2, 19, 7, 11, 14, 20, 22, 13, 9, 15 }
(a) (1 marks)
Suppose the array above is to be sorted using quicksort. Which item would be chosen as the first pivot if median-of-
three pivot selection is used? Give the value of the pivot, not its index.
(b) (2 marks)
Suppose the array above is sorted using bubble sort, implemented using bubble-down/downward scans (in the same
way as in the lecture slides). What would the array look like after the first three scans?
(c) (3 marks)
Suppose the array above is sorted using bottom-up mergesort. Show what the array would look like after each pass of
the algorithm.
Submission
Submit via the give command
$ give cs2521 supp_q5 q5.txt
Question 6 (5 marks)
Write your answers for this question in q6.txt.
Suppose that you need to implement a Priority Queue ADT that provides the following operations:
Push: Adds a new key-element pair
Pop: Remove a key-element pair with highest priority
PrintInOrder: Prints all the key-element pairs in decreasing order of priority
Assuming that all three operations will be frequently used, which one of the following data structures is most suitable?
Justify your answer. You must use time complexities as a basis for your justification.
Ordered Linked List
Ordered Array
AVL Tree
Hash Table
Heap
Submission
Submit via the give command
$ give cs2521 supp_q6 q6.txt
Question 7 (7 marks)
Write your answers for this question in q7.txt.
Consider the following hash table that has 9 slots, and uses double hashing with primary hash function
and secondary hash function :
(a) (3 marks)
Show the state of the hash table after inserting the following keys into the above table:
22, 7, 20
(b) (2 marks)
Using the table that you obtained in part (a), how many items would be examined in searching for the key 16? Justify
your answer.
(c) (2 marks)
The combination of the following factors: (1) the size of the hash table being 9, and (2) the secondary hash function
being is problematic for the proper functioning of the hash table. Explain what the problem is.
Submission
Submit via the give command
$ give cs2521 supp_q7 q7.txt
Question 8 (3 marks)
Write your answers for this question in q8.txt.
A common feature in modern smartphones is autocompletion, which suggests words based on the part of the word
that the user has already entered. For example, if the user enters "th", then autocompletion may suggest the words
"the", "this" and "that".
Describe how you could use a trie to implement basic autocompletion. Note: You are not required to provide code -
only a description.
Submission
Submit via the give command
$ give cs2521 supp_q8 q8.txt
Question 9 (15 marks)
Your task is to implement the following func tion in the file q9/mergeOrdered.c:
List mergeOrdered(List l1, List l2);
The function takes two ordered lists, each of which is in increasing order. It merges the two ordered lists together into a
new list that is also in increasing order and returns the new list.
Note that the mergeOrdered function always produces a new list; both of the original lists must remain unchanged.
You must also clearly state the worst case time complexity (in big O notation) of your solution in a comment just above
the function. The time complexity should be in terms of and , where and are the lengths of l1 and l2
respectively.
Assumptions and Constraints
All general assumptions and constraints at the top of this exam paper apply.
The given lists may contain duplicate values. Duplicate values may be added to the merged list in any order.
The given lists will be in increasing order.
x and y
The given lists must not be modified.
You must not use arrays. Failure to comply with this will result in a mark of zero for this question.
Files
MakefileA Makefile to compile your code
list.cContains the implementation of basic linked list functions
list.hContains the definition of the linked list data structure and function prototypes
testMergeOrdered.c
A testing program. The program reads two lists from stdin, calls mergeOrdered, and
outputs the result to stdout.
mergeOrdered.c
Contains mergeOrdered, the function you must implement. This is the only file you
should modify.
tests/A directory containing the inputs and expected outputs for some basic test cases
Examples
$ ./testMergeOrdered < tests/input1.txt
list1: 1, 4, 6
list2: 2, 8, 10, 15
merged list: 1, 2, 4, 6, 8, 10, 15
$ ./testMergeOrdered < tests/input2.txt
list1: 1, 4, 6
list2: 2, 4, 4, 8, 10, 20
merged list: 1, 2, 4, 4, 4, 6, 8, 10, 20
$ ./testMergeOrdered < tests/input3.txt
list1:
list2: 7, 9, 14, 55, 82
merged list: 7, 9, 14, 55, 82
Te s t i n g
You can compile and test your func tion using the following commands:
$ make # compiles the program
$ ./testMergeOrdered # tests with manual input, outputs to terminal
$ ./testMergeOrdered < input-file # tests with input from a file, outputs to terminal
$ ./testMergeOrdered < tests/input1.txt # for example, tests with input from tests/input1.txt
# (then manually compare with tests/output1.txt)
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note
that you will need to check the output yourself.
Submission
Submit via the give command
$ give cs2521 supp_q9 mergeOrdered.c
Make sure you are in the q9 directory before using this command.
Question 10 (15 marks)
Your task is to implement the following func tion in the file q10/nodesNotBalanced.c:
int nodesNotBalanced(BSTree t);
The function takes one argument: a binary search tree t, and returns the number of nodes in the tree that are not
height-balanced.
A node is considered to be height-balanced if the absolute difference in height between its left subtree and its right
subtree is greater than 1. The height of an empty tree is -1.
Assumptions and Constraints
All general assumptions and constraints at the top of this exam paper apply.
You must not modify the given tree.
You must not use arrays or any variant of malloc (malloc, calloc or realloc), either directly or indirectly.
Failure to comply with this will result in a mark of zero for this question.
The time complexity of your solution must be , where represents the number of nodes in the tree. If your
solution is slower than , the maximum mark you can attain for this question will be 9 (out of 15).
Files
MakefileA Makefile to compile your code
BSTree.cContains the implementation of basic binary search tree functions.
BSTree.hContains the definition of the binary search tree data structure and function prototypes.
testNodesNotBalanced.c
A testing program. The program reads tree data from stdin, calls
nodesNotBalanced, and outputs the result to stdout.
nodesNotBalanced.c
Contains nodesNotBalanced, the function you must implement. This is the only file
you should modify.
tests/A directory containing the inputs and expected outputs for some basic test cases
Examples
$ ./testNodesNotBalanced < tests/input1.txt
Tree:
50
\
60
nodesNotBalanced returned: 0
$ ./testNodesNotBalanced < tests/input2.txt
Tree:
30
\
60
/
50
nodesNotBalanced returned: 1
Explanation: The node containing 30 is not height-balanced, as the height of its left subtree is -1 and the height of its
right subtree is 1.
$ ./testNodesNotBalanced < tests/input3.txt
Tree:
50
/ \
/ \
30 70
/ \ \
/ \ 80
20 44 \
90
\
92
\
94
\
96
nodesNotBalanced returned: 5
Explanation: The nodes containing 50, 70, 80, 90 and 92 are not height-balanced, thus the number of nodes that are
not height-balanced is 5.
Te s t i n g
You can compile and test your func tion using the following commands:
$ make # compiles the program
$ ./testNodesNotBalanced # tests with manual input, outputs to terminal
$ ./testNodesNotBalanced < input-file # tests with input from a file, outputs to terminal
$ ./testNodesNotBalanced < tests/input1.txt # for example, tests with input from tests/input1.txt
# (then manually compare with tests/output1.txt)
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note
that you will need to check the output yourself.
Submission
Submit via the give command
O(10
n
)
h(k)=k % 9
h2(k)=k % 3+1
h2(k)=k % 3+1
nmnm
≥0≥0
O(n)n
O(n)
COMP2521 22T1
Submit via the give command
$ give cs2521 supp_q10 nodesNotBalanced.c
Make sure you are in the q10 directory before using this command.
Question 11 (20 marks)
Your task is to implement the following func tion in the file q11/calculateViralTransmission.c:
void calculateViralTransmission(Graph g, int src, int srcViralLoad, double *transmissionArray);
The function takes four arguments: an undirected graph g, a source node src, the viral load at the source node
srcViralLoad (where 0 ≤ srcViralLoad ≤ 100) and an array transmissionArray. For each node i that is
reachable from src (and only these nodes), the function calculates the viral load transmitted to node i (see definition
below) and stores it in transmissionArray[i]. For example, transmissionArray[2] should contain the viral
load transmitted to node 2 if node 2 is reachable from src. If node i is not reachable from src, the function should not
modify transmissionArray[i].
Viral Transmission
The viral load transmitted to a node v is given by the following formula:
transmissionArray[v] = srcViralLoad
where is length of the shortest path from src to v.
If the viral load transmitted to node v is < 10, transmissionArray[v] should be set to zero instead.
Please see the example below for more clarifications.
You must also clearly state the worst case time complexity (in big O notation) of your solution in a comment just above
the function. The time complexity should be in terms of , the number of vertices in the graph.
Important: We will consider how efficiently you have implemented your solution when we award you marks. Inefficient
solutions will receive a slight penalty.
Assumptions and Constraints
All general assumptions and constraints at the top of this exam paper apply.
The size of the transmissionArray array is equal to the number of nodes in the graph.
All values in the transmissionArray array are initially -1.
Files
MakefileA Makefile to compile your code
Graph.cContains the implementation of the Graph ADT
Graph.hContains the interface to the Graph ADT
Queue.cContains the implementation of the Queue ADT
Queue.hContains the interface to the Queue ADT
testCalculateViralTransmission.c
A testing program. The program reads graph data and the values of src and
srcViralLoad from stdin, calls calculateViralTransmission, and
outputs the result to stdout.
calculateViralTransmission.c
Contains calculateViralTransmission, the function you must
implement. This is the only file you should modify.
tests/
A directory containing the inputs and expected outputs for some basic test
cases
Example
Consider the following graph:
Suppose that src = 0 and srcViralLoad = 70. Then the viral load transmitted to each node is:
transmissionArray[0] = srcViralLoad * (0.6 ^ 0) = 70.00, because 0 is the source node.
transmissionArray[1] = srcViralLoad * (0.6 ^ 2) = 25.20, because the length of the shortest path from 0 to 1 is 2.
transmissionArray[2] = srcViralLoad * (0.6 ^ 1) = 42.00, because the length of the shortest path from 0 to 2 is 1.
transmissionArray[3] = srcViralLoad * (0.6 ^ 1) = 42.00, because the length of the shortest path from 0 to 3 is 1.
transmissionArray[4] = srcViralLoad * (0.6 ^ 2) = 25.20, because the length of the shortest path from 0 to 4 is 2.
transmissionArray[5] = srcViralLoad * (0.6 ^ 2) = 25.20, because the length of the shortest path from 0 to 5 is 2.
transmissionArray[6] is unchanged (-1), because node 6 is not reachable from src node 0.
transmissionArray[7] = 0, because the length of the shortest path from 0 to 7 is 4, and srcViralLoad * (0.6 ^ 4) =
9.072, which is less than 10.
transmissionArray[8] = srcViralLoad * (0.6 ^ 3) = 15.12, because the length of the shortest path from 0 to 8 is 3.
Te s t i n g
You can compile and test your func tion using the following commands:
$ make # compiles the program
$ ./testCalculateViralTransmission # tests with manual input, outputs to
terminal
$ ./testCalculateViralTransmission < input-file # tests with input from a file, outputs to
terminal
$ ./testCalculateViralTransmission < tests/input1.txt # for example, tests with input from
tests/input1.txt
# (then manually compare with
tests/output1.txt)
It is possible to devise your own tests by creating your own input files. See the existing input files for examples. Note
that you will need to check the output yourself.
Submission
Submit via the give command
$ give cs2521 supp_q11 calculateViralTransmission.c
Make sure you are in the q11 directory before using this command.
This is the end of the exam.
COMP2521 22T1: Data Structures and Algorithms is brought to you by
the School of Computer Science and Engineering
at the University of New South Wales, Sydney.
For all enquiries, please email the class account at [email protected]
CRICOS Provider 00098G
× 0.6
m
m
n
