This program should be written in c++ and should work on a linux server: meaning no conio.h. Thank you

The main objective of this programming assignment is to build a set class using three different data structures, and analyze their performance. You will implement set classes using linked lists, vectors, and hash tables. You may use your linked list and vector implementations made for the review assignment. Your set implementations must be able to perform the following operations:

Create an empty set and add items to it. Uniqueness of items within the set must be maintained

Deletion of an item from the set. This deletion must not lose any data other than the given element to be deleted.

Print out the elements currently contained within the set. They will be printed out as {element1, element2, }

Union between sets, as defined in class

Intersection of sets, as defined in class

Difference of sets, as defined in class

In this archive there are 4 small data files int1, int2, int3, int4. Each one represents a set. Your program will load the data from each list into individual sets and be able to evaluate the following three set equations (Note S1 refers to the set found in int1, S2 to int2, ). We may test your program using different (but similarly sized) data sets, so your program should be able to handle files specified by the user as opposed to hard coding the file names in. Your program must print out each equation, and then display the result. Display of the work during intermediary steps is not necessary for the final submission, but it may be helpful for debugging purposes during coding. You will NOT be counted off if the work is left in the final submission. Example output: EQ1: S1 (S2 - S3) = {1,2,3,4,5,6,7,8,9,10}

((S1 S4) S3) S2

(S1 S2) ((S3 S2) (S4 S1))

S4 S3 S2 S1

(S3 ((S1 S3) (S2 S4)

A basic hash table implementation will be provided, bonus points will be given if you create your own implementation. Each implementation and the resulting analysis is worth 1/3 of the assignment grade. Due to the small size for most of the datasets, we will do this analysis by counting the loop iterations our various set operations go through as opposed to a time metric. As an example, the loop in the pseudocode below will execute the inner loop between 1 to m times, where n is the size of the array, and the outer loop 1 to n times, giving it a big-O of O(m*n).

for(int i = 0; i < set.size(); i++)

for(int j = 0; j < array.size(); j++)

if(set[i] == array[j])

break

Total points: 130

Set implementation: 40 points each

Creation of set 5 points

Union operation 5 points

Intersection operation 5 points

Difference operation 5 points

Equations being correctly evaluated 10 points

Performance analysis 5 points

Pseudocode submission (Due 9/20at 11:59pm) 5 points

10 points for clean code.

Clear variable names

Descriptive comments (when necessary)

Proper output formatting

Below are the 4 data files .txt

int1.txt

1 2 3 4 5 6 7 8 9 10

int2.txt

1 3 5 7 9 11 13 17 19 21

int3.txt

10 10 10 10 10 10 10 10 12 14 13 1 2 3 4 7

int4.txt

1 2 18 16 15 12 11 6 8 2

Hash Table sample code

// Ryan Michaels // Modified Hash Table/Hash Map Code // Updated 9/13/2017 // Original code used with permission // May be used or expanded for assignments in CSCE 2110 Fall 2017 #include #include #include #include using namespace std; const int TABLE_SIZE = 29; class HashEntry { private: int value; public: HashEntry(int value) { this->value = value; } int GetValue() { return value; } }; class HashMap { private: HashEntry **table; public: HashMap() { table = new HashEntry*[TABLE_SIZE]; for (int i = 0; i< TABLE_SIZE; i++) { table[i] = NULL; } } // Generates the hash for this table int HashFunc(int value) { return value % TABLE_SIZE; } // Inserts the specified value into the table at the first empty location void Insert(int value) { int hash = HashFunc(value); while (table[hash] != NULL && table[hash]->GetValue() != value) { hash = HashFunc(hash + 1); } if (table[hash] != NULL) delete table[hash]; table[hash] = new HashEntry(value); } // Searchs the table for a given value // Returns the index at which the value is found // Or returns -1 if it is not found int Search(int value) { int hash = HashFunc(value); while (table[hash] != NULL && table[hash]->GetValue() != value) { hash = HashFunc(hash + 1); } if (table[hash] == NULL) return -1; else return hash; } // Removes a specified value from the table, if the value is found void Remove(int value) { int hash = HashFunc(value); while (table[hash] != NULL) { if (table[hash]->GetValue() == value) break; hash = HashFunc(hash + 1); } if (table[hash] == NULL) { cout<<"No Element found at value "<GetValue() << " "; } } ~HashMap() { for (int i = 0; i < TABLE_SIZE; i++) { if (table[i] != NULL) delete table[i]; delete[] table; } } }; int main() { HashMap hash; int value; int temp_key; int choice; while (1) { cout<<" ---------------------- "; cout<<"Operations on Hash Table "; cout<<"---------------------- "; cout<<"1.Insert element into the table "; cout<<"2.Search element from the value "; cout<<"3.Delete element at a value "; cout<<"4.Print elements in hash. "; cout<<"5.Insert sample data. "; cout<<"6.Exit "; cout<<"Enter your choice: "; cin>>choice; switch(choice) { case 1: cout<<"Enter element to be inserted: "; cin>>value; temp_key = hash.HashFunc(value); cout<<"The key at which element will be inserted is: " << temp_key << " "; hash.Insert(value); break; case 2: cout<<"Enter value of the element to be searched: "; cin>>value; if (hash.Search(value) == -1) { cout<<"No element found at value "<>value; hash.Remove(value); break; case 4: cout << "The current table is: "; hash.print(); break; case 5: cout << "Sample load "; cout << "We will load 15 values into the hash table and then display it. "; for (int i = 1; i < 16; i++) hash.Insert(i * i); hash.print(); break; case 6: exit(1); default: cout<<" Enter correct option "; } } return 0; }