Hello/Please find attached document
CP5602 Assignment SP2, Townsville Due by Friday November 1, 2019 (no later than 5:00pm) Aim: This assignment is designed to help you improve your critical thinking and problem solving skills. Requirements, Method of Submission, and Marking Criteria: • Answer all of the following questions in a single document. Each question should begin on a new page. • Include your name on the first page. Include list of references (if any) for each question with proper in-text citations. • Show all your work. • Upload your solution to the Assignment Box, located in the subject’s site. 1. Use the master method to give tight asymptotic bounds for the following recurrences (if the master method cannot be applied give your argument): (a) T (n) = 8T (n/2) + n2. (b) T (n) = 8T (n/2) + n2 lg n. [2 marks] 2. Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array A = 〈10, 6, 27, 121, 44, 16, 6, 32, 49〉. [1 mark] 3. Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the array A = 〈25, 3, 12, 5, 7, 27, 20, 18, 34, 45〉. [1 mark] 4. Using Figure 7.1 as a model, illustrate the operation of PARTITION on the array A〈3, 19, 9, 25, 12, 8, 37, 14, 33, 2, 16, 17〉. [1 mark] 1 5. Consider inserting the keys 21, 22, 32, 10, 25, 28, 17, 38, 9 into a hash table of length m = 11 using open addressing with the auxiliary hash function h′(k) = k. Illustrate the result of inserting these keys (a) using linear probing, [1 mark] (b) using quadratic probing with c1 = 1 and c2 = 3, and [1 mark] (c) using double hashing with h1(k) = k and h2(k) = 1 + (k mod (m− 1)). [1 mark] 6. Find an optimal parenthesization of a matrix-chain product whose sequence of dimensions is (7, 10, 5, 18, 20, 40, 10, 15). That is: matrix dimension ———– ————— A1 7× 10 A2 10× 5 A3 5× 18 A4 18× 20 A5 20× 40 A6 40× 10 A7 10× 15 [3 marks] 7. Determine an LCS (Longest Common Subsequence) of sequences A = (1, 1, 1, 0, 0, 0, 1, 0, 1) and B = (0, 1, 0, 1, 0, 0, 1, 1). [3 marks] 8. What is an optimal Huffman code for the following set of frequencies? a:1, b:1, c:2, d:3, e:5, f:8, g:13, h:21, i:34. [1 marks] 9. Consider a directed graph G, where its adjacency-matrix is: q r s t u v w x y z q 0 0 1 1 0 0 1 0 0 0 r 0 0 0 0 1 0 0 0 1 0 s 0 0 0 0 0 1 0 0 0 0 t 0 0 0 0 0 0 0 1 1 0 u 0 0 0 0 0 0 0 0 1 0 v 0 0 0 0 0 0 1 0 0 0 w 0 0 1 0 0 0 0 0 0 0 x 0 0 0 0 0 0 0 0 0 1 y 1 0 0 0 0 0 0 0 0 0 z 0 0 0 0 0 0 0 1 0 0 2 (a) Show the d and π values that result from running breadth-first search on graph G, using vertex q as the source. [1 mark] (b) Show how depth-first search works on the graph G. [1 mark] (c) Show the parenthesis structure of the depth-first search. [1 mark] (d) Show the parenthesis structure of the depth-first search on graph G. [1 mark] (e) Determine whether or not the graph G is strongly connected. [1 mark] 3