B4.1.5 Construct and apply sets as an ADT. (HL only)

The big idea

A set is an Abstract Data Type (ADT) that represents a collection of unique, unordered elements.
Unlike lists or arrays:

• Elements cannot be duplicated.
• There is no defined order for elements.
• Sets are best for membership tests and mathematical set operations.

In Python, sets are built-in and implemented using a hash table under the hood, giving average O(1) time complexity for membership checks, additions, and removals.

 

1. Fundamental characteristics of sets

1. Unordered nature

   • The order in which elements are stored or retrieved is arbitrary.

   s = {3, 1, 4}
   print(s)  # {1, 3, 4} (order is not guaranteed)
   

2. Uniqueness of elements

   • Any duplicate added to a set is ignored.

   s = {1, 2, 2, 3}
   print(s)  # {1, 2, 3}
   

3. Mutability of the set, immutability of elements
   • You can add or remove elements from a set, but each element must be immutable (e.g., numbers, strings, tuples).

 

2. Core set operations

a) Union

Combines all unique elements from two sets.

A = {1, 2, 3}
B = {3, 4, 5}
print(A | B)          # {1, 2, 3, 4, 5}
print(A.union(B))     # {1, 2, 3, 4, 5}

b) Intersection

Finds elements common to both sets.

print(A & B)          # {3}
print(A.intersection(B))  # {3}

c) Difference

Finds elements in the first set but not in the second.

print(A - B)          # {1, 2}
print(A.difference(B))    # {1, 2}

 

3. Basic operations in Python

a) Check if an element is in a set

A = {10, 20, 30}
print(20 in A)   # True
print(40 in A)   # False

b) Add an element to a set

A.add(40)
print(A)  # {40, 10, 20, 30}

c) Remove an element from a set

A.remove(20)  # Raises KeyError if not found
print(A)      # {40, 10, 30}

A.discard(50) # No error if element doesn't exist

d) Check subset and superset relationships

X = {1, 2}
Y = {1, 2, 3}
print(X.issubset(Y))   # True
print(Y.issuperset(X)) # True

 

4. Why use sets as an ADT?

• Membership testing efficiency:
  Sets provide constant-time in checks compared to O(n) for lists.
• No duplicates automatically:
  Useful for removing duplicates from a collection.
• Built-in mathematical operations:
  Ideal for problems involving unions, intersections, and differences.

 

5. Example application

Finding unique common tags between two blog posts:

tags_post1 = {"python", "oop", "data-structures"}
tags_post2 = {"python", "sets", "algorithms"}

common_tags = tags_post1 & tags_post2
print("Common tags:", common_tags)  # {'python'}