#include

#include //srand, rand

#include //clock_t, clock, CLOCKS_PER_SEC

using namespace std;

// implementing hash tables as an array of linked lists

class Node{

private:

int data;

Node* nextNodePtr;

public:

Node(){}

void setData(int d){

data = d;

}

int getData(){

return data;

}

void setNextNodePtr(Node* nodePtr){

nextNodePtr = nodePtr;

}

Node* getNextNodePtr(){

return nextNodePtr;

}

};

class List{

private:

Node *headPtr;

public:

List(){

headPtr = new Node();

headPtr->setNextNodePtr(0);

}

Node* getHeadPtr(){

return headPtr;

}

bool isEmpty(){

if (headPtr->getNextNodePtr() == 0)

return true;

return false;

}

void insert(int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

while (currentNodePtr != 0){

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(0);

prevNodePtr->setNextNodePtr(newNodePtr);

}

void insertAtIndex(int insertIndex, int data){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == insertIndex)

break;

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

Node* newNodePtr = new Node();

newNodePtr->setData(data);

newNodePtr->setNextNodePtr(currentNodePtr);

prevNodePtr->setNextNodePtr(newNodePtr);

}

int read(int readIndex){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

int index = 0;

while (currentNodePtr != 0){

if (index == readIndex)

return currentNodePtr->getData();

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

index++;

}

return -1; // an invalid value indicating

// index is out of range

}

bool deleteElement(int deleteData){

Node* currentNodePtr = headPtr->getNextNodePtr();

Node* prevNodePtr = headPtr;

Node* nextNodePtr = headPtr;

while (currentNodePtr != 0){

if (currentNodePtr->getData() == deleteData){

nextNodePtr = currentNodePtr->getNextNodePtr();

prevNodePtr->setNextNodePtr(nextNodePtr);

return true;

}

prevNodePtr = currentNodePtr;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return false;

}

int countList(){

Node* currentNodePtr = headPtr->getNextNodePtr();

int numElements = 0;

while (currentNodePtr != 0){

numElements++;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return numElements;

}

void IterativePrint(){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

cout getData()

currentNodePtr = currentNodePtr->getNextNodePtr();

}

cout

}

bool containsElement(int searchData){

Node* currentNodePtr = headPtr->getNextNodePtr();

while (currentNodePtr != 0){

if (currentNodePtr->getData() == searchData)

return true;

currentNodePtr = currentNodePtr->getNextNodePtr();

}

return false;

}

};

class Hashtable{

private:

List* listArray;

int tableSize;

public:

Hashtable(int size){

tableSize = size;

listArray = new List[size];

}

int getTableSize(){

return tableSize;

}

void insert(int data){

int hashIndex = data % tableSize;

listArray[hashIndex].insert(data);

}

void deleteElement(int data){

int hashIndex = data % tableSize;

while (listArray[hashIndex].deleteElement(data));

}

bool hasElement(int data){

int hashIndex = data % tableSize;

return listArray[hashIndex].containsElement(data);

}

void printHashTable(){

for (int hashIndex = 0; hashIndex

cout

listArray[hashIndex].IterativePrint();

}

}

double FindAvgNumComparisonsSuccessfulSearch(){

// Implement the function to determine and return the

// average number of comparisons for a successful search

}

double ComputeLoadImbalanceIndex(){

// Implement the function to determine and return the load imbalance index

}

};

int main(){

int numElements = 100000;

//the number of elements you want to store in the hash table

int maxValue = 50000;

//the maximum value for an element

int numTrials = 25;

//the number of trials

int numTableSizeValues = 20;

int* hashTableSize = new int[numTableSizeValues];

hashTableSize[0] = 11;

hashTableSize[1] = 29;

hashTableSize[2] = 47;

hashTableSize[3] = 71;

hashTableSize[4] = 173;

hashTableSize[5] = 281;

hashTableSize[6] = 409;

hashTableSize[7] = 541;

hashTableSize[8] = 659;

hashTableSize[9] = 809;

hashTableSize[10] = 941;

hashTableSize[11] = 1069;

hashTableSize[12] = 1223;

hashTableSize[13] = 1373;

hashTableSize[14] = 1511;

hashTableSize[15] = 1657;

hashTableSize[16] = 1811;

hashTableSize[17] = 1987;

hashTableSize[18] = 2129;

hashTableSize[19] = 2287;

srand(time(NULL));

for (int tableSizeIndex = 0; tableSizeIndex

double totalAvgNumComparisons = 0;

double totalLoadImbalanceIndex = 0;

for (int trials = 1; trials

Hashtable hashTable(hashTableSize[tableSizeIndex]);

int *array = new int[numElements];

for (int index = 0; index

array[index] = rand() % maxValue;

hashTable.insert(array[index]);

}

totalAvgNumComparisons += hashTable.FindAvgNumComparisonsSuccessfulSearch();

totalLoadImbalanceIndex += hashTable.ComputeLoadImbalanceIndex();

}

cout

}// table size loop

system("pause");

return 0;

}

Q2 - 30 pts) For this question, you will explore the tradeoff between the average number of comparisons for a successful search of an element in a hash table vs. the load imbalance index. It is logical to expect that as the hash table size (the size of the array of linked lists representing the hash table) grows, the length of each of the linked lists reduces: as a result, the number of comparisons that would be needed to search for any element is likely to reduce. On the other hand, as we fix the number of elements to store in a hash table, the load imbalance index (the ratio of the sum of the maximum and minimum lengths of the linked lists and the difference between the maximum and minimum lengths of the linked lists; see the slides for the formulation and details) is expected to increase with increase in the hash table size. Thus, for a fixed number of elements to store in a hash table, as we increase the hash table size, the average number of comparisons for a successful search is expected to decrease and the load imbalance index is expected to increase. As part of your you will explore/quantify the above tradeoff. You are given the code featuring the implementation of a hash table as an array of singly linked lists. The main function is already coded to create an array of size 100,000 with the maximum value per element being 50,000. You will try 20 different values for the hash table size ranging from 11 to 2,287 as given in the code (note the array of hash table size is already created for you in the main function). For each hash table size, you will run 25 trials. You are required to implement the functions FindAvgNumComparisonsSuccessfulSearch() and ComputeLoadImbalanceIndex( ) in the Hashtable class. The time complexity of each of these functions should be (n) where n is the number of elements in the array. The main function is coded in such a way that these two functions are called for each of the trials for a certain hash table size and the average of the average number of comparisons for a successful search and the average load imbalance index are computed and printed for each value of the hash table size. Take a screenshot of the output displaying the average number of comparisons for a successful search and the load imbalance index for different values of the hash table size. Plot two Excel charts (X-Y plots) that features the values for the hash table size in X-axis and the values for the average number of comparisons for a successful search and the average load imbalance index in the Y-axes. Use the trend line option in Excel for each of these plots and determine a power function- based relation between the metric on the Y-axis and the hash table size in the X-axis. Display the power function-relation as well as the Rvalue for the fit in the Excel plots