CSE 326, Winter 1999: Homework 5

Due 2/19/99

For all program or data structure design problems such as the two below you must provide pseudocode (see the manual)and an adequate explanation of the methods. It is often helpful to include small examples demonstrating the methods. Staight pseudocode with no additional documentation is not enough.

1. (10 points) In this problem you will design an algorithm to do a rectangular range query in a two-dimensional k-d tree. A query is specified by two points (x₁,y₁) and (x₂,y₂) which indicate two opposite corners of the rectangle. Your function should simply print all the points that are inside or on the boundary of the rectangle. For simpliclity you can assume that the coordinates of all the points in the input are non-negative integers less than some maximum specified integer.
2. (10 points) In this problem you will design algorithms to handle lazy deletion for closed hashing using linear probing. Assume we have an on going process of insertions, deletions, and finds. Design four algorithms where each algorithm is briefly described in pseudocode. Assume the keys are non-negative integers which are hashed into a table T of size HSize. An empty table entry can be indicated using -2. Use -1 in a location to indicate that the entry formerly in the location has been deleted. Your hash table algorithms do not have to resize the hash table.
   • Find(x,T) which returns the index of where x is stored if it is in the table T and -1 otherwise.
   • Insert(x,T)which inserts x into the table T with the precondition that x is not currently in the table. Naturally, a location with a -1 in it can be used to place a newly inserted item. Your algorithm should indicate when the hash table T is full and x cannot be inserted.
   • Delete(x,T) which removes x from the table T using lazy deletion.
   • Rehash(T) which returns a new table of the same size HSize which contains all the items of the old table, but has no items marked as deleted.