University of Washington
CSE 326, Data Structures
Homework #3
Due: Wednesday, February 7, 2001, 1:30pm

Winter 2001                                     January 29, 2001
Donald Chinn

Homework is due at the beginning of class on the day specified.
Any homework turned in after the deadline will be considered late.
Late homework policy: You may turn in your homework after the
deadline but before the beginning of the next lecture after it is
due, but at a cost of a 20% penalty.

Please staple all of your pages together (and order them according
to the order of the problems below) and have your name on each page,
just in case the pages get separated.  Write legibly (or type) and
organize your answers in a way that is easy to read.  Neatness counts!
Also, show your work and explain your reasoning.

For each problem, make sure you have acknowledged all persons with
which you worked.  Even though you are encouraged to work together
on problems, the work you turn in is expected to be your own.  When
in doubt, invoke the Gilligan's Island rule (see the course
organization handout). 
* * *
Regular problems (to be turned in) :

1.  Complete Cases 3b and 3c from the handout on how to remove a node
from an AVL tree.  You need not write any code.  Explain (in words
and in diagrams) what the algorithm should do in each case.
2.  Weiss, 5.1.
3.  When you buy a ticket in the State Lottery, you choose six
different numbers between 1 and 49.  The lottery officials keep a
dictionary keyed on the set of six numbers chosen on each ticket.
After the officials pick the winning numbers, they access this
dictionary to identify the winning ticket or tickets, if any.  Since
millions of tickets are sold, the officials have decided to keep the
dictionary in external storage with a directory in an internal hash
table.  (That is, the internal hash table indicates where on disk
to look for items associated with the computed hash value.)  Their
computer consultant, S. L. Ow, has recommended that they use the
hash function
    h(x_1, x_2, x_3, x_4, x_5, x_6) = (x_1 + x_2 + x_3 + x_4 + x_5 + x_6) mod m,
where m is the number of external buckets in which the records will be
stored.  Give a critique of this recommendation.  (Is this a good way
to do this?  Why or why not?)  Suggest a better alternative if you
believe it is not a good idea.
* * *
Suggested problems (highly recommended, but not to be turned in) :
1.  4.27.
2.  4.37.
3.  4.46.
4.  5.8.