Question 1:
Consider the sequence of keys 1205, 3248, 1330, 1844, 2042, 2861, 1475, 3582, 2492, 4125 and 2503 are inserted into an empty hash table. The hash function is h(x) = x mod 11. For each of the following four scenarios, per the specified operations:
a) When collisions are handled by separate chaining.
(i) Draw the hash table after all the keys have been inserted.
(ii) Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.
(iii) Find the largest number of key comparison in a successful search in the hash table.
(iv) What is the load factor of the hash table?
b) When collisions are handled by linear probing.
(i) Draw the hash table after all the keys have been inserted.
(ii) Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.
(iii) Find the largest number of key comparison in a successful search in the hash table.
(iv) What is the load factor of the hash table?
c) When collisions are handled by quadratic probing using a quadratic probe function f'(x, i) = (h(x) + 1.5i +1.5i2) mod 11, where i = 1, 2, 3, ... and h(x) = x mod 11.
(i) Draw the hash table after all the keys have been inserted.
(ii) Find the aver-age number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.
(iii) Find the largest number of key comparison in a successful search in the hash table.
(iv) What is the load factor of the hash table?
d) When collisions are handled by double hashing using a double hash function h'(x, i) = (h(x) + i x ((2x - 1) mod 7) + 1) mod 11, where i = 0, 1, 2, 3, .... and h(x) = x mod 11.
(i) Draw the hash table after all the keys have been inserted.
(ii) Find the average number of key comparisons in a successful search in the hash table. You can assume that a search for each of the nine keys is equally likely.
(iii) Find the largest number of key comparison in a successful search in the hash table.
(iv) What is the load factor of the hash table?
Question 2
a) The operation convertToMaxHeap(h) converts a minimum heap into a maximum heap. Design an algorithm of convertToMaxHeap that runs in O(n lgn) time. Show that your algorithm runs in o(n lg n).
b) Given the following minimum heap, illustrate the process of converting it into a maximum heap using your algorithm described in (a). You need to show the intermediate processes. Please show every steps you made clearly.
Question 3
The INORDER traversal output of a binary tree is U, N, I, V, E, R, 5, I, T, Y and the POSTORDER traversal output of the same tree is I, N, U, E, R, It Y, T, 5, V. Construct the tree and determine the output of the PREORDER traversal output.
Question 4
a) One main difference between a binary search tree (BST) and an AVL (Adelson-Velski and Landis) tree is that an AVL tree has a balance condition, that is, for every node in the AVL tree, the height of the left and right subtrees differ by at most 1. Starting with an empty BST and AVL tree, insert elements into the two trees with the following keys:
0) 7, 11, 12, 18, 21
(ii) 20, 30, 80, 40, 10, 60, 50, 70
b) Comment on the worst-case running time complexity of the two trees structure.
c) A list of student's names is maintained in an AVL tree T. Design an algorithm for performing the operation findAll to return all the names in the AVL tree that match the searched name. Note that there is a posibility that same names exist in the tree. In the case that the same name exists, the name is added to the left subtree.
d) What is asymptotic running time complexity of your algorithm from part c?
Question 5:
a) Starting with an empty 2-4 tree, construct a 2-4 tree with the following keys. Show the major working steps.
5, 16, 22, 45, 2, 10, 18, 30, 50, 12, 1
b) What is the running time complexity to process a 2-4 tree with n keys? Show or explain.