Blog

19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 2 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam 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 cs2521@cse.unsw.edu.au 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 check your submission status for a particular question, use the command 2521 classrun check question, where question is the name of a particular submission. For example: $ 2521 classrun check exam_q1 Programming Questions General Constraints and Assumptions All inputs will be valid. No error checking is necessary. You may define your own helper functions in the files to be submitted. You may not #include any additional libraries. You may use any functions provided by the #included libraries. You may add your own #defines and define your own structs/enums. You must not use global variables or static variables. Solutions that do so will receive zero marks. You must not start any new programs or communicate with external programs. Marking You should ensure that your code works on CSE machines. 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 Marks Contributes 50% towards your final mark Submit See the submission instructions for each question 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 3 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Submit See the submission instructions for each question Date and time 2pm to 5pm Thursday 5 May 2022 (Sydney time) Total Marks 100 Total number of questions 11 (not worth equal marks) Note: the actual final exam may have a different number of questions Structure This exam consists of two parts: Written short/extended answers (50 marks) Programming questions (50 marks) Setting Up Change into the directory you created for the sample exam and run the following command: $ unzip /web/cs2521/22T1/exams/sample/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 (5 marks) An algorithm solves a problem of size recursively by breaking it down into two subproblems of size with the same structure, until the size of a subproblem is one or zero. It takes time to solve a (sub)problem of size one or zero. It takes time to convert a problem of size into two subproblems and it takes time to combine the results of these subproblems into the result of the problem of size . What is the time complexity of this algorithm Justify your answer. Write your answer in q1.txt. Submission Submit via the give command $ give cs2521 sample_exam_q1 q1.txt NOTE: Since this is the sample exam, these submission commands will not actually work. Question 2 (5 marks) Please note that the topics covered in the final exam may be different to the topics covered in this sample exam. Also, the mark distribution across topics may vary. n n/2 O(1) O(n) n O(n) n 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 4 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Consider the following algorithm, which converts a positive integer to its binary representation. BinaryConversion: Input positive integer n Output binary representation of n on a stack create empty stack S while n > 0 do push (n mod 2) onto S n = floor(n / 2) end while return S What is the time complexity of the algorithm Assume that creating a stack and pushing an element onto a stack are both operations (i.e., constant). Justify your answer. Write your answer in q2.txt. Submission Submit via the give command $ give cs2521 sample_exam_q2 q2.txt Question 3 (5 marks) Consider the the following 2-3-4 tree : (a) (2 marks) 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 of the two middle values. Justify your answer. (b) (3 marks) 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 of the two middle values. Justify your answer. Write your answers in q3.txt. Submission Submit via the give command $ give cs2521 sample_exam_q3 q3.txt Question 4 (7 marks) Consider the following trie. Finishing nodes are shown in red. n O(1) 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 5 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam (a) (1 mark) How many words are stored in this trie (b) (2 marks) Which nodes would be visited in searching for “deeds” (c) (2 marks) What new nodes would be created if the word “bogus” was added to the trie Justify your answer. (d) (2 marks) What new nodes would be created if the word “do” was added to the trie Justify your answer. Write your answers in q4.txt. Submission Submit via the give command $ give cs2521 sample_exam_q4 q4.txt Question 5 (6 marks) (a) (2 marks) What is the difference between an Euler path and a Hamilton path (b) (2 marks) Does the graph below have any Euler paths If so, give one of them. If not, explain why. (c) (2 marks) Does the graph below have any Hamilton paths If so, give one of them. If not, explain why. Write your answers in q5.txt. 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 6 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Submission Submit via the give command $ give cs2521 sample_exam_q5 q5.txt Question 6 (6 marks) This question is about the array-based implementation of a max heap. (a) (3 marks) Suppose the original state of the heap is: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] — Q N H D K E — — — Show the state of the heap after performing each of the following operations: join(pq, S) join(pq, P) Note that the “join(pq, P)” operation should be performed on the state of the heap obtained after performing the “join(pq, S)” operation. (b) (3 marks) Suppose the original state of the heap is: [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] — Q N H D K E — — — Show the state of the heap after performing each of the following operations. What are the values of it1 and it2 it1 = leave(pq) it2 = leave(pq) Note that the “it2 = leave(pq)” operation should be performed on the state of the heap obtained after performing the “it1 = leave(pq)” operation. Write your answers in q6.txt. Submission Submit via the give command $ give cs2521 sample_exam_q6 q6.txt Question 7 (8 marks) Consider a hash table of integer keys with 11 slots and a primary hash function of . Consider the following sequence of values: 10, 12, 28, 35, 25, 32, 20, 17, 24, 39 (a) (4 marks) Suppose the hash table described above uses linear probing for collision resolution. Show the final contents of the hash table after the values above have been inserted into an initially empty table in the order given. Give the cost, in terms of the number of keys examined, when searching for the key value 6 in the resulting table. (b) (4 marks) Suppose the hash table described above uses double hashing for collision resolution, with a secondary hash function of . Show the final contents of the hash table after the values above have been inserted into an initially empty table in the order given. Give the cost, in terms of the number of keys examined, when searching for the key value 6 in the resulting table. h(k) = k % 11 h2(k) = 1 + (k % 5) 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 7 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Write your answers in q7.txt. Submission Submit via the give command $ give cs2521 sample_exam_q7 q7.txt Question 8 (8 marks) Suppose you are given four sort programs each implementing one of the following sorting algorithms, but you are not told which one is which: bubble sort insertion sort merge sort naive quicksort Describe in detail the steps you would perform to tell the sort programs apart. Note: It is not known whether the bubble sort scans from left to right or from right to left. Write your answer in q8.txt. Submission Submit via the give command $ give cs2521 sample_exam_q8 q8.txt Question 9 (10 marks) Implement the function totalTextSize in q9/totalTextSize.c, which takes a pretend file system (represented by a system of linked lists) and returns the total size of all the text files in the pretend file system. The size of a text file is simply the length of the text in the file. The pretend file system contains two types of files: directories (also known as folders) and text files. (Yes – directories are a type of file.) The data structures used to implement the pretend file system are defined in Fs.h. Each file is represented by an instance of struct File, where the type field is used to distinguish between file types (directory or text file). Each directory has a linked list of files that are contained within that directory. Each text file contains some text, represented by a string. The file system as a whole is represented by an instance of struct Fs, which contains a pointer to the root/top-level directory. Constraints All general constraints and assumptions at the top of this exam paper apply You must not open any files – you are given a pretend file system represented by linked lists, not a real file system. The given pretend file system must not be modified You must not use arrays or any variant of malloc (malloc, calloc or realloc). If you do, you will receive zero for this question. Files Makefile A Makefile to compile your code Fs.c Contains the implementation of some in-memory file system functions 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 8 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Fs.h Contains the definition of the in-memory file system data structure and function prototypes testFs.c A testing program. This program takes a test number as a command-line argument, sets up the file system corresponding to that test number, calls totalTextSize, and outputs the result to stdout. totalTextSize.c Contains totalTextSize, the function you must implement. This is the only file you should modify (except when adding your own tests in testFs.c). tests/ A directory containing the expected outputs for some basic tests Example $ ./testFs 1 File system: / a b.txt c.txt d e.txt Total text size: 49 Testing You can compile and test your function using the following commands: $ make # compiles the program $ ./testFs 1 # runs test 1, outputs to terminal (now compare with tests/output1.txt) $ ./testFs 2 # runs test 2, outputs to terminal (now compare with tests/output2.txt) It is possible to devise your own tests by modifying testFs.c. See the existing test functions for a demonstration of how to construct a file system. Submission Submit via the give command $ give cs2521 sample_exam_q9 totalTextSize.c Question 10 (20 marks) A contiguous subsequence of a list is a sequence made up of consecutive elements of . For example, the contiguous subsequences of the list [5, 3, 8] are: [5, 3, 8] [5, 3] [3, 8] [5] [3] [8] [] For this question, we introduce the notion of a tolerance, which indicates the number of mismatches allowed while looking for a contiguous subsequence. Your task is to implement the following function in the file q10/numSubsequences.c: int numSubsequences(List listA, List listB, int tolerance); The function takes two lists, listA and listB, and a tolerance, and returns the number of times listB appears as a contiguous L L 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 9 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam subsequence of listA with the given tolerance. Important: You must clearly state the worst case time complexity (in big O notation as discussed in the lectures) of your solution in a comment just above the function. The time complexity should be in terms of and , where is the length of list and is the length of list . Example Consider the two lists below: List : 50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9 List : 50 9 25 67 If the tolerance is zero (no mismatch is allowed), list only appears once in as shown below: 50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9 If the tolerance is one (one mismatch is allowed), list appears twice in : from index 5 to 8, and from index 10 to 13 (index 10 is a mismatch): 50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9 If the tolerance is two (two mismatches are allowed), list appears three times in : from index 0 to 3 (with mismatches at indices 1 and 3), from index 5 to 8 and from index 10 to 13 (with a mismatch at index 10): 50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9 Please note that it is possible for the subsequences that appear to overlap. For example, suppose we have the following lists: List : 5 5 5 5 6 6 List : 5 5 5 If the tolerance is zero, list appears twice in list : 5 5 5 5 6 6 5 5 5 5 6 6 If the tolerance is one, list appears three times in list : 5 5 5 5 6 6 5 5 5 5 6 6 5 5 5 5 6 6 If the tolerance is two, list appears four times in list : 5 5 5 5 6 6 5 5 5 5 6 6 5 5 5 5 6 6 5 5 5 5 6 6 Constraints and Assumptions All general constraints and assumptions at the top of this exam paper apply will be non-empty The tolerance will be between and (inclusive) The given lists must not be modified You must not use arrays or any variant of malloc (malloc, calloc or realloc). If you do, you will receive zero for this question. n m n A m B A B B A B A B A A B B A B A B A B 0 length(B) 1 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 10 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Files Makefile A Makefile to compile your code list.c Contains the implementation of basic linked list functions list.h Contains the definition of the linked list data structure and function prototypes testNumSubsequences.c A testing program. The program reads list data and the tolerance from stdin, calls numSubsequences, and outputs the result to stdout. numSubsequences.c Contains numSubsequences, 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 $ ./testNumSubsequences 5 5 5 5 6 6 List A: 5, 5, 5, 5, 6, 6 5 5 5 List B: 5, 5, 5 2 Tolerance: 2 numSubsequences returned: 4 $ ./testNumSubsequences 50 25 25 12 67 50 9 25 67 98 34 9 25 67 25 9 List A: 50, 25, 25, 12, 67, 50, 9, 25, 67, 98, 34, 9, 25, 67, 25, 9 50 9 25 67 List B: 50, 9, 25, 67 1 Tolerance: 1 numSubsequences returned: 2 $ ./testNumSubsequences List A: 1 2 3 List B: 1, 2, 3 0 Tolerance: 0 numSubsequences returned: 0 In the last example, an empty list was created by pressing enter without typing any numbers. Testing You can compile and test your function using the following commands: $ make # compiles the program $ ./testNumSubsequences # tests with manual input, outputs to terminal $ ./testNumSubsequences < input-file # tests with input from a file, outputs to terminal $ ./testNumSubsequences < tests/input1.txt # for example, tests with input from tests/input1.txt # (then 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 sample_exam_q10 numSubsequences.c 19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam Page 11 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam Question 11 (20 marks) Implement the following function in the file q11/findPopularFollowers.c: void findPopularFollowers(Graph g, int src, int followers[]); findPopularFollowers takes three arguments: a directed graph g, a source node src, and an array followers. Given a graph g, the function should find all popular followers of a given node (src) and for each popular follower i, sets followers[i] to 1. For example, followers[2] should contain 1 if node 2 is a popular follower of the given source (src). Initially, all values in the followers array are set to -1. followers[i] should remain as -1 if i is not a popular follower of src. We say a node A is a popular follower of node B if the following two conditions are true. There is a directed path from node A to node B, OR A = B (node itself). For node A, inA > outA, where inA represents incoming links of node A and outA represents outgoing links of node A. Important: You must clearly state the worst case time complexity (in big O notation as discussed in the lectures) 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: You must implement your solution efficiently; we will consider how efficiently you have implemented your solution when we award you marks. Inefficient solutions will be penalised. In the following example graph, for the source node 2, there are two popular followers: nodes 2 and 3. Both these nodes satisfy the requirements mentioned above. Just to clarify, there is a directed path from node 0 to node 2 (src), however for node 0, in-degree is not greater than out-degree, so node 0 is not considered as a popular follower of node 2. Examples n 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 12 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam $ ./testFindPopularFollowers < tests/input3.txt nV: 7 src: 2 Edge inserted: 1 -> 6 Edge inserted: 0 -> 5 Edge inserted: 3 -> 1 Edge inserted: 1 -> 4 Edge inserted: 4 -> 3 Edge inserted: 0 -> 3 Edge inserted: 0 -> 1 Edge inserted: 1 -> 0 Edge inserted: 5 -> 6 Edge inserted: 1 -> 2 Popular followers of node 2: node 2 node 3 $ ./testFindPopularFollowers < tests/input2.txt nV: 8 src: 7 Edge inserted: 1 -> 3 Edge inserted: 0 -> 3 Edge inserted: 2 -> 3 Edge inserted: 4 -> 3 Edge inserted: 3 -> 0 Edge inserted: 0 -> 5 Edge inserted: 1 -> 5 Edge inserted: 4 -> 5 Edge inserted: 5 -> 2 Edge inserted: 5 -> 7 Edge inserted: 1 -> 4 Edge inserted: 2 -> 4 Edge inserted: 0 -> 6 Edge inserted: 3 -> 7 Popular followers of node 7: node 3 node 5 node 7 Note that the first example corresponds to the diagram above. Constraints and Assumptions All general constraints and assumptions at the top of this exam paper apply The size of the followers array is equal to the number of vertices in the graph. All values in the followers array are initially -1. Files Makefile A Makefile to compile your code Graph.c Contains the implementation of the Directed Graph ADT (using the adjacency matrix representation) Graph.h Contains the definition of the Directed Graph ADT and function prototypes testFindPopularFollowers.c A testing program. The program reads graph data from stdin, calls findPopularFollowers, 19/5/22, 2:17 PMCOMP2521 22T1 – Sample Exam Page 13 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-exam and outputs the result to stdout. findPopularFollowers.c Contains findPopularFollowers, 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 Testing You can compile and test your function using the following commands: $ make # compiles the program $ ./testFindPopularFollowers # tests with manual input, outputs to terminal $ ./testFindPopularFollowers < input-file # tests with input from a file, outputs to terminal $ ./testFindPopularFollowers < tests/input1.txt # for example, tests with input from tests/input1.txt # (then 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 sample_exam_q11 findPopularFollowers.c This is the end of the exam paper. 19/5/22, 2:17 PMCOMP2521 22T1 - Sample Exam Page 14 of 14https://cgi.cse.unsw.edu.au/~cs2521/22T1/sample-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 cs2521@cse.unsw.edu.au CRICOS Provider 00098G