COMP9024 Supplementary Exam (22T0)

The Supplementary Exam paper will be released on the class webpage (at https://webcms3.cse.unsw.edu.au/COMP9024/22T0/) at 2pm on Saturday 12 February 2022 (AEST, that is Sydney time). You need to submit answers by 05pm Saturday 12 February 2022 (AEST), that is after 3 hours. All the times are in Australian Eastern Standard Time (AEST), that is Sydney time zone.

Exam Conditions

You can start reading the exam at 2pm Saturday 12 February 2022 Sydney time.
You can start typing at 2pm Saturday 12 February 2022 Sydney time.
You have until 5pm Saturday 12 February 2022 Sydney time to complete this exam.
Only submissions before 5pm Saturday 12 February 2022 Sydney time will be marked.
Students with extra exam time approved by Equitable Learning Services (ELS) can make submissions after 5pm Saturday 12 February 2022 Sydney time within their approved extra time.
You are not permitted to communicate (email, phone, message, talk, social networks, etc.) with anyone during this exam, except COMP9024 staff.
Again, please note that you are not permitted to get help from anyone except COMP9024 staff during this exam.
You are not permitted to access web pages or other internet resources, except the the following web pages (for the exam, the lecture notes and documentation):
- you can access and read this exam paper!
- you can access the course material available on the course webpage and your assignment work.
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)
You are not permitted 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 permitted 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.
Even after you finish the exam, on the day of 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.
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.
Deliberate violation of exam conditions will be referred to Student Integrity as serious misconduct.

Special Consideration

By starting this exam you acknowledge that you are fit to sit the exam and cannot apply for Special Consideration for issues that existed prior to the exam.
If during the exam a circumstance arises that prevents you from completing the exam, please email cs9024@cse.unsw.edu.au immediately and apply for special consideration shortly after.
Before your Supplementary 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.

Admin

Marks: Contributes 50% towards your final mark
Submit: See the submission instructions for each question
Date and time: Saturday 12 February 2pm-5pm
Total Marks: 50

Structure

This exam consists of two parts:

Part 1: Short Answer questions (25 marks)
Part 2: Programming questions (25 marks)

Notes:

Answer all questions. Questions may not be worth equal marks. Questions may be answered in any order.
All answers must be submitted online using the provided instructions in the respective questions.
For programming questions, please note that marks are awarded primarily for your solution algorithm, not just for getting the correct final answer.

Part 1 (of 2): Short Answer Questions (25 marks)

Question 1 (3 marks)

An algorithm solves a problem of size n recursively by breaking it down into two subproblems of size n / 2 with the same structure, until the size of a subproblem is one or zero. It takes O(1) time to convert a problem of size n into two subproblems and it takes O(1) time to combine the results of two subproblems of size n into the result of the problem. What is the time complexity of this algorithm? Justify your answer.

Write your answer in q1.txt (download using "Save As" or similar).

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q1 q1.txt

Question 2 (3 marks)

An algorithm for solving a problem runs in exponential time O(2ⁿ). Suppose that your computer, running an implementation of this algorithm, can process an input of size 10 in one day. What is the maximum input size that can be processed in one day by a computer that is 1000 times faster if it uses the same implementation? Justify your answer.

Write your answer in q2.txt (download using "Save As" or similar).

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q2 q2.txt

Question 3 (3 marks)

Consider the the following 2-3-4 tree :

(a) What value(s) would be stored in the root node of the above 2-3-4 tree after the insertion of the value 8? What value(s) would be stored in the node that now contains 8? Note: if you need to promote a value, you must promote the smaller value from the available alternatives (if any). Justify your answer.

(b) What value(s) would be stored in the root node of the above 2-3-4 tree after the insertion of the value 50? What value(s) would be stored in the node that now contains 50? Note: if you need to promote a value, you must promote the smaller value from the available alternatives (if any). Justify your answer.

Write your answer in q3.txt (download using "Save As" or similar)..

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q3 q3.txt

Question 4 (4 marks)

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 non-increasing 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
Hashtable
Heap

Write your answer in q4.txt (download using "Save As" or similar)..

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q4 q4.txt

Question 5 (3 marks)

While constructing the above minimum spanning tree, the edges were added in the following sequence:

A - E
C - D
E - B
E - C

Which one of the following algorithms discussed in the lectures was used to construct the above minimum spanning tree? Justify your answer.

Depth First Algorithm
Dijkstra's Algorithm
Prim's Algorithm
Kruskal's Algorithm

Write your answer in q5.txt (download using "Save As" or similar)..

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q5 q5.txt

Question 6 (3 marks)

A binary search tree contains the values 2, 7, 8, 10, 14, 16, 20, 24, 33, and 40. A pre-order traversal produces the sequence: 16, 10, 7, 2, 8, 14, 24, 20, 40, 33. Which one of the following sequences will be produced by a valid post-order traversal of the same tree? Briefly explain your answer.

2, 7, 8, 14, 10, 20, 33, 40, 24, 16
2, 8, 7, 14, 10, 20, 33, 40, 24, 16
2, 7, 8, 14, 10, 20, 33, 24, 40, 16
2, 7, 8, 10, 14, 20, 24, 33, 40, 16
None of the other choices are correct.

Write your answer in q6.txt (download using "Save As" or similar)..

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q6 q6.txt

Question 7 (3 marks)

Which of following statements about tries is not correct? Briefly explain your answer.

Searching for a word in a standard trie takes O(m) time, where m is the length of the longest word in the trie.
In a trie, no word can be a prefix of another word.
In a standard trie, each leaf node corresponds to a word.
A compressed trie is used to save memory for storing words.

Write your answer in q7.txt (download using "Save As" or similar)..

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q7 q7.txt

Question 8 (3 marks)

Which of the following statements about the Knuth-Morris-Pratt (KMP) algorithm is not correct?

The time complexity of the KMP algorithm is O(m + n), where m and n are the sizes of the pattern and the text, respectively.
The KMP algorithm is optimal in terms of time complexity.
When checking if the pattern occurs at a character in a text, the KMP algorithm always compares the first character of the pattern with the corresponding character in the text.
The failure function can be computed in O(m) time, where m is the size of the pattern.

Write your answer in q8.txt (download using "Save As" or similar)..

Submission

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

give cs9024 exam_q8 q8.txt

Part 2 (of 2): Programming Questions (25 marks)

Notes

You can implement as many helper functions as you need.
Note: If you get a "permission denied" error when you try to run the autotest script, you must first make the script executable using the command:
```
chmod +x autotest
```
You can use any code provided in lectures, tutorials, and practice question solutions. However, you must acknowledge the source (e.g., indicate the lecture slide, tutorial question, etc.) in a comment.
You must test your solutions on the CSE system (e.g., via VLAB or SSH) before making your final submission. This avoids issues due to different testing environments. If you do not do this, you are accepting that even if you have passed the autotests on your local machine, your code may contain errors that were not detected on your machine (e.g., due to differing architectures) that may cause it to fail tests during marking.

Part 2: Q1 (12 Marks)

Your task for this question is to implement the following function in the file nodesNotBalanced.c.

int nodesNotBalanced(BSTree t);

The function nodesNotBalanced(BSTree t) takes one argument: a binary search tree t, and returns the number of nodes that are not height balanced.

For this question, as discussed in the lectures (see here), we say the height of a tree is equal to the maximum path length from the root to a leaf node. A node is not height balanced if the absolute difference between the heights of its left subtree and right subtree is greater than one. The height of an empty tree is -1.

Important:

You must not modify the given tree.
The time complexity of your solution must be O(n), where n represents the number of nodes in the tree. If your solution is slower than O(n), the maximum mark you can attain for this question will be 5 (out of 12).
You must not use any arrays or call malloc (or any of its variants). If you don't satisfy this requirement, you will receive zero for this question.
Note that the provided autotest does not check the time complexity of your solution and does not check whether you are using arrays or malloc. Hence, you must check that you have met these requirements yourself.
You can only submit one file, nodesNotBalanced.c. So all your code must be in this file.

Download

Click here to download the zip file for this question.

Alternatively, if you are connected to the CSE system (e.g., via VLAB or SSH), you can copy the zip file using the following command:

$ cp /home/cs9024/public_html/22T0/exam/t24aeu67/supp22T0/q1-files.zip .

The Files

BSTree.c	Contains the implementation of basic binary search tree functions.
BSTree.h	Contains the definition of the binary search tree data structure and function prototypes.
testNodesNotBalanced.c	The test driver program. The program reads tree data from `stdin`, calls `nodesNotBalanced`, and outputs the answer to `stdout`. You must carefully study how your function is tested by `testNodesNotBalanced.c`. You can find out more about the behaviour of the `testNodesNotBalanced` program by looking at the files `testNodesNotBalanced.c`, `autotest` and the files in the `tests` directory. The files named `X.in` contain sample inputs for the test program and the corresponding expected outputs are in files named `X.exp`.
nodesNotBalanced.c	Contains `nodesNotBalanced`, the function you must implement. This is the only file you should modify.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases
autotest	A script that uses the tests in the tests directory to autotest your solution. You should only run this after you have tested your solution manually.

Examples

The following examples show the expected output for some different trees. The nodes that are not height balanced are shown in bold.

Displaying tree (sideways) 
        60
50

 -------  
nodesNotBalanced(t) returns: 0 
 -------

Displaying tree (sideways) 
        60
50
        30

 -------  
nodesNotBalanced(t) returns: 0 
 -------

Displaying tree (sideways) 
                                                96
                                        94
                                92
                        90
                80
        70
50
                44
        30
                20

 -------  
nodesNotBalanced(t) returns: 5 
 -------

Displaying tree (sideways) 
                        80
                70
        60
                55
50
                40
        30
                20
                        10

 -------  
nodesNotBalanced(t) returns: 0 
 -------

Displaying tree (sideways) 
                        140
                130
        120
100
        90
                80
                        70
                                60
                                        50
                                                40
                                                        30
                                                                20
                                                                        10

 -------  
nodesNotBalanced(t) returns: 9 
 -------

Displaying tree (sideways) 
45

 -------  
nodesNotBalanced(t) returns: 0 
 -------

Testing

You can compile and test your function using the following commands:

$ make       # builds the testNodesNotBalanced program
$ ./autotest # applies all the tests in the tests directory to the testNodesNotBalanced program

# applies only one given test case from the tests directory to the testNodesNotBalanced program
$ ./autotest test-number

You can find out more about the behaviour of the testNodesNotBalanced program by looking at the files testNodesNotBalanced.c, autotest and the files in the tests directory. The files named X.in contain sample inputs for the test program and the corresponding expected outputs are in files named X.exp.

For example, if you want to run test case 2, use the following command:

$ ./autotest 2

If you want to run all the sample test cases provided, use the following command:

$ ./autotest

After you run the tests, additional files will appear in the tests directory. X.out contains the output from running test X.

You can add debugging code to nodesNotBalanced.c or testNodesNotBalanced.c if you want, however, make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all the tests. You can also add any auxiliary functions to nodesNotBalanced.c that you think are necessary.

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

$ give cs9024 exam_q9 nodesNotBalanced.c

Please note that the submission script does not run any tests on your program. Thus, it is important that you test your program on the CSE system before submitting.

Make sure you thoroughly test your program! We will run further tests on your submission after the exam which may test different cases from the tests provided to you.

Part 2: Q2 (13 Marks)

Your task for this question is to implement the following function in the file rankPopularity.c.

void rankPopularity(Graph g, int src, double *mnV);

The function rankPopularity takes three arguments: a directed graph g, a source node src and an array mnV. For each node v that is reachable from src, the function should store its popularity rank in the array mnV at index v. For example, if node 2 is reachable from src, then when the function returns, mnV[2] should contain the popularity rank of vertex 2.

Popularity rank: Calculate a node's popularity rank using the following equation:

popularityRank(v) = (inDegree(v) / outDegree(v))

If outDegree(v) is zero, replace it with 0.5.

Please read the example below for more clarifications.

Important notes:

If a node is not reachable from src, the function should not calculate and store the popularity rank for that node. In other words, only nodes reachable from src are considered, and your function must not calculate and store popularity rank values for nodes not reachable from src. In the test program testRankPopularity.c, initially all values in mnV are set to -1. If a node is not reachable from src, the function must not change the corresponding value in mnV (i.e., it should remain as -1), otherwise you will fail that test case.
You can assume that the mnV array is large enough to store all the required popularity ranks. You can also assume that the given graph g will not have self-loops or parallel edges.
You must properly use either the DFS or BFS graph traversal algorithm in your solution. Otherwise, you will receive zero marks for this question.
There is no time complexity requirement for this question.
Note that the provided autotest does not check whether you are properly using DFS or BFS. Therefore, you must check that you have met this requirement yourself.
You can only submit one file: rankPopularity.c. So all your code must be in this file.
As discussed in the lectures, nodes are identified by integers between 0 and nV - 1 (inclusive), where nV is the number of nodes in the graph.

Download

Click here to download the zip file for this question.

Alternatively, if you are connected to the CSE system (e.g., via VLAB or SSH), you can copy the zip file using the following command:

$ cp /home/cs9024/public_html/22T0/exam/t24aeu67/supp22T0/q2-files.zip .

The Files

Graph.c	Contains the implementation of basic Graph ADT functions.
Graph.h	Contains the definition of the Graph ADT and function prototypes.
testRankPopularity.c	The test driver program. The program reads data, creates a Graph and calls the function `rankPopularity`, and outputs the answer to `stdout`. You must carefully study how your function is tested by `testRankPopularity.c`. You can find out more about the behaviour of the `testRankPopularity` program by looking at the files `testRankPopularity.c`, `autotest` and the files in the `tests` directory. The files named `X.in` are input files for the test program `testRankPopularity` and the corresponding expected outputs are in files named `X.exp`.
rankPopularity.c	Contains `rankPopularity`, the function you must implement. This is the only file you should modify.
Makefile	A Makefile to compile your code
tests/	A directory containing the inputs and expected outputs for some basic test cases
autotest	A script that uses the tests in the tests directory to autotest your solution.You should only run this after you have tested your solution manually. Note that this script only tests simple cases. You need to extensively test your program for a wide range of test cases.

Examples

For example, consider the following graph:

Popularity ranks for nodes reachable from node "4" in the above graph are:

popularityRank(1) = 3/1 = 3
popularityRank(3) = 2/2 = 1
popularityRank(4) = 1/2 = 0.5
popularityRank(5) = inDegree(5) / outDegree(5). Here, inDegree(5) is 3 and outDegree(5) is 0. So we need to replace outDegree(5) by 0.5 in the above equation, resulting in popularityRank(5) = (3) / (0.5) = 6.

Note that node "2" is not reachable from node "4", so it must be ignored.

Testing

You can compile and test your function using the following commands:

$ make       # builds the required testRankPopularity program
$ ./autotest # applies all the tests in the tests directory to the testRankPopularity program
# applies only one given test case from the tests directory to the testRankPopularity program
$ ./autotest test-number

You can find out more about the behaviour of the testRankPopularity program by looking at the files testRankPopularity.c, autotest and the files in the tests directory. The files named X.in contain sample input for the test program and the corresponding expected outputs are in files named X.exp.

For example, if you want to run test case 2, use the following command:

$ ./autotest 2

If you want to run all the sample test cases provided, use the following command:

$ ./autotest

After you run the tests, additional files will appear in the tests directory. X.out contains the output from running test X.

You can add debugging code to rankPopularity.c or testRankPopularity.c if you want, however, make sure that you remove it before testing and submitting, otherwise your output won't match the expected output and you'll fail all the tests. You can also add any auxiliary functions to rankPopularity.c that you think are necessary.

Once you are satisfied with your solution, submit it through the give command or via WebCMS (click here).

The give command is:

$ give cs9024 exam_q10 rankPopularity.c

Please note that the submission script does not run any tests on your program. Thus, it is important that you test your program on the CSE system before submitting.

Make sure you thoroughly test your program! We will run further tests on your submission after the exam which may test different cases from the tests provided to you.

End