Implement a HashTable for integers using open hashing to represent sets of integers.

You must implement the hash table yourself and are not allowed to use the C++ standard

template library, i.e., you will need to implement a class for the set. Your set must provide

the basic set operations as discussed in class (add, delete, search, show, quit). Each

element of the set will be stored in a node object, i.e. you will need a separate class that

handles the nodes.

Upon starting your program, it will display the following prompt: set> (followed by a

space):

set>

The user can then add, delete, search, or show the set. If the element is already in the

set and you attempt to add that element to the set, then you need to display an

informational warning message. Similarly, if the element is not already in the set and you

attempt to delete that element from the set, then you need to display an informational

warning message.

Your hash table will have B=7 buckets and your hash function is h(x) = x^2 mod B.

FUNCTION DETAILS:

add will insert a number into the set and is followed by the prompt. If the element is

already in the set, provide an informational message WARNING: duplicate input: #

set> add 7

set> add 7

WARNING: duplicate input: 7

set> add 3

set>

delete will delete an element, if it is in the set. If the element does not exist, provide an

informational message WARNING: target value not found: #

set> delete 3

set> delete 8

WARNING: target value not found: 8

set>

search will return true or false to indicate if the element has been found

set> search 7

true

set> search 4

false

set>

show will list all the elements of the hash table in the following form:

set> show

()-()-()-()-()-()-()

set>

The parenthesis will contain the elements of the individual buckets, separated by

commas. The above example is the empty set

Assume the hash table contains the following elements (order of insertion matters, since

elements are appended at the end of a list for each bucket)

set> add 1

set> add 2

set> add 3

set> add 4

set> add 5

set> add 6

set> add 7

set> show

(7)-(1,6)-(3,4)-()-(2,5)-()-()

set>

quit will exit the program

set> quit

An alternative method for implementing a set S is to imitate the bit string implementation of Delphi by using a boolean array S where S[ch] is true if the element ch is in S and is false otherwise. Using this implementation, write functions for the basic set operations of union, intersection, difference, membership, and equality. The rules for the program are: 1) Declare a boolean array type which will be mapped from 'A' to 'Z'. Note that the subscripts are characters so that we can actually test S[ch] directly M loop from 'A' to '2' directly in the for loop. 2) Create three arrays which will mimic sets: UNIVERSAL, VOWEL and MYNAME. Call a function INIT to initialize these arrays, with UNIVERSAL holding all of the letters, VOWEL contains the letters A, E, I, O and U. Initialize MYNAME to be an empty set, then read a data file which will contain the letters in your name. For ease of input, you can put one letter on each line. 3) Create a print function which will be sent one array. The print will be across a row with a space between elements, as in the following format: ABCDEFGHIJKLMNOPQRSTUWXYZ Call it three times to print the members of UNIVERSAL, VOWEL, and MYNAME, printing an appropriate message each time. 4) Write a function which will find the union of any two sets sent to it. Test the function by having it union VOWEL and MYNAME. Call the print function to print this set with an appropriate message. Problem 1. Let X c S. Define a function fx : S - {0, 1}5 by fx (s ) = 0 if s E X 1 if s EX. Given fx and fy, we can extend the arithmetic of Problem 0 from {0, 1} to such functions by defining for s E S (fx + fy) (s) = fx(s) + fr(s), ( fx . fy) (s) = fx(s) . fy(s), fx(s) = 1+ fx(s), (fx V fy) (s) = fx(s) . fy(s). For example, if S = {a, b, c}, X = {a, b}, and Y = (a, c}, then fx(a) = fx(b) = fy(a) = fy(c) = 1 and fx(c) = fy(b) =0. Then (fx + fy)(a) = (1 + fx(a)) + fy(a) = (1+1) +1=1, ( fx + fy ) (b) = (1 + fx(b)) + fy(b) = (1 + 1) +0=0, and (fx + fy) (c) = (1+ fx(c)) + fy(c) = (1 +0) +1=0. We will show that many basic set operations can be modeled using arithmetic on such "indicator functions." (a) Show that fot fx = fx, that fs . fx = fx, and that fs + fs = fo. (b) Write X = S\\ X. Show that fx = fx