The big idea: A set holds each value at most once, and holds them in no particular order.
Both of those are guarantees enforced by the structure — not rules the programmer has to remember.
No duplicates
- Adding a value already present changes nothing
- No error, no second copy — the operation simply has no effect
- Uniqueness is structural, so it cannot be forgotten
No order
- There is no first element and no index
- You cannot ask for "the third one"
- Iteration order is not something to rely on
Fast membership
- "Is x in here?" is the defining question
- O(1) on average — usually a hash table underneath
- A list answers the same question in O(n)
Free preview
This is the free notes preview
You're reading the free notes. Aimnova Pro unlocks the full study experience — and you can try it with your first topic free to keep:
- FlashcardsLock in vocabulary and key terms with spaced repetition.
- Practice questionsAnswer exam-style questions and get instant AI marking.
- Mock exams & past-paper vaultSit full mocks and see exactly how examiners award marks.
- Personalised study planA daily plan built around your exam date and weak areas.
| Operation | Means | Example on {1,2,3} and {3,4} |
|---|---|---|
| Union | Everything in either | {1, 2, 3, 4} |
| Intersection | Only what is in both | {3} |
| Difference | In the first, not the second | {1, 2} |
| Membership | Is this value present? | 2 is in the first, not the second |
Difference is not symmetric: a − b is not the same as b − a. With a = {1,2,3} and b = {3,4}: a − b is {1,2}, but b − a is {4}.
Union and intersection do not care about order. Difference does, and that is what gets tested.
Get feedback like a real examiner
Submit your answers and get instant feedback — what you did well, what's missing, and exactly what to write to score full marks.
The signals
- The program asks "have I seen this before?" repeatedly
- Duplicates must be impossible, not merely discouraged
- You need what two collections share, or what only one has
- Position and order are never asked for
- Removing duplicates from a list: convert to a set and back
The costed comparison: The mark is rarely for saying "a set". It is for the comparison:
Membership in a set is O(1) on average; in a list it is O(n). With 10,000 records checked against 10,000 others, that is 10,000 operations against 100,000,000.
How this is tested — you must apply the three operations correctly and justify a set from the operation the program repeats. It comes up two ways:
Paper 2 — working with code
- State the result of a set operation, 1-2 marks
- Define unordered and uniqueness
- Give the result of a union, intersection or difference
Paper 2 — the algorithmic-thinking question
- Choose a set for a scenario and justify it
- Compare the cost against a list
The classic trap: Treating difference as symmetric. a − b keeps what is in a and not in b; b − a keeps what is in b and not in a. They are different sets, and questions are set to catch exactly that.
Two school clubs each keep a list of member IDs. Construct set expressions for: students in both clubs, students in chess but not debate, and all students in at least one club. State why a set suits this better than a list.
Model answer plan
See the mark-by-mark plan — for / against / judgement, with marking guidance — in study mode.