**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*,_{1}*k*) (which returns an enumeration of all the elements in the_{2}*D*with key*k*such that ) on*D*in time , 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 as follows. We choose some initial value*N*for the initial hash table*T*. Then, when the number of elements inserted in_{0}*T*exceeds_{0}*N*, we create a new hash table*T*of size 2_{1}*N*and by rehashing (choose a new universal hash function) move all elements of*T*in to_{0}*T*._{1}*T*can now be discarded. We can then insert new elements in to_{0}*T*till the number of elements exceed 2_{1}*N*. In general, we create a table*T*_{k}of size 2^{k}*N*as soon as table*T*_{k-1}contains 2^{k-1}*N*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 students be distributed samosas
and the next students be given gulab jamuns. However, he
has stipulated that we cannot sort the student roll list according
to marks (which would take time) but should use our
data structures skills to determine who gets what in
*O*(*n*) time.