Data Structures (CS130N) Minor II March 20, 2001

Name:                                 Entry:                 Grp:   

Note: Maximum marks : 60 (a mark a minute). All questions carry equal marks. Answer only in the space provided. 2 pages in all.

1.

Describe an algorithm to find the inorder successor of a given node x in an AVL tree.

2.

Let D be an ordered dictionary with n items implemented by means of an AVL tree. Show how to implement the operation findAllInRange(k₁,k₂) (which returns an enumeration of all the elements in the D with key k such that $k_1 \leq k \leq k_2$) on D in time $O(\log{n} + s)$, where s is the size of the enumeration returned.

3.

Suppose that the number of elements n to be inserted in a hash table (assume chaining and universal hashing) is not known in advance. We can then construct a sequence of hash tables $T_0, T_1, T_2,\ldots$ as follows. We choose some initial value N for the initial hash table T₀. Then, when the number of elements inserted in T₀ exceeds N, we create a new hash table T₁ of size 2N and by rehashing (choose a new universal hash function) move all elements of T₀ in to T₁. T₀ can now be discarded. We can then insert new elements in to T₁ till the number of elements exceed 2N. In general, we create a table T_k of size 2^k N as soon as table T_k-1 contains 2^k-1N elements. Derive the expected time for insertion of n elements using the above procedure.

4.

Dean Prasad wants to keep the motivation levels of students of CS130N high by giving incentives. He has suggested that after the second minor the top $\log{n}$ students be distributed samosas and the next $\sqrt{n}$ students be given gulab jamuns. However, he has stipulated that we cannot sort the student roll list according to marks (which would take $O(n \log{n})$ time) but should use our data structures skills to determine who gets what in O(n) time.