CIS-610 Data Structures and Algorithms

Home Work #10							Due:	12/09/1999


1. Write a function search(table, key) that searches a hash table for a record with key key. The function accepts an integer key and a table declared by

Struct record {
	KEYTYPE	k;
	RECTYPE	r;
	int 		flag;
} array[TABLESIZE];

table[j].k and table[j].r are the jth key and record, respectively. table[j].flag equals FALSE if the jth table position is empty and TRUE otherwise. The routine returns an integer in the range 0 to tablesize – 1 if a record with key key is present in the table. If no such record exists, the function returns –1. Assume the existance of a hash function h(key), and a rehashing function rh(index) that both produce integers in the rabge 0 to tablesize – 1.

2. For the graph of figure 8.1.1b:

a. Find its adjacency matrix
b. Find its path matrix using adjacency matrix

3. Draw a digraph to correspond to each of the following relations on the integers from 1 to 12

a. x is related to y if x – y is evenly divisible by 3.
b. x is related to y if x + 10 * y < x * y
c. x is related to y if the remainder on division of x by y is 2.

Compute the adjacency and path matrices for each of relations.

4. A node n1 is reachable from a node n2 in a graph if n1 is equals n2 or there is a path from n2 to n1. Write a routine reach(adj, i, j) that accepts a adjacency matrix and two integers and determines if the jth node in the digraph is reachable from ith node.

5. Rewrite the routine shortpath; presented in the class; to implement the set of “permanent” nodes as linked list.