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.
  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.