CSE 326, Spring 1997: Homework 7

Due 5/21/97

1. (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 deleted.
   • "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.
2. (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.