For this problem, you must implement the openHashTableAdd function and openHashTableContains for an open address hash table with linear probing. Assume you have access to a hash function named _HASH that returns an arbitrary integer value (not necessarily between [0, tablesize-1]!)

/* NOTE the definition of TOMBSTONE here */

#define TOMBSTONE -1

int _HASH ( TYPE newValue);

struct openHashTable {

TYPE ** table; /* array of pointers to TYPE */

int tablesize;

int count;

};

/* Initialize the open addressing hash table. Note the table entries are initialized to NULL pointers to indicate they are empty */

void initOpenHashTable (struct openHashTable * ht, int size) {

int i;

assert (size > 0);

ht->table = (TYPE **) malloc(size * sizeof(TYPE *));

assert(ht->table != 0);

ht->table[0] = 0;

for (i = 0; i < size; i++)

ht->table[i] = 0; /* initialize empty */

ht->tablesize = size;

ht->count = 0;

}

int openHashTableSize (struct openHashTable *ht) { return ht->count; }

/* Double the size of an open addressing hash table */

void _resizeOpenHashTable (struct openHashTable *ht) {

int oldTableSize = ht->tableSize;

if (ht->tableSize == 0)

ht->tableSize = 1;

ht->tableSize = 2* ht->tableSize;

TYPE **oldArray = ht->table;

/* Create a new array */

ht->table = (TYPE **)malloc(ht->tableSize * sizeof(TYPE *));

assert(ht->table != 0);

/* Rehash elements into new array */

for(i=0; i < oldTableSize i++) {

if(oldArray[i] != 0 && oldArray[i] != TOMBSTONE)

openHashTableAdd(ht, oldArray[i]);

}

free(oldArray);

}

void openHashTableDelete(struct openHashTable * ht, TYPE newValue) {

int loc = openHashTableContains(ht, newValue);

if (loc >= 0) {

/* NOTE: delete will free memory for the item. This assumes that this program owns the memory for this hash table item */

free(ht[loc]); ht[loc] = TOMBSTONE;

ht->count--;

}

}

void openHashTableAdd (struct openHashTable * ht, TYPE newValue) {

/* TODO: Implement this function, remember to consider TOMBSTONES which should not stop the search but can be replaced with a new item. Note that no two identical values should be added to the hash table. Assume that you can use val == newValue or val != newValue to compare between a variable val and the newValue */

}

/* returns the location of the item in the hash table, -1 if it is not present */

int openHashTableContains (struct openHashTable *ht, TYPE testValue) {

/* TODO: Implement this function, remember to consider TOMBSTONES which should not stop the search. Assume that you can use val == testValue or val != testValue to compare between a variable val and the testValue */

}

Problem #3: Fill in the following code for a breadth-first search (BFS) algorithm that returns reachability of every node in an unweighted directed graph from a particular node startVertex, assume that the adjacency list representation of a graph is given as a parameter to your function (12 points). #include

#include

struct Edge {

int vertex;

struct Edge * next; /* You can assume next = 0 at the end of the list */

};

bool * BreadthFirstReachability(

struct Edge * adjacencyList[],

int num_vertices,

int startVertex

)

{

/* adjacencyList is a given edge-list representation of a graph;

num_vertices is the number of vertices in the graph; startVertex gives the vertex to start from. */

/* Assume all vertex indices will be integers from 0 to num_vertices 1, hence adjacencyList[vertexA] will contain all the edges originating from vertexA */

/* calloc will allocate and zero the array (set all values to false)*/

bool *reachable = calloc(num_vertices * sizeof(bool));

assert (reachable != 0);

reachable[startVertex] = true;

/* TODO: Implement the rest of the BFS reachability function here (you are allowed to define additional variables below the given code). */

return reachable;

}