Homework 2

Search Trees and Hash Tables

Due: Friday, Oct 31, beginning of class

This assignment is designed to give you practice with various implementations of the search and dictionary ADTs we have seen. Given the timing of this assignment and the upcoming midterm, it may not give you enough practice with the underlying concepts. You are encouraged to work on some more problems from the textbook on your own and verify your solutions with the course staff.

Note: Please review the collaboration policy on the course web page. You must mention the names of fellow students who you worked with on this assignment.

Total: 80 points. 20 points for each problem.

  1. [Search Trees] Show the result of inserting 10, 15, 12, 3, 1, 13, 4, 17 and 8 into the following initially empty search tree data structures. It's fine to turn in only the final result. However, if your final answer in incorrect, intermediate steps may allow partial credit.
    1. Binary search tree (unbalanced)
    2. AVL tree
    3. Splay tree
    4. B-tree with M=3, L=2
    5. B-tree with M=3, L=3

  2. [Hash Tables] Do the same as you did in the above problem, but now for the following hash table implementations. Indicate if and when no more keys can be inserted into the table.
    1. Hash table of size 11 with separate chaining
    2. Hash table of size 11 with open addressing and linear probing
    3. Hash table of size 11 with open addressing and quadratic probing
    4. Hash table of size 11 with open addressing and double hashing, where hash2(x) = 5 - (x mod 5)
    5. Hash table of size 11 with open addressing, quadratic probing and rehashing when the table is half full

  3. [Range Search] Give an algorithm (pseudocode) that takes a binary search tree as input along with two keys x and y, with x less than or equal to y, and prints out all keys z in the tree that lie between (and including) x and y.
    1. What is the worst-case running time of your algorithm? Give a bound in terms of the tree size N, the tree depth D, and the number M of keys output.
    2. What would be the worst-case running time if instead of a binary search tree, you were given a hash table with tableSize S and N elements?

  4. [Open Addressing] Problem 5.6, page 178.