CSE 326 – Data Structures – Winter 2002

Homework #4 – Trees and Hash Tables

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

 

Goals of this assignment:

 

 

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.