IB COMPUTER SCIENCE | B4.1.5 Sets as an ADT (HL)

Lesson objective

Construct and apply sets with unique, unordered membership, basic updates, set algebra and subset/superset checks in Python and Java.

Learn

B4.1.5 | SETS AS AN ADT (HL ONLY)

01 | WHEN MEMBERSHIP MATTERS MORE THAN POSITION

A school wants to invite every student who attends Robotics or Coding, without sending duplicate invitations. A list of registration events can contain the same student several times. For the invitation membership, we need a collection in which each student ID occurs only once.

A set ADT represents a collection of distinct elements. Its core questions are whether an element belongs, how to add or remove it, and how its membership relates to another set. The abstract contract does not assign numbered positions to its elements.

Throughout this lesson, A is the Robotics membership {S01, S02, S03}, and B is Coding {S03, S04}. S03 belongs to both, but is still one student ID.

02 | TWO ESSENTIAL PROPERTIES

Property Meaning Consequence
Uniqueness An element is either present or absent; repeated additions do not create extra occurrences Adding S02 twice leaves one S02 membership
Unordered nature The ADT does not promise a sequence or an index position {S01, S02} and {S02, S01} describe the same membership

Unordered does not mean the computer must shuffle elements on every display. It means a caller should not rely on a particular iteration order unless a more specific implementation contract promises one.

A list can record order and repetition; a set deliberately represents membership without those features. Converting an event list to a set loses repeated occurrences and sequence information.

03 | DEFINE THE OPERATIONS AND POLICIES

Operation High-level meaning
contains(x) Test whether x is a member
add(x) Ensure x is present without duplicating it
remove(x) Ensure x is absent; specify the missing-member policy
size Count distinct members
union Members in either input, including those in both
intersection Members common to both inputs
difference A minus B Members in A that are not in B
subset / superset Test whether all members of one set occur in another

The ADT describes the meaning; the language API chooses names, return values and error behaviour. Python add returns None, whereas Java Set.add returns whether membership changed. They can both implement the same uniqueness rule.

A missing-member removal can raise an exception, return False or do nothing, depending on the chosen operation. State which one your program uses.

04 | CONSTRUCT A PYTHON SET

robotics = {"S01", "S02", "S03"}
registrations = ["S01", "S02", "S01", "S03"]
unique_ids = set(registrations)
empty_ids = set()
print(sorted(unique_ids))
print(len(unique_ids))
# ['S01', 'S02', 'S03']
# 3

Braces containing elements create a set literal. set(iterable) constructs membership from an existing collection, collapsing repeats. An empty set is set(); empty braces {} create a dictionary instead.

sorted returns a separate list for predictable presentation. That does not give the set an index order or change its ADT contract. The examples use same-type string IDs so they can be sorted consistently.

05 | CONSTRUCT A JAVA SET

Set<String> robotics = new HashSet<>(
    Arrays.asList("S01", "S02", "S03"));
Set<String> emptyIds = new HashSet<>();
System.out.println(robotics.size());
// 3

These statements belong inside a method such as main with java.util.Set, HashSet and Arrays imported. Set is the interface used by the variable; HashSet is the selected concrete implementation.

Use the complete program later if you want a file that runs immediately. HashSet does not promise iteration order. A TreeSet copy can provide sorted presentation for these comparable string IDs, but that is a separate ordered implementation choice.

06 | TEST MEMBERSHIP, NOT AN INDEX

robotics = {"S01", "S02", "S03"}
print("S02" in robotics)
print("S99" not in robotics)
# True
# True

Python in asks whether the element is a member. Java uses robotics.contains("S02"). Neither requires knowing where the implementation stores the member.

A Python set does not support robotics[0]. If a user needs a numbered display, create an appropriate sequence for presentation. Do not mistake the display’s first row for an intrinsic first member of the set.

07 | ADD A NEW OR EXISTING ELEMENT

robotics = {"S01", "S02", "S03"}
result = robotics.add("S02")
print(result, len(robotics))
robotics.add("S05")
print(sorted(robotics))
# None 3
# ['S01', 'S02', 'S03', 'S05']

Adding existing S02 leaves membership unchanged. Adding new S05 increases the distinct-member count. Python’s returned None does not tell you whether the element was already present; inspect membership or size if that matters.

In Java, add("S02") returns false when S02 is already present, while adding a new S05 returns true. Keep the distinction between an operation’s membership effect and its language-specific return value.

08 | REMOVE CAREFULLY WHEN MEMBERSHIP IS UNCERTAIN

robotics = {"S01", "S02", "S03"}
robotics.remove("S02")
robotics.discard("S99")
print(sorted(robotics))
try:
    robotics.remove("S99")
except KeyError:
    print("S99 was not registered")
# ['S01', 'S03']
# S99 was not registered

Python remove raises KeyError for an absent element. discard leaves membership unchanged without that missing-member error. Both mutate the original set and return None on normal completion.

Java Set.remove returns true when membership changed and false when the requested member was absent. A missing-ID policy is part of the application design: silently tolerating an absent member can be suitable for cleanup, while a registration screen might need to report it.

09 | UNION: IN A OR B, INCLUDING BOTH

Union A ∪ B includes both circles A | Robotics B | Coding S01 S02 S03 S04
Union A ∪ B includes both circles. Shading marks the result region; each ID belongs in one region.
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
either = a | b
print(sorted(either))
# ['S01', 'S02', 'S03', 'S04']

Union gathers every element present in at least one input. The overlapping member S03 appears once, so the union has four members rather than five.

Python a.union(b) is an equivalent method form. These expressions produce a new set and leave a and b unchanged. In Boolean terms, union membership is inclusive OR, not “exactly one”.

10 | INTERSECTION: IN A AND B

Intersection A ∩ B is the overlap A | Robotics B | Coding S01 S02 S03 S04
Intersection A ∩ B is the overlap. Shading marks the result region; each ID belongs in one region.
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
both = a & b
print(sorted(both))
# ['S03']

Intersection contains only the common members. It answers “Which students attend both clubs?” Python also offers a.intersection(b). The result can be empty when there is no overlap.

Union and intersection are commutative: swapping the two inputs does not change membership of the result. This is not true of ordinary difference.

11 | DIFFERENCE: THE DIRECTION MATTERS

Difference A − B selects only A outside the overlap A | Robotics B | Coding S01 S02 S03 S04
Difference A − B selects only A outside the overlap. Shading marks the result region; each ID belongs in one region.
a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
print(sorted(a - b))
print(sorted(b - a))
# ['S01', 'S02']
# ['S04']

A minus B contains Robotics members who are not in Coding. B minus A answers the reverse question. These are different sets here, so do not swap the operands when translating a scenario.

Python also provides a.difference(b). Difference does not remove members from a unless you use a mutating form such as difference_update or -=.

12 | MAKE JAVA SET ALGEBRA NON-DESTRUCTIVE

Set<String> either = new HashSet<>(robotics);
either.addAll(coding);

Set<String> both = new HashSet<>(robotics);
both.retainAll(coding);

Set<String> roboticsOnly = new HashSet<>(robotics);
roboticsOnly.removeAll(coding);

These statements use the sets and imports from the complete Java program. addAll, retainAll and removeAll change the receiving set. Creating a copy first preserves the original club membership.

retainAll keeps only members also in the supplied collection; removeAll removes the supplied collection’s members. Assigning another variable to robotics would create an alias, not an independent set copy.

13 | SUBSETS: ALL OF THESE MEMBERS ARE INCLUDED

team = {"S01", "S03"}
robotics = {"S01", "S02", "S03"}
print(team.issubset(robotics))
print(team <= robotics)
print(robotics <= robotics)
# True
# True
# True

Team is a subset of Robotics because every Team member occurs in Robotics. Equality is allowed for an ordinary subset relation: every set is a subset of itself.

One shared member is insufficient to prove subset. {S01, S99} is not a subset of Robotics even though S01 is shared. Check every required membership.

14 | SUPERSETS AND PROPER RELATIONS

team = {"S01", "S03"}
robotics = {"S01", "S02", "S03"}
print(robotics.issuperset(team))
print(robotics >= team)
print(team < robotics)
print(robotics < robotics)
# True
# True
# True
# False

A superset relation reverses the subset view: Robotics is a superset of Team. A proper subset requires inclusion and inequality, so Team is a proper subset of Robotics but Robotics is not a proper subset of itself.

Java robotics.containsAll(team) tests whether Robotics is a superset of Team, equivalently whether Team is a subset of Robotics. For finite sets, adding a smaller-size check distinguishes a proper subset. The argument direction matters.

15 | EMPTY SETS, EQUALITY AND DISJOINTNESS

Statement Result Reason
∅ is a subset of A True There is no empty-set member missing from A
A is a superset of ∅ True The same inclusion rule viewed in reverse
A ∩ ∅ ∅ No members are shared
A ∪ ∅ A Empty membership adds nothing
A − A ∅ Every member is excluded by the second A

Set equality compares membership, not order or variable names. Python uses ==; Java Set uses equals for set membership equality. Java == instead compares whether two references reach the same object.

Two sets are disjoint when their intersection is empty. Python a.isdisjoint(b) expresses this directly. A set can be empty without being an error: “no students attend both clubs” is a meaningful result.

16 | EXPLORE THE OPERATIONS VISUALLY

Enter IDs such as S01, S02 and S03, separated by commas. Whitespace around each ID is ignored, but IDs must match uppercase S followed by two digits. Blank input means an empty set; repeated IDs collapse to one membership. Results are displayed sorted for checking, not because the ADT promises that order.

Try identical sets, disjoint sets, an empty input and reversed difference. The table separates A-only, shared and B-only members so you can justify each answer from membership rather than memorising the picture.

17 | DO NOT CONFUSE A SET WITH AN ELEMENT

ids = {"S01", "S02"}
print("S01" in ids)
print({"S01"} <= ids)
print(set("S01"))
# True
# True
# The final set contains the characters S, 0 and 1.

"S01" is one string element. {"S01"} is a set containing that element. set("S01") iterates through the string, so it constructs a character set rather than a one-ID set.

For a one-element set, use {"S01"} or set(["S01"]). Membership and subset are different questions even when the examples seem to refer to one ID.

18 | UPDATES, ALIASES AND COPIES

a = {"S01", "S02"}
alias = a
copy = a.copy()
alias.add("S03")
print(sorted(a))
print(sorted(copy))
result = a | {"S04"}
print(sorted(a))
print(sorted(result))
# ['S01', 'S02', 'S03']
# ['S01', 'S02']
# ['S01', 'S02', 'S03']
# ['S01', 'S02', 'S03', 'S04']

alias and a refer to one mutable set. copy has a separate membership container. The union expression also creates a separate set. By contrast, a.update(other), intersection_update and difference_update mutate a.

This is a shallow copy: objects referenced as members are not recursively duplicated. The element restrictions still matter, and the immutable string IDs used here keep the example simple.

19 | CHOOSE VALID ELEMENTS AND CONSISTENT IDENTIFIERS

Python set requires hashable members, such as strings, integers and suitable immutable tuples. A mutable list or another mutable set cannot normally be a member of a Python set. A frozenset can provide an immutable set value when needed, though it is not required for the core examples.

The logical set ADT is not intrinsically restricted to one hashing mechanism; that restriction belongs to this implementation. Java HashSet similarly relies on consistent equals and hashCode behaviour. Changing a stored object in a way that changes its equality or hash behaviour can undermine lookup.

Define what counts as the same identifier. "S01" and "s01" are different Python strings. If the application requires case-insensitive IDs, normalise deliberately before storage rather than expect the set to guess that rule.

20 | COMPLETE PYTHON MEMBERSHIP APPLICATION

Save this as sets_demo.py and click Run. Both club inputs remain unchanged by the algebra operations. sorted is used only to make the displayed results reproducible.

robotics = {"S01", "S02", "S03"}
coding = {"S03", "S04"}

print("S02" in robotics)
robotics.add("S02")
print(len(robotics))
robotics.add("S05")
robotics.discard("S99")
robotics.remove("S05")

both = robotics & coding
either = robotics | coding
robotics_only = robotics - coding
coding_only = coding - robotics

print(sorted(both))
print(sorted(either))
print(sorted(robotics_only))
print(sorted(coding_only))
print({"S01", "S03"}.issubset(robotics))
print(robotics.issuperset({"S01", "S03"}))
print(robotics == {"S03", "S02", "S01"})

The output is True, 3, then [S03], [S01, S02, S03, S04], [S01, S02], [S04], followed by True, True, True. The actual Python list displays include quotes around the IDs.

The duplicate add does not increase size. S05 is added and then removed, so the original Robotics membership is restored before the comparisons.

21 | COMPLETE JAVA MEMBERSHIP APPLICATION

Save this as SetsExample.java and run main. The TreeSet copies are for sorted display of these string IDs. The actual membership inputs remain HashSet objects.

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeSet;

public class SetsExample {
    public static void main(String[] args) {
        Set<String> robotics = new HashSet<>(Arrays.asList("S01", "S02", "S03"));
        Set<String> coding = new HashSet<>(Arrays.asList("S03", "S04"));

        System.out.println(robotics.contains("S02"));
        System.out.println(robotics.add("S02"));
        System.out.println(robotics.size());
        robotics.add("S05");
        System.out.println(robotics.remove("S99"));
        robotics.remove("S05");

        Set<String> both = new HashSet<>(robotics);
        both.retainAll(coding);
        Set<String> either = new HashSet<>(robotics);
        either.addAll(coding);
        Set<String> roboticsOnly = new HashSet<>(robotics);
        roboticsOnly.removeAll(coding);
        Set<String> codingOnly = new HashSet<>(coding);
        codingOnly.removeAll(robotics);

        System.out.println(new TreeSet<>(both));
        System.out.println(new TreeSet<>(either));
        System.out.println(new TreeSet<>(roboticsOnly));
        System.out.println(new TreeSet<>(codingOnly));

        Set<String> required = new HashSet<>(Arrays.asList("S01", "S03"));
        boolean requiredIsSubset = robotics.containsAll(required);
        boolean roboticsIsSuperset = robotics.containsAll(required);
        boolean properSubset = requiredIsSubset && required.size() < robotics.size();
        System.out.println(requiredIsSubset);
        System.out.println(roboticsIsSuperset);
        System.out.println(properSubset);
        System.out.println(robotics.equals(
            new HashSet<>(Arrays.asList("S03", "S02", "S01"))));
    }
}

Java prints true for the membership check, false for the duplicate add, 3 for size and false for the absent removal. The algebra results then display [S03], [S01, S02, S03, S04], [S01, S02] and [S04]. The four final relation checks are true.

requiredIsSubset and roboticsIsSuperset intentionally use the same containsAll expression because they describe the same inclusion relationship from opposite viewpoints.

22 | CONSTRUCT A SMALL SET ADT WITHOUT HASHING

This teaching implementation uses a Python list internally but exposes membership-style operations. It shows that the ADT contract and the underlying representation are separate. Save it as list_set.py if you want to test the operations yourself.

class ListSet:
    def __init__(self, values=()):
        self._items = []
        for value in values:
            self.add(value)

    def contains(self, value):
        return value in self._items

    def add(self, value):
        if self.contains(value):
            return False
        self._items.append(value)
        return True

    def discard(self, value):
        if not self.contains(value):
            return False
        self._items.remove(value)
        return True

    def size(self):
        return len(self._items)

    def snapshot(self):
        return tuple(self._items)

    def union(self, other):
        result = ListSet(self._items)
        for value in other._items:
            result.add(value)
        return result

    def intersection(self, other):
        return ListSet(value for value in self._items if other.contains(value))

    def difference(self, other):
        return ListSet(value for value in self._items if not other.contains(value))

    def issubset(self, other):
        return all(other.contains(value) for value in self._items)

    def issuperset(self, other):
        return other.issubset(self)

add and discard return whether membership changed in this custom API, unlike Python’s built-in methods. union, intersection and difference return new ListSet objects and leave both inputs unchanged. snapshot provides values for inspection, not a promised ordering feature of the ADT.

The example relies on equality checks and cooperative use of the private-by-convention _items field. It is not a replacement for the built-in set in performance-sensitive code.

23 | APPLY SETS TO A CHECK-IN TASK

registered = {"S01", "S02", "S03", "S04"}
raw_scans = ["S01", "S03", "S01", "S99"]
scanned = set(raw_scans)
present = registered & scanned
absent = registered - scanned
unexpected = scanned - registered
print(sorted(present))
print(sorted(absent))
print(sorted(unexpected))
# ['S01', 'S03']
# ['S02', 'S04']
# ['S99']

The event list retains repeated scans; the scanned set represents distinct IDs. Intersection identifies recognised attendees, while the two differences distinguish absence from unrecognised scans.

Do not discard the event list if you still need scan times, repeated-event counts or arrival order. Different representations can support different parts of the same application.

24 | PERFORMANCE BELONGS TO THE IMPLEMENTATION

Built-in hash-based sets can provide expected constant-time membership, addition and removal under suitable hashing and resizing assumptions. That does not mean every individual operation or every possible workload has guaranteed O(1) time. The next lesson explains hashing mechanics in detail.

Our ListSet membership scans values, so it is O(n) worst case. Its pairwise intersection and difference can cost O(nm) with input sizes n and m, because each of n candidates may search the other m values. A naive union also performs repeated membership work.

A set can be represented with other structures, including suitable trees. The logical uniqueness and membership contract does not itself dictate a hash table, iteration order or universal performance bound.

25 | TEST MEMBERSHIP LAWS AND BOUNDARIES

a = {"S01", "S02", "S03"}
b = {"S03", "S04"}
assert a | b == b | a
assert a & b == b & a
assert a - b == {"S01", "S02"}
assert b - a == {"S04"}
assert a - a == set()
assert set() <= a
assert a <= a and not a < a
before = a.copy()
a.add("S01")
assert a == before
assert a.isdisjoint({"S99"})

Test empty inputs, identical membership, complete separation and partial overlap. Include missing-member removal under the exact API policy, and confirm whether a result should mutate an input or create a new set.

When writing assertions, compare membership rather than an incidental printed order. An expected sorted list is appropriate only if the output contract explicitly calls for sorted presentation.

26 | CONSTRUCT, APPLY AND EXPLAIN

A school needs students who attended either an AI workshop or Robotics, students who attended both, students who attended AI only, and confirmation that a project team contains only registered workshop students. Choose the appropriate operations before writing code.

Explain the reason: intersection keeps only shared IDs, therefore it identifies students who attended both. Difference excludes the second membership, so its operand direction determines who remains. A subset test checks every team ID, rather than merely finding any overlap.

The next lesson connects ADT principles to the mechanics of hash tables, sets and maps. Keep logical membership separate from storage choices as you move on.

MATCH THE SET OPERATION

Terminology

Terminology

Set ADT

A collection of distinct elements with membership and set operations, without an intrinsic sequence contract.

Element

A value that can be a member of a set.

Uniqueness

Repeated equal membership does not create another logical occurrence.

Unordered nature

The ADT promises no particular element sequence or index positions.

Membership

Whether an element belongs to a set.

Cardinality

The number of distinct members.

Empty set

A set containing no elements.

Union

Members in at least one of two input sets.

Intersection

Members present in both input sets.

Difference

Members of the first set that are absent from the second.

Subset

Every member of one set occurs in the other; equality is permitted.

Superset

A set containing every member of another set.

Proper subset

A subset unequal to the containing set.

Proper superset

A superset unequal to the contained set.

Set equality

Two sets have exactly the same members.

Disjoint sets

Sets with an empty intersection.

Idempotent addition

Adding an existing member leaves logical membership unchanged.

Mutation

Changing the membership of an existing set object.

Non-mutating result

A separate set result that preserves the input sets.

Alias

Another reference to the same object.

Shallow copy

A new container referring to the same member objects rather than recursively cloning them.

Hashable value

A Python value supporting a stable hash and consistent equality suitable for hashed membership.

HashSet

A Java hash-based implementation of the Set interface.

containsAll

A Java collection operation used here to test whether the receiver includes all supplied members.

retainAll

A Java mutating operation keeping only members also in the supplied collection.

removeAll

A Java mutating operation removing supplied members from the receiver.

discard

Python removal that tolerates an absent member without KeyError.

Normalisation

Deliberately converting data to an agreed representation before comparison or storage.

Commutativity

Swapping inputs leaves the result unchanged, as for union and intersection.

Representation independence

A logical contract can be implemented by different internal structures.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which are core properties of this set ADT?
2. Which construct the intended Python sets?
3. For A={S01,S02,S03} and B={S03,S04}, which are true?
4. Which difference results are correct?
5. Which subset statements are true?
6. Which Java statements fit the set operations?
7. Which Python removal statements are correct?
8. Which equality or ordering statements are correct?
9. Which design choices are sound?
10. Which performance statements are appropriate?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Define a set as an ADT.

2. Explain why a set suits distinct workshop attendees but not a complete scan-event history.

3. Construct Python sets for the two clubs and calculate their union and intersection.

4. Explain the difference between A minus B and B minus A.

5. Distinguish subset and proper subset.

6. Explain how to test in Java whether Team is a subset of Robotics.

7. Compare Python remove, Python discard and Java Set.remove for absent members.

8. Explain how to construct a Java intersection while preserving both inputs.

9. Trace the alias example when alias refers to a and then adds S03.

10. Evaluate the claim that every set membership operation is guaranteed O(1).

11. Construct a check-in solution identifying present, absent and unexpected IDs.

12. Describe tests for a set implementation and its algebra operations.

CONSTRUCT AND APPLY | MEMBERSHIP CHECK-IN

Construct a check-in solution for registered IDs S01, S02, S03 and S04 and scans S01, S03, S01 and S99. Report present, absent and unexpected IDs. Then test whether team {S01, S03} is a subset of registered students. Explain why the scan list may still need to be retained.

Reveal a worked solution
registered = {"S01", "S02", "S03", "S04"}
raw_scans = ["S01", "S03", "S01", "S99"]
scanned = set(raw_scans)
present = registered & scanned
absent = registered - scanned
unexpected = scanned - registered
team = {"S01", "S03"}
assert present == {"S01", "S03"}
assert absent == {"S02", "S04"}
assert unexpected == {"S99"}
assert team <= registered

The distinct memberships answer attendance questions. The original event list retains repeated scans and their sequence; an actual timestamped event record would retain times too. A set alone cannot reconstruct that information.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B4.1.5 Sets as an ADT (HL) is coming soon. Complete the matching task and written questions in your exercise book.