CSE326 Winter 2006
 CSE Home 326 Home About Us Search Contact Info

 Projects Project 1 Project 2 - phase A Project 2 - phase B Project 3 Homework Homework 1 Homework 2 Homework 3 Administrative Home Message Board Annoucement Archive Class List Archive Anonymous Feedback Mail Instructor & TAs Lectures Calendar & Slides Handouts First Day Handout Policies General Guidelines Grading Policies Programming Guidelines Writeup Guidelines Computing Unix Basics

# 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.

1. [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.
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] (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.
1. Hash table of size 11 with separate chaining where each bucket is an unsorted linked list
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] (20 points)
1. 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.
2. 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.
3. 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.
4. What would be the worst-case running time of your algorithm given in part c.  Give a bound in terms of `tableSize`` `and `N`.
4. [Open Addressing] (12 points) Problem 5.6, page 178.

 Computer Science & Engineering University of Washington Box 352350 Seattle, WA  98195-2350 (206) 543-1695 voice, (206) 543-2969 FAX [comments to cary]