advance algorithm analysis
CP5602 Assignment SPXX, JCUB/S Due by XXXX, 202X (no later than 5:00pm) Aim: This assignment is designed to help you improve your critical thinking and problem solving skills. It also helps you to be prepared for the final examination (i.e., strongly recommended to do this assignment). Requirements, Method of Submission, and Marking Criteria: Include your name on the first page. Answer all questions in a single document. Each question should begin on a new page. Show all your work. Providing an answer without explanation in which how did you acheive it, is not acceptable. If you use pen-and-paper you may submit a scan of your worksheet. Upload your solution to the Assignment Box, located in the subject’s site. 1. Consider recurence T (n) = 2T (n/2) + n. (a) Use the recursion tree to give tight Big-Oh asymptotic bound for this recurence. [1 mark] (b) Use the substitution method to support your computed bound in item (a). [1 mark] 2. 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. [1 mark] (b) T (n) = 4T (n/2) + n3 lg n. [1 mark] 3. Let A = 〈10, 6, 27, 21, 44, 16, 6, 32, 49〉 be an array associated with a complete binary tree (i.e. 10 is the root, with 6 as its left child and 27 as its right child, and so forth). (a) Using Figure 6.3 as a model, illustrate the operation of BUILD-MAX-HEAP on the array. [1 mark] (b) Using Figure 6.4 as a model, illustrate the operation of HEAPSORT on the resulting heap of item (a). [1 mark] 1 4. Using Figure 7.1 as a model (i.e., choosing the last element as pivot), illustrate the operation of PARTITION (used in Quick-sort algorithm) on the array A〈13, 35, 9, 25, 12, 8, 37, 14, 33, 2, 16, 17〉. [1 mark] 5. Consider inserting the keys 31, 22, 32, 10, 25, 44, 14, 18, 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 up to the point that algorithm fails. (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, 15, 10). That is: matrix dimension ———– ————— A1 7× 10 A2 10× 5 A3 5× 18 A4 18× 20 A5 20× 15 A6 15× 10 [2 marks] 7. Determine an LCS (Longest Common Subsequence) of sequences X = (A,L,G,O,R, I, T,H,M) and Y = (L,O,G,A,R, I, T,H,M). [2 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. Show the results of inserting the keys 18, 55, 50, 34, 8, 36, 23, 60, 67, 70, 40, 53, 42, 48, 2, 5, 73, 77, 12, 80, 16 in order into an empty B-tree with minimum degree 2. Draw only the configurations of the tree just before some node must split, and also draw the final configuration. [1 marks] 10. Consider a directed graph G in Figure 1. Using vertex p as the source, and assuming that all nodes are required to be discovered in alphabetic order; 2 Figure 1: Directed graph G. (a) Show the d and π values that result from running breadth-first search on graph G, [1 mark] (b) Show how depth-first search (DFS) works on the graph G. [1 mark] (d) Determine the strongly connected components of graph G (use DFS on the transpose graph of G). [1 mark] 11. Find all integers x that have remainders 1, 2, 3 when divided by 11, 12, 13 respectively. [1 mark] 3