1. Use a recursion tree to determine a good asymptotic upper bound on the recurrence T (n) = T (n/2) + T (n - 1) + cn.
2. Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10, 30 into a hash table with collisions resolved by chaining. Let the table have 10 slots and let the hash function be h(k) = k mod 10.
3. Consider inserting the keys 5, 28, 19, 15, 20, 33, 12, 17, 10, 30 into a hash table of length m = 10 with the auxiliary hash function h(k) = k mod 10. Illustrate the result of inserting they keys using linear probing.
4. Suppose two keys are inserted into an empty hash table with m slots. Assuming simple uniform hashing, what is the probability of a collision?
5. Suppose three keys are inserted into an empty hash table with m slots. Assuming simple uniform hashing, what is the probability of no collisions? One collision? Two collisions?
6. Suppose n keys are inserted into an empty hash table with m slots. Assuming simple uniform hashing, what is the probability of no collisions? One or more collisions?
7. Demonstrate what happens when we insert the keys 5, 28, 19, 15, 20, 33, 12, 17, 10, 30 into a binary search tree.
8. For the binary search tree in the previous exercise, demonstrate what happens when 5, 28, 19 are deleted from the tree.
9. Suppose we have an array A that is already sorted. Using the book's pseu-docode conventions, write a recursive procedure Sorted-Array-To-Tree(A, p, r) that returns a balanced binary search tree. Assume that Sorted-Array-To-Tree(A, 1, A.length) is the initial call. What is the running time of your procedure?
10. For the book's Tree-Insert procedure, write a comment between each pair of lines describing what is true when the program reaches that point in the code.