# 6. Control questions and tasks / Контрольні запитання і завдання

## Understanding of sets

1. Define a **set**. What two properties distinguish a set from an arbitrary
   list, and how does your implementation enforce each of them?
2. What is the **cardinality** of a set? What is $|\varnothing|$?
3. Why do $\{1,2,2,3\}$ and $\{1,2,3\}$ denote the **same** set? Why do
   $\{1,2,3\}$ and $\{3,2,1\}$?
4. How do you test whether two sets are **equal** when they are stored as lists
   in an arbitrary order?

## The operations

5. Give the formal definition of $A \cup B$, $A \cap B$, $A \setminus B$, and
   $\overline{A}$.
6. Why does the **complement** require a **universal set** $U$, while union,
   intersection, and difference do not?
7. Express $A \setminus B$ using intersection and complement. *(Hint: relative
   to a universe $U$, $A \setminus B = A \cap \overline{B}$.)*
8. Which of the operations are **commutative**? Is $A \setminus B = B \setminus
   A$ in general? Give a counterexample.
9. State the **De Morgan laws** for sets: $\overline{A \cup B} = \;?$ and
   $\overline{A \cap B} = \;?$

## Implementation and complexity

10. In your implementation, what is the time complexity of `containsElement`? Of
    `union`? How would a hash-based structure change these?
11. Why must the set operations work regardless of the element type (integers,
    strings, …)? What does your code rely on to compare elements?
12. Why should each operation return a **new** set rather than modify its
    arguments?

## Tasks by hand

13. Let $A = \{1,2,3,4\}$, $B = \{3,4,5\}$, $U = \{1,2,3,4,5,6\}$. Compute
    $A \cup B$, $A \cap B$, $A \setminus B$, $B \setminus A$, and $\overline{A}$.
14. With $A = \{1,2,3\}$, $B = \{3,4,5\}$, $C = \{5,6,7\}$, evaluate
    `A intersection B union C` **step by step** and confirm the result
    $\{3,5,6,7\}$ from [4task.md](4task.md).
15. For the same sets, evaluate `A union B difference C` left to right. What is
    the result?