CP5602 Assignment: Algorithms & Data Structures
Answer all questions in a single document. Each question should begin on a new page.
Providing an answer without explanation in which how did you achieve it, is not acceptable. Show all your work (Partial mark applies).
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.
Consider recurrence T (n) = T (n/2) + n.
(a) Use the recursion tree to give tight Big-Oh asymptotic bound for this recurrence. [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) + n3. [1 mark]
(b) T (n) = 8T (n/2) + n2 lg n. [1 mark]
3. Let A = (21, 16, 49, 32, 22, 5, 6, 21, 60) be an array associated with a complete binary tree (i.e. 21 is the root, with 16 as its left child and 49 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]
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(3, 5, 19, 15, 12, 18, 17, 24, 23, 21, 6, 7). [1 mark]
Consider inserting the keys 20, 0, 21, 10, 3, 33, 25, 29,42 into a hash table of length m = 11 using open addressing with the auxiliary hash function ht(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 (5,8, 7, 9, 20). That is: matrix dimension———– —————
A1 5 × 8
A2 8 × 7
A3 7 × 9
A4 9 × 20
[1 mark]
Consider the m-table of Figure 1 that is generated from matrix chain multiplication of A1×· · ·×A6. Discuss that the first cut on multiplications of A1 ×· · ·×A6. cannot be 3. That is, in the associated s-table, the value in s[1, 6] cannot be 3. Conclude that (((A1 × A2) × A3) × ((A4 × A5) × A6)) cannot be a correct parenthesization for efficient solution to this matrix chain multiplication. Figure 1: m-table. [1 mark]
Determine an LCS (Longest Common Subsequence) of sequences X = (A, L, G, O, L) and Y = (G, O, A, L). [1 mark]
What is an optimal Huffman code for the following set of frequencies? a:1, b:2, c:4, d:7, e:9, f:10, g:13, h:18, i:25. [1 marks]
Show the results of inserting the keys 8, 25, 20, 4, 18, 6, 3, 30, 7, 10, 40, 33, 42, 38, 2, 5, 53, 47, 32, 41, 1 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. [2 marks]
Consider a directed graph G in Figure 2. Using vertex p as the source, and assuming that all nodes are required to be discovered in alphabetic order; Figure 2: 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]
Find all integers x that have remainders 4, 5, 6 when divided by 11, 12, 13 respectively. [1 mark]
