CSE 326 – Data Structures – Winter 2002

Homework #4 – Trees and Hash Tables

Due Friday, February 8^th, 2002
Hand in hardcopy in class

Goals of this assignment:

• Understand tree re-balancing schemes
• Work through an application of two different hashing methods
• Prepare for the midterm examination

1. Weiss #4.6. Provide a formal inductive proof, on the number of nodes in the tree.

2. Weiss #4.19. Show the intermediate tree after each operation, or at least after every insertion and rotation pair.

3. Weiss #5.10. Assume a pointer is 4 bytes long, and that the hash table is an array of pointers to words.

4. Weiss #5.11. Assume that a bool takes up only 1 bit, and that the table of bools is packed as densely as possible (8 bools to the byte). Fun fact: this is how the “spell” command on Unix is implemented!

5. Weiss #5.4. Provide (a) the answer, and (b) an English justification for your answer. For extra credit provide (c) a formal proof (amortized analysis upper bound) for you answer.

To prepare for the midterm, you should also:

* Review the previous homework assignments carefully – be sure you understand the correct solutions to all questions.

* Be prepared to discuss the tradeoffs (advantages and disadvantages) of all of the different hashing methods discussed in class.

* Be prepared to write short, pseudo-code recursive algorithms for operations involving linked data structures.