COMP20007 Design of Algorithms, Semester 1, 2021 School of Computing and Information Systems COMP20007 Design of Algorithms Semester 1, 2021 Sample Exam Instructions to Students • This exam counts for 60% of your final grade. • You should allow at least 15 minutes to scan and upload your solutions. • The test is open book, which means you may only use course materials provided via the LMS or the text book but must not use any other resource including the Internet. • You must not communicate with other students or make use of the Internet. • Solutions must be written on separate pieces of paper with pen or pencil. You must write your solution to each question on a new sheet of paper and clearly indicate which question you are answering on each page. • You must not use a tablet to complete this test. • You must indicate which question is answered on which page via Gradescope. • You must use a Scanner app on your smartphone to scan your solutions, email them to your laptop and then submit a PDF file to Gradescope via Canvas. • A Gradescope guide to scanning your test can be found here: https://gradescope-static-assets.s3-us-west-2.amazonaws.com/help/submitting_ hw_guide.pdf Page 1 of 7 COMP20007 Design of Algorithms, Semester 1, 2021 Question 1 [10 Marks] (a) Perform mergesort on the array [ 25, 23, 17, 29, 7, 16, 33, 21 ] , showing the result after each recursive call. Indicate which range of elements are being considered during each recursive call by outlining those elements. [2 marks] (b) Which two operations must a queue implement? Give the name and a brief description of these two operations. [2 marks] (c) Describe how you would implement a queue using a singly linked list to ensure that both of these operations run in O(1) time. [1 mark] (d) Insert the characters C, O, M, P, L, E, X, I, T, Y into an initially empty 2-3 tree. You must show the state of the 2-3 tree after every insertion. [2 marks] (e) Describe which two rotations must be done to balance the following tree? Give the node and the direction of the rotation (left or right). [1 mark] I C M A D Y N (f) Describe how performing a right rotation of the tree above would change the in-order traversal of the tree. You should give the resultant in-order traversal as part of your answer. [2 marks] Page 2 of 7 COMP20007 Design of Algorithms, Semester 1, 2021 Question 2 [9 Marks] (a) Demonstrate how to search for the pattern EAR in the text STRINGSEARCH using Horspool’s algorithm. How many comparisons were made? [1 mark] (b) A pair of strings are anagrams of each other if they contain the exact same letters, for example "DESSERTS" and "STRESSED" are anagrams. Write an algorithm which takes as input two strings, S and T , and determines whether or not they are anagrams. Your algorithm should run in O(n) time where n := max{|S|, |T |}. You may assume that all characters in S and T are uppercase alphabetic characters. [4 marks] (c) Write an algorithm which takes as input an array of n strings, of length no longer than m characters long, and outputs the largest set of strings which are all anagrams of each other. For example, given the array [ "ABC", "ABBA", "CAB", "BABA", "CBA", "BAC", "BAD" ] your algorithm would output "ABC", "CAB", "CBA", "BAC" (not necessarily in that order). Your algorithm must run in O(mn log n) time. You may again assume that all characters are uppercase alphabetic characters. [4 marks] Page 3 of 7 COMP20007 Design of Algorithms, Semester 1, 2021 Question 3 [8 Marks] (a) For each of the following, explain whether f(n) ∈ O(g(n)), f(n) ∈ Ω(g(n)), or f(n) ∈ Θ(g(n)). Only solutions with sufficient justification will be awarded marks. (i) f(n) = log(n) and g(n) = log(log(n)) (ii) f(n) = log3(n) and g(n) = log2(n 2) (iii) f(n) = 100 √ n + 0.01n2 + 0.001n3 and g(n) = n (iv) f(n) = log n + n2 and g(n) = n [4 marks] (b) Solve, using the method of repeated substitutions, the following recurrence relation. You must give a closed form expression and a Big-Theta bound for T (n). T (n) = 2T (n− 1) + 7, T (2) = 0 [2 marks] (c) Consider the following sorting algorithm: function ChunkSort(A[0 . . . n− 1]) if n == 2 and A[0] > A[1] then swap A[0] and A[1] else ChunkSort(A[0 . . . n 2 − 1]) ChunkSort(A[n 2 . . . n− 1]) ChunkSort(A[n 4 . . . 3n 4 − 1]) ChunkSort(A[0 . . . n 2 − 1]) ChunkSort(A[n 2 . . . n− 1]) ChunkSort(A[n 4 . . . 3n 4 − 1]) Write the recurrence relation (including the base case) for the number of comparisons of Chunk-Sort. [1 mark] (d) Recall, the master theorem states that if T is a recurrence relation such that T (n) = aT (n b )+ Θ(nc) and T (1) = constant then, T (n) ∈  Θ (nc) if c > logb(a) Θ (nc log n) if c = logb(a) Θ ( nlogb(a) ) if c < logb(a) . Use the master theorem to find the time complexity of ChunkSort. [1 mark] Page 4 of 7 COMP20007 Design of Algorithms, Semester 1, 2021 Question 4 [10 Marks] (a) Consider a hash table with 8 slots and a hash function h(k) = k mod 8, which uses open addressing with a step size of 1. Show the contents of the table after inserting 16, 23, 7, 10 and 12. [2 marks] (b) How many comparisons are required to lookup the key 7? Indicate which comparisons are performed. You can assume that we can check if a slot is empty without making any comparisons. [1 mark] (c) How many comparisons are required to lookup the key 15? Indicate which comparisons are performed. You can assume that we can check if a slot is empty without making any comparisons. [1 mark] (d) Consider again a hash table with 8 slots and a hash function h1(k) = k mod 8. This time, the hash table uses open addressing and double hashing, with the step size determined by the hash function h2(k) = k mod 3 + 1. Explain why h2(k) must contain the +1 term? [1 mark] (e) Show the state of the hash table after using this double hashing scheme (i.e., the scheme described in Part (d)) to insert 9, 17, 4 and 11 into an empty hash table. [1 mark] (f) Use Huffman’s algorithm to construct a Huffman tree for the string "free-coffee". [2 marks] (g) What is the encoded version of this string, using your Huffman tree? Let each left child be 0 and each right child be 1. Give the total length of the encoding in bits. [1 mark] (h) Using the following Huffman tree (again, using 0 for left and 1 for right), give the codes for f, o, t, and y and decode 0111001000. o f y t [1 mark] Page 5 of 7 COMP20007 Design of Algorithms, Semester 1, 2021 Question 5 [10 Marks] (a) A string of parentheses ("(" and ")") is valid if no pair of parentheses is “closed” before it is “opened”, "(())()" is valid while "())(" is not. The 5 valid strings of 6 parentheses are: "()()()", "(())()", "()(())", "(()())" and "((()))". Give 3 (three) examples of valid strings of parentheses containing 8 (eight) parentheses. [1 mark] (b) Write a recursive formula and base case(s) for the subproblem Ni, where Ni is defined as the number of different valid strings containing exactly i parentheses. [4 marks] (c) Using the recursive formula you derived in Part (b) write pseudocode for an algorithm which computes the number of different valid strings containing n parentheses. [3 marks] (d) What is the space complexity of your algorithm? Give an answer in Big-Theta notation and justify your answer. [1 mark] (e) What is the time complexity of your algorithm? Give an answer in Big-Theta notation and justify your answer. [1 mark] Page 6 of 7 COMP20007 Design of Algorithms, Semester 1, 2021 Question 6 [13 Marks] (a) Show how we interpret the array [ null, 8, 4, 3, 5, 2, 13, 6, 4 ] as a tree with the indexing scheme used for heaps. [1 mark] (b) Run the bottom-up construct heap algorithm to convert this array into a max-heap. Show the state of the heap (in tree form) after each step, indicating exactly which operations are being performed. [2 marks] (c) Now show the state of the heap after one RemoveMax operation. Which element is returned after this operation is performed? [1 mark] (d) Give the weights matrix for the following graph. [1 mark] 1 2 3 4 3 -1 22 5 (e) Run Floyd’s algorithm to find the shortest paths between each pair of vertices in the graph from part d. Write the matrices after each step of the algorithm [3 marks] (f) Describe what the time complexity of Floyd’s algorithm is (assume the graph has n vertices and m edges). [1 mark] (g) Using Dijkstra(G, u, v) as a helper function which returns the cost of the shortest path between u and v in a graph G, write an algorithm in pseudocode for computing the all pairs shortest paths in a graph G with non-negative edge weights. The graph G has n vertices and m edges and is sparse, i.e., m ∈ O(n). Your algorithm must have a time complexity better (i.e., smaller) than Floyd’s algorithm. [3 marks] END OF TEST Page 7 of 7








































































































































































































































学霸联盟