Exercises

1. Implement a library of functions to implement sparse arrays as hash tables. Make sure that you address the issue of finding a hash function that works well for arrays of different sizes.
2. Devise an efficient algorithm that finds the intersection of two binary search trees (i.e. the list of keys that appear in both trees) and prints it in order. The algorithm must visit each node in both trees at most once.
3. Using the algorithm from the previous exercise, implement the fast matrix multiplication algorithm for sparse arrays described at the end of chapter 3, modified to work with sparse arrays represented by binary trees.
4. Devise an efficient algorithm that finds the union of two binary search trees (i.e. the list of keys that appear in either trees) and prints it in order.