Description
EL9343 Homework 7
1. Suppose that we wish to implement a dynamic, open-address hash table. Why might we consider the table
to be full when its load factor reaches some value 𝞪 that is strictly less than 1?
Describe briefly how to
make insertion into a dynamic, open-address hash table run in such a way that the expected value of the
amortized cost per insertion is O(1).
Why is the expected value of the actual cost per insertion not
necessarily O(1) for all insertions? (Exercise 17.4-1 in CLRS Textbook, page 471)
2. Write pseudocode for RIGHT-ROTATE. (Exercise 13.2-1 in CLRS Textbook, page 313)
3. Demonstrate what happens when we insert the keys [5, 28, 19, 15, 20, 33, 12, 17, 10] into a hash table
with collisions resolved by chaining.
Let the table have 9 slots and let the hash function be h(k) = k mod 9.
0
1
2
3
4
5
6
7
8
4. Building an AVL Tree out of the Binary Search Tree according to the rotation operations in the lecture.
(You can simply give the final result.)
5
/ \
3 8
/ \
7 9
/ \
6 10
