CSE 326, Spring 1997: Homework 7
- (20 points)
Consider the problem of lazy deletion in closed hashing with linear probing.
Assume we have an on going process of insertions, deletions, and finds.
Design five 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 there has been
"Find(x)" which returns the index of where x is stored if it is in the
table and -1 otherwise.
"Insert-new(x)" which inserts x into the table 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.
"Insert(x)" which inserts x into the table with no precondition on whether x is
currently in the table or not.
"Delete(x)" which removes x from the table 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.
- (10 points)
You have been asked to work on the algorithms and data structures for
the worlds best computer Go-Moku program. Go-Moku
is played on a 19 by 19 board.
There are two players, one with white stones and one with black stones.
They alternate play by placing stones on the board. The board is initially
empty. The first player who gets 5 of his or her
stones in a row, horizontally,
vertically, or diagonally, wins.
Design a simple data type for a game position. Remember that a game
position includes where the stones are on the board plus whose turn it
is to play.
Design a function int that maps game positions to integers such
that given a position P, int(P) mod k makes a good hash function
when k is a prime. Provide pseudocode that computes int(P) mod k when
P is represented as your data type and k is a given prime.