This program should be written in c++ and should work on a linux server: meaning

Question

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

Explanation / Answer

#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; iGetValue() != 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

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.