Computer Representation of Sets Quiz and Flashcards

Study Notes

Computer Representation of Sets

There are various ways to represent sets using a computer, and one method is to store elements in an unordered fashion.
However, this method is inefficient for computing the union, intersection, or difference of two sets, as it requires a large amount of searching for elements.
A more efficient method is to store elements using an arbitrary ordering of the elements of the universal set.

Bit String Representation

Represent a subset A of U with a bit string of length n, where the i-th bit in the string is 1 if aj belongs to A and 0 if aj does not belong to A.
Example: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order.
The bit string for the set of odd integers in U is 1 0 1 0 1 0 1 0 1 0.
The bit string for the set of all even integers in U is 0 1 0 1 0 1 0 1 0 1.
The bit string for the set of all integers in U that do not exceed 5 is 1 1 1 1 1 0 0 0 0 0.

Operations on Bit Strings

To obtain the bit string for the union and intersection of two sets, perform bitwise Boolean operations on the bit strings.
Union: OR operation
Intersection: AND operation
Example: Find the bit string for the union and intersection of two sets A1 = {1, 3, 5, 7, 9} and A2 = {1, 2, 3, 4, 5}.
A1 ∪ A2 = 1 1 1 1 1 0 1 0 1 0
A1 ∩ A2 = 1 0 1 0 1 0 0 0 0 0

Multisets

Multisets are unordered collections of elements where an element can occur as a member more than once.
The notation {m1.a1, m2.a2, ..., mr.ar} denotes the multiset with element a1 occurring m1 times, element a2 occurring m2 times, and so on.
The union of the multisets P and Q is the multiset where the multiplicity of an element is the maximum of its multiplicities in P and Q.
The intersection of P and Q is the multiset where the multiplicity of an element is the minimum of its multiplicities in P and Q.
The difference of P and Q is the multiset where the multiplicity of an element is the multiplicity of the element in P less its multiplicity in Q unless this difference is negative, in which case the multiplicity is 0.
The sum of P and Q is the multiset where the multiplicity of an element is the sum of multiplicities in P and Q.

Operations on Multisets

The union, intersection, and difference of P and Q are denoted by P U Q, P ∩ Q, and P - Q, respectively.
The sum of P and Q is denoted by P + Q.
Example: Let A = {3.a, 2.b, 1.c} and B = {2.a, 3.b, 4.d}, find A ∪ B, A ∩ B, A + B, A - B, B - A.
A ∪ B = {3.a, 3.b, 1.c, 4.d}
A ∩ B = {2.a, 2.b}
A + B = {5.a, 5.b, 1.c, 4.d}
A - B = {1.a, 1.c}
B - A = {1.b, 4.d}

Description

Explore various methods of representing sets using a computer, including storing elements in an arbitrary ordering to optimize operations like union, intersection, and difference. Learn how different storage methods can impact the efficiency of set operations.