Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 1 School of Information Technology and Electrical Engineering EXAMINATION Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures This paper is for all students. Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 2 Question 1 (2 marks) What is the maximum possible number of external nodes in a binary tree with height 4 Give a brief description by drawing a resulting tree. Question 2 (1 mark) Consider the following Java program, containing a recursive method. When the class ContainsRecursion is run, the final line of output will be: Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 3 Question 3 (4 marks) a) Given two algorithms, A with O(n) time complexity, and B with Θ(n logn) time complexity, testing shows that algorithm B is faster than algorithm A in practice for all datasets tested. Give two possible reasons why this may be. (2 marks) b) Given two algorithms for performing a task, is it ever reasonable to use the algorithm with worse asymptotic performance Why or why not (2 marks) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 4 Question 4 (2 marks) Consider the following recurrences: R1(n) = 4 R1(n/2) + O(1) R2(n) = 2 R2(n/4) + O(1) Explain which one is asymptotically faster and why (2 marks) Question 5 (2 marks) Draw a table to represent the “last occurrence” function for the pattern P=”baccarat”, which is used as part of the Boyer-Moore pattern matching algorithm. Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 5 Question 6 (4 marks) A splay tree is populated by inserting into an empty tree the keys: 4, 15, 8, 16, 42, and 23, in that order. a) Draw the final tree. No need to include the external leaves in the drawing. (2 marks) b) What is the order that nodes are visited during a post-order traversal of the resulting tree (1 mark) c) Draw a different splay tree with the same post order traversal. (1 mark) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 6 Question 7 (2 marks) We defined a hash function h(s) = s.size(), for a hash table which stores a set of strings. a) Explain why h(s) is not a good hash function. Note: size() returns the length of the string. (1 mark) b) Suggest an alternative hash function or technique that would perform more suitably (and why ). (1 mark) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 7 Question 8 (4 marks) Arrays store a set of values by index using O(n) space, where n is the largest index in use. In some cases, most indices of the array are null, wasting space; such arrays are called sparse arrays. In other words, the number of non-default values stored m, is much smaller than the largest index n. a) Describe how you would efficiently implement a sparse array using a hash table. What would be the worst-case time complexity of standard array operations (insert, delete (moving indices of elements later in the array after deletion), and search an item) in Big-O notation, if we implement sparse arrays using hash tables (2 marks) b) Describe how you would efficiently implement a sparse array using a linked list. What would be the worst-case time complexity of standard array operations in Big-O notation, if we implement sparse arrays using linked lists (2 marks) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 8 Question 9 (2 marks) Below is a Huffman tree generated from the exact frequencies of the text: “this is an example of a huffman tree” Using the Huffman tree above, determine the binary code and count the number of bits required to transmit the text “fill pool” (do not forget the space separating the words). Note: Left branches represented a 0 bit and right branches represent a 1 bit. CODE= #BITS= Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 9 Question 10 (5 marks) For each of the following scenarios, suggest an efficient and suitable sorting algorithm (out of the ones we learned in this course), and explain why you chose it. Note: n potentially is very large. (a) We have an array consisting of n objects in random order. The objects are comparable, and not necessarily numbers. (1 mark) (b) We have an array consisting of n objects. The objects are comparable. Apart from d items (d< log2n) that are in random positions in this array, all the other items are in sorted order. (2 marks) (c) We have an array consisting of n random integers in the range of 0 to d, with d< log2n. (2 marks) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 10 Question 11 (4 marks) a) Given a semi-balanced binary tree with n nodes, where the number of leaves in the corresponding left and right subtrees differs at most by one. Explain the worst-case height of the tree. Note: Write the Big-O with respect to the number of nodes (n). (2 marks) b) Given a semi-balanced binary tree with n nodes, where the number of nodes in the left subtree is at most twice the number of nodes in the corresponding right subtree. Explain the worst-case height of the tree. Note: Write the Big-O with respect to the number of nodes (n). (2 marks) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 11 Question 12 (4 marks) Given an unweighted graph G with n vertices and the adjacency matrix A: a) Given a positive integer k, propose an algorithm (give a pseudo-code or explain in words) to calculate the number of walks (vertices/edges can be revisited) consisting of exactly k number of edges between vertices i and j. Your algorithm should return 0 if there are no walks of length k. (3 marks) b) What is the worst-case time complexity of your proposed algorithm in terms of n and k and explain why. (1 mark) Semester Two Final Examination, 2020 COMP3506/COMP7505 Algorithms and Data Structures 12 Question 13 (4 marks) Work out the most efficient Big-O time complexity of finding pth smallest element in a BST with m elements. Hint: The Big-O will be in terms of m and p. Describe in words your proposed algorithm. End of Examination
