Problem 1
Design and implement ADT SmallSet by treating a single unsigned int word as a bit vector and the positions as members of the universe:
Let N be sizeof(unsigned int). Then any subset of the universal set U = { 0, 1, ... , N-1 } can be represented as a bit vector of size N (which in turn can be stored as an int word.)
Given S U, for any j U, (j S) iff (jth bit (counting 0 as the LSB) of S is 1)
Adding j to S can be implemented as setting jth bit to 1; deleting as setting it to 0.
Obtaining jth bit of an int in C can be achieved by masking the vector with a bit pattern and testing it: i.e.
(S & Bj) iff (jth bit of S is 1) where Bj is all 0s except the jth bit.
Bj can be obtained by left-shifting ((unsigned int) 1) j times.
Implement typical set operations union, intersect, and difference for this SmallSet ADT. You can use the following table for designing your functions.
Key
Function
Input Format
Description
0
readData
0NXY
N represents the size of U (taken as input for convenience). X
A1 A2 A3 .. Ax
and Y represent the sizes of two sets of A & B respectively.
B1 B2 B3 .. By
You shall need to read two sets (A & B) of integers, separated
by a new line. Each set contains values with space separation.
Represent A and B in the form of SmallSet ADT described
above.
1
Union
1
Perform union operation on A and B (C = A ∪ B) and print C.
You may sort C in ascending order first before printing.
2
Intersection
2
Perform intersection operation on A and B (C = A ∩ B) and
print C.
You may sort C in ascending order first before
printing.
3
Difference
3
Perform difference operation on A and B (C = A - B) and print
C.
You may sort C in ascending order first before printing.
Sample input and output
Sample Input
Sample Output
03256
2479101516202124
2415724
15
91615102021
24724
1
2
3
1 | P a g e
