|
|
|
|
|
Homework 2
Search Trees and Hash Tables
Due: Wednesday, Feb 22, beginning of class
This assignment is designed to give you practice with
various implementations of the search and dictionary ADTs
we have seen.
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: 72 points.
- [Search Trees] (20
points) 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.
- Binary search tree
(unbalanced)
- AVL tree
- Splay tree
- B-tree with M=3, L=2
- B-tree with M=3, L=3
- [Hash Tables] (20
points) 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. Use h(x) = x mod tableSize.
- Hash table of size 11
with separate chaining where each bucket is an unsorted linked list
- Hash table of size 11
with open addressing and linear probing
- Hash table of size 11
with open addressing and quadratic probing
- Hash table of size 11
with open addressing and double hashing, where
hash2(x) = 5 - (x mod 5)
- Hash table of size 11
with open addressing, quadratic probing and rehashing when the table is
half full
- [Range Search] (20
points)
- 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 x and y inclusive.
- What is the worst-case
running time of your algorithm given in part a? Give a bound in terms of
the tree size
N, the
tree height H, and the
number M of keys
output.
- Give an algorithm (pseudocode) that instead of a binary search tree, uses a hash table of size
tableSize with separate chaining and N elements where each bucket is an
unsorted linked list.
- What would be the
worst-case running time of your algorithm given in part c. Give a
bound in terms of
tableSize and N.
- [Open Addressing] (12
points) Problem 5.6, page 178.
|
CSE Home 
