Assignment 3 Advanced Algorithm Analysis (CP5602) Due Date: 2nd February 2020 at 11:59pm Total: 20 marks
Aim: This assignment is designed to evaluate/improve your critical thinking and problem solving skills. It also evaluate/improve your coding skill.
1. For a tree T, let nI denote the number of its internal nodes, and let nE denote the number of its external nodes. Show that if every internal node in T has exactly 3 children, then nE = 2nI + 1. [2 marks]
2. Insert entries with keys, 2, 7, 3, 12, 5, 20, 14, 6, 11, 8, 15, 17, 1, 19, 23, 14 (in this order), into an empty:
(a) heap. [1 mark] (b) binary search tree. [1 mark] (c) AVL tree. [1 mark] (d) (2, 4) tree. [1 mark]
[4 marks] 3. Draw the 13-entry hash table that results from using the hash function h(i) = (3i + 5) mod 13 to hash the keys 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5, assuming collisions are handled by: i) Separate chaining; [1 mark] ii) Linear probing; [1 mark] iii) Quadratic probing till the method fails; [1 mark] iv) Using the secondary hash function h0(i) = 11- (i mod 11). [2 marks] [5 marks] 4. Consider the recurrence T(n) = 3T(⌊n/2⌋) + n. i) Use the master method to give tight asymptotic bound for this recurrence (if the master method cannot be used, explain why). [1 mark] ii) Use a recursion tree to determine a good asymptotic upper bound on this recurrence. [2 marks] iii) Use the substitution method to verify your answer. [1 mark] [4 marks]
5. Show all the steps for performing any of the following algorithms for matching the pattern `belabela' in the text `bellisalabelabelbelabela'. (a) brute-force [1 mark] (b) Boyer-Moore [2 mark] (c) Knuth-Morris-Pratt [2 mark] [5 marks]