10/11/2021, 12:23 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 1 (13 marks)
In the q1 directory is an implementation of a simple Matrix ADT, along with a main program to test it. The ADT contains functions to create, read, and remove matrices, as well as addition and multiplication functions to combine pairs of compatible matrices.
Your task for this question is to implement the multiply() function, which is currently incomplete. For two matrices X (with dimensions M¡ÁN) and Y (with dimensions N¡ÁP), multiplication produces a matrix Z (with dimensions M¡ÁP) whose elements are defined as follows:
The multiply() function takes two matrices as parameters, checks their compatibility, and then multiples the two matrices, storing the result in a newly-created matrix, and returning the new matrix as the result.
The overall structure of the multiply() function is somewhat like the structure of the existing add() function. But note that the compatibility check for matrix multiplication is different to the
compatibility check for matrix addition. Note also that all output, including error messages, should be written to the standard output.
The q1 directory contains the following:
Makefile … handles compilation and testing
Matrix.h … interface to the Matrix ADT
Matrix.c … implementation of the Matrix ADT
main.c … main program, used to produce an executable called q1 m0,m1,..,m6 … data files containing matrices to be read in
tests/ … a directory containing test scripts and expected outputs
The Makefile compiles the Matrix ADT and the main program in main.c to produce an executable program called q1. This program has three command-line arguments: an operation (add or mul), and the names of two files, where each file contains data for one matrix.
As supplied, the q1 program can perform matrix addition on two matrices which have the same number of rows and columns. A simple example of using this program would be:
$ ./q1 add m0 m0 Matrix X [12] [34] Matrix Y [12] [34] add(X,Y) [24] [68]
You compile and test the q1 program using the following commands:
$ make q1 # build the q1 program
$ check q1 # apply the tests in the tests directory to the q1 program
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q01.html
10/11/2021, 12:23 Sample Final Exam
You can find out more about the behaviour of the q1 program by looking at the files in the tests directory. The files named tX are test scripts. Each test script has a corresponding file tX.exp which contains the expected output from running that test. If you want to run the tests individually, use commands like:
Note that test t3 is supposed to produce an error; it is trying to multiply incompatible matrices. After you run the tests, additional files will appear in the tests directory: tX.out contains the
output of running test tX.
You can add debugging code to main.c or Matrix.c if you want, but make sure that you remove it before testing and submitting, otherwise your output won’t match the expected output and you’ll fail all of the tests. You can also add any auxiliary functions to Matrix.c that you think are necessary.
Once you are satisfied with your program, submit it using the command:
This will make a copy of the Matrix.c file from the q1 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that
your final submission compiles without any errors or warnings. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using additional test cases to the examples in the q1/tests directory.
$ sh tests/t1
$ submit q1
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q01.html 2/2
10/11/2021, 12:24 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 2 (15 marks)
In the q2 directory is an implementation of a simple HashTable ADT, along with a main program to test it. The ADT contains functions to build, remove and display hash tables, as well as a function to insert new keys into the table (in this table, keys are integer values). It uses collision resolution via chaining (i.e. it builds linked lists of keys that have the same hash value). The HashTable ADT implements its chains using a simple List ADT. It also has a private (and very simple) hash function, and an incomplete function to expand the size of the table, once the chains become too long.
As supplied, the program creates a hash table with 3 slots, reads numbers (keys) from standard input and builds a hash table using these keys. The hash table maintains its original 3 slots, regardless of how many keys are added, and the chains will grow longer and longer as more keys are added, e.g.
In the output from the program, the hash table is displayed one slot at a time, first showing the slot index (aka hash value) in square brackets (e.g. [ 0]) then showing all of the keys in the chain associated with that hash value. Since the hash function is implemented simply as (key%nslots), the above shows all of the keys with hash(key)==0 on the first line of output, all of the keys with hash(key)==1 on the second line of output, and so on.
Your task for this question is to implement the expand() function, which takes a hash table, doubles the number of slots in the table and rehashes all of the existing keys to their new slots (chains). You can achieve this however you like, but the pointer to the HashTable object must not be changed (i.e. you keep the same HashTable object but change what’s stored in it and linked from it). Also, you are not allowed to change the List ADT to achieve this (since you only submit HashTable.c, changing List.c won’t help your submission) and you may only access the chains via the interface given in List.h. (Hint: valuesFromList() is useful).
After you implement the expand() function correctly, the hash table will have more slots, but the chains will be shorter and searches will be more efficient, e.g.
$seq115|./q2 #withq2assupplied [ 0] 3->6->9->12->15
[ 1] 1->4->7->10->13
[ 2] 2->5->8->11->14
$ seq 1 15 | ./q2 [ 0] 12
[ 1] 1->13
[ 2] 2->14
[ 3] 3->15
# with q2 including expand()
The q2 directory contains the following:
Makefile … handles compilation and testing HashTable.h … interface to the HashTable ADT
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q02.html
10/11/2021, 12:24
Sample Final Exam
HashTable.c … implementation of the HashTable ADT List.h … interface to the List ADT
List.c … implementation of the List ADT
main.c … main program, used to produce an executable called q2 tests/ … a directory containing test scripts and expected outputs
The Makefile compiles the List and HashTable ADTs and the main program in main.c to produce an executable program called q2. This program reads integer keys from standard input, builds a hash table, and then displays the hash table (in the format shown above).
You compile and test the q2 program using the following commands:
You can find out more about the behaviour of the q2 program by looking at the files in the tests directory. The files named tX are test scripts. Each test script has a corresponding file tX.exp which contains the expected output from running that test. If you want to run the tests individually, use commands like:
You can add debugging code to main.c, HashTable.c or List.c if you want, but make sure that you remove it before testing and submitting, otherwise your output won’t match the expected output and you’ll fail all of the tests. You can add any auxiliary functions to HashTable.c that you think are necessary.
Once you are satisfied with your program, submit it using the command:
This will make a copy of the HashTable.c file from the q2 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that
your final submission compiles without any errors or warnings. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using additional test cases to the examples in the q2/tests directory.
$ make q2 # build the q2 program
$ check q2 # apply the tests in the tests directory to the q2 program
$ sh tests/t1
$ submit q2
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q02.html 2/2
10/11/2021, 12:24 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 3 (17 marks)
In the q3 directory is an implementation of a simple non-directed and non-weighted Graph ADT, along with a main program to test it. The ADT contains functions to create, build, remove and display graphs. Graphs are represented using an adjacency matrix, and each edge appears twice in the matrix (both (v,w) and (w,v)). Vertices are simply integer values in the range 0..N-1, where N is the number of vertices.
When graphs are used to represent networks such as the Web, it is often important to know which vertices are connected to many other vertices. We will call such vertices “well-connected”. In our context (of quite small graphs), a vertex is well-connected if it has edges to at least two other vertices.
The Graph ADT contains an incomplete function to generate an ordered sequence of well- connected vertices in a graph:
Your task for this question is to complete the implementation of the wellConnected() function. This function takes a graph and a pointer n to an integer variable, computes a sequence of well-connected vertices, and sets *n to a count of the number of well-connected vertices. The sequence consists of pairs (vertex,#conns), where #conns is a count of the edges incident on the vertex. The sequence is arranged in descending of the #conns values; where multiple vertices have the same #conns, the pairs are arranged in ascending order of the vertices. The pairs are implemented as an array of Connects structures; Connects is defined in Graph.h. You can see examples of what these sequences look like in the expected output files under the tests directory.
The main() function (in main.c), builds a graph, then displays details of the graph, and then computes and displays the sequence of well-connected vertices. The graph data is read from the X.in files in the tests directory. If you want a better idea of what the wellConnected() function produces, look at how its results are used in the main() function. Note that, as supplied, the wellConnected() function always says that there are zero well-connected vertices and the main program prints an appropriate message based on this.
The q3 directory itself contains the following:
Makefile … handles compilation and testing
Graph.h … interface to the Graph ADT
Graph.c … implementation of the Graph ADT
main.c … main program, used to produce an executable called q3 tests/ … a directory containing test scripts, input files and expected outputs
You compile and test the q3 program using the following commands:
You can find out more about the behaviour of the q3 program by looking at the files in the tests directory. The files named tX are test scripts. Each test script has a corresponding file tX.exp which contains the expected output from running that test. If you want to run the tests individually, use commands like:
Connects *wellConnected(Graph g, int *n)
$ make q3 # build the q3 program
$ check q3 # apply the tests in the tests directory to the q3 program
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q03.html 1/2
10/11/2021, 12:24 Sample Final Exam
$ sh tests/t1
You can add debugging code to main.c or Graph.c but make sure that you remove it before testing and submitting, otherwise your output won’t match the expected output and you’ll fail all of the tests. You can add any auxiliary functions to Graph.c that you think are necessary.
Once you are satisfied with your program, submit it using the command:
This will make a copy of the Graph.c file from the q3 directory as your answer for this question. You can run the submit command as many times as you like, but make sure that
your final submission compiles without any errors or warnings. Test your program thoroughly, possibly using test cases additional to those supplied. Your program will be tested using inputs which are different to the examples in the q3/tests directory.
$ submit q3
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q03.html 2/2
10/11/2021, 12:24 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 4 (8 marks)
Consider the following recursive binary search function and a possible use-case for the function:
// return the index of element containing key in array a[] // if key is not in the array, return -1
int bsearch(int key, int a[], int lo, int hi)
if (lo > hi)
return -1;
else if (lo == hi) {
if (key == a[lo])
return lo;
return -1;
int mid = (lo+hi)/2;
if (key < a[mid])
return bsearch(key, a, lo, mid-1);
else if (key > a[mid])
return bsearch(key, a, mid+1, hi);
else // (key == a[mid])
return mid;
int a[10] = {2,4,6,8,10,12,14,16,18,20};
int i, x, ncalls;
ncalls = 0;
i = bsearch(x, a, 0, 9);
printf(“bsearch was called %d times\n”,ncalls);
Based on the above answer the following questions:
A. What are the base cases for this recursion?
B. How many calls are made to the bsearch() function for each of the following values of x?
i. x == 4 ii. x == 9
iii. x == 12
(i.e. what is the value of ncalls after bsearch() returns its final result)
C. What are the smallest and largest number of calls to bsearch() needed to search in the above array (a[10])?
D. What are the smallest and largest number of calls to bsearch() needed to search in an array of size N?
Type the answer to this question into the file called q4.txt and submit it using the command: https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q04.html 1/2
10/11/2021, 12:24 Sample Final Exam
$ submit q4
The above command will make a copy of q4.txt as your answer for this question.
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q04.html 2/2
10/11/2021, 12:24 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 5 (9 marks)
Consider a scenario where we have
a hash table with 7 slots,
key values are positive integers,
a hash function h(x) = x%7,
a secondary hash function h2(x) = x%5
Based on the above answer the following questions:
A. In the ideal case (no collisions), what is the complexity of searching for a key in a hash
table with N slots?
B. Consider the scenario where the above hash table uses chaining for collision resolution, and has the following distribution of chain lengths: 2 slots are empty, 2 slots have a chain of length 1, 1 slot has a chain of length 2, 1 slot has a chain of length 3, and 1 slot has a chain of length 4.
i. What is the minimum number of key comparisons required to search for a key in this table?
ii. What is the maximum number of key comparisons required to search for a key in this table?
C. Now consider the scenario where the hash table uses linear probing for collision resolution. If we start from an initially empty hash table and insert the following keys (in the order supplied) into the table:
show the state of the hash table after the insertion of each key. (The q5.txt file contains a template for how to show the table, and even shows the state of the table after the insertion of the first key).
D. Now consider the scenario where the hash table uses double hashing for collision resolution, with h2 as the secondary hash function. If we start from an initially empty hash table and insert the following keys (in the order supplied) into the table:
show the state of the hash table after the insertion of each key. (The q5.txt file contains a template for how to show the table, and even shows the state of the table after the insertion of the first key).
Type the answer to this question into the file called q5.txt and submit it using the command:
The above command will make a copy of q5.txt as your answer for this question.
11 21 31 32 12 22 24
11 21 31 32 12 22 24
$ submit q5
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q05.html 1/1
10/11/2021, 12:24 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 6 (7 marks)
Consider the following binary search tree and a variable t which contains a pointer to the node
containing the key 20 (i.e. the root node):
Based on the above, answer the following questions:
A. Give the keys that would be examined, in the order that they are examined, when searching for the value 17 starting from the root node.
B. Show the order that key values would be be displayed if we performed a level-order traversal of the tree.
C. The above tree is perfectly balanced (i.e. every node has the same number of nodes in its left and right subtrees) and has a height of 4 (the number of nodes in the longest path from the root to a leaf). Give a formula for the number of nodes in a perfectly balanced tree of height n.
D. If the following function was applied to the original tree above (i.e. with root node containing key 20):
what would be the new value in the root node, and what would be the values in its immediate left and right children?
E. If the following function was applied to the original tree above (i.e. with root node containing key 20):
what would be the new value in the root node, and what would be the values in its immediate left and right children?
Use the definitions of rotateL() and deleteRoot() are in the Algorithms Almanac. Type the answer to this question into the file called q6.txt and submit it using the command:
The above command will make a copy of q6.txt as your answer for this question.
t = rotateL(t);
t = deleteRoot(t);
$ submit q6
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q06.html 1/1
10/11/2021, 12:24 Sample Final Exam
Sample Sample Final Exam COMP2521 [Instructions] [C language] [Algorithms]
[Q1] [Q2] [Q3] [Q4] [Q5] [Q6] [Q7] [Q8] [Q9]
Question 7 (9 marks)
Consider the following splay tree :
Based on the above answer the following questions:
A. Give an example of a key that would result in a worst case scenario for splay insertion in terms of time complexity. State the number of comparisons performed and show the resulting splay tree and state exactly what sequence of rotations were used.
B. Give an example of a key that would result in the worst case scenario for splay insertion in terms of the resulting height of the tree. Assume you are inserting into the origina tree, not the tree from your answer in part A. State the number of comparisons performed and show the resulting splay tree and state exactly what sequence of rotations were used.
C. Explain how your answers from part a and b relate the amortised time complexity of splay tree insertion and search.
D. Show the trees that would have resulted from performing the same insertions using normal root insertion.
Type the answer to this question into the file called q7.txt and submit it using the command:
The above command will make a copy of q7.txt as your answer for this question.
$ submit q7
https://www.cse.unsw.edu.au/~cs2521/19T0/exams/sample/14s2/Q07.html 1/1
10/11/2021, 12:25 Sample Final Exam
Sample Sample Final