In this programming assignment, you will design and implement a O(n) algorithm to use a hash table to determine the most frequently occurring integer in an array of 'n' integers as well as print the associated largest frequency. You are given a singly Linked List-based implementation of a Hash table. You could augment this code to do the assignment. The main function is setup to generate an array of random integers (of size numElements) in the range [1...maxValue]; the hash function is given by K mod hashTableSize where K is an integer data in the array. Submission (in Canvas): Submit Items 1 and 3 together as a PDF file and submit item 2 as a .cpp file 1) Explain of your algorithm and justify that its time complexity is (n) for an array of 'n' integers. 2) The complete C++ code, including the augmentation/changes you made to the assigned code. 3) A screenshot of the output obtained by running the code for numElements = 50; maxValue = 15 and hashTableSize = 7. #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->getNext NodePtr() == 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(); prevNodePtr ->setNextNodePtr(newNodeptr); void IterativePrint() { Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout getData() getNextNodePtr(); cout getNext NodePtr(); 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); bool hasElement(int data) { int hashIndex = data % tableSize; return listArray[hashIndex] .containsElement(data); void printHashTable() { for (int hashIndex = 0; hashIndex > numElements; int maxValue; cout > maxValue; int hashTableSize; cout > hashTableSize; Hashtable hashTable(hashTableSize); srand(time(NULL)); int array[numElements]; cout #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->getNext NodePtr() == 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(); prevNodePtr ->setNextNodePtr(newNodeptr); void IterativePrint() { Node* currentNodePtr = headPtr->getNextNodePtr(); while (currentNodePtr != 0){ cout getData() getNextNodePtr(); cout getNext NodePtr(); 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); bool hasElement(int data) { int hashIndex = data % tableSize; return listArray[hashIndex] .containsElement(data); void printHashTable() { for (int hashIndex = 0; hashIndex > numElements; int maxValue; cout > maxValue; int hashTableSize; cout > hashTableSize; Hashtable hashTable(hashTableSize); srand(time(NULL)); int array[numElements]; cout