2. Methodical guidelines / Методичні вказівки #

This section is self-contained: it collects all the theory of the work’s theme — finite sets and their operations — together with practical guidance for carrying out the tasks in 4task.md. No outside material is required.

2.1 Sets: basic notions #

A set is an unordered collection of distinct objects, called its elements. We write $x \in A$ if $x$ is an element of $A$, and $x \notin A$ otherwise. A finite set may be written by listing its elements in braces, e.g. $A = \{1, 2, 3\}$.

Two conventions define what a set is:

• Distinctness (no duplicates). An element is either in the set or not; repeating it changes nothing: $\{1, 2, 2, 3\} = \{1, 2, 3\}$.
• No order. The elements have no positions: $\{1, 2, 3\} = \{3, 1, 2\}$.

Equality. $A = B$ means they have exactly the same elements — every element of $A$ is in $B$ and every element of $B$ is in $A$. Equality is therefore decided by membership, not by position. This is the rule you must use to compare two sets that are stored as lists in an arbitrary order.

Cardinality. $|A|$ is the number of distinct elements of $A$. The empty set $\varnothing$ contains nothing, so $|\varnothing| = 0$.

Subset. $A \subseteq B$ (“A is a subset of B”) means every element of $A$ is also in $B$. Note $A = B$ exactly when $A \subseteq B$ and $B \subseteq A$.

Universal set. Many problems fix in advance a set $U$ of all elements under consideration — the universe. It is the reference domain against which the complement of a set is taken (see below).

2.2 The operations of this work #

Let $A$ and $B$ be sets and $U$ a universal set with $A \subseteq U$.

Two remarks that matter for the implementation:

• Complement is relative. $\overline{A}$ has no meaning without a universe; outside $U$ there is no notion of “everything not in $A$.” Your complement function therefore takes the universal set as an explicit argument.
• Difference is directed. $A \setminus B$ and $B \setminus A$ are different in general: for the sets above, $A \setminus B = \{1,2\}$ but $B \setminus A = \{4,5\}$. Sets with $A \cap B = \varnothing$ are called disjoint.

2.3 The algebra of sets #

The operations obey algebraic laws. You do not need to prove them for this work, but they explain why your functions should behave as they do, and they let you check results by hand (see 6questions.md).

Note in particular the identity $A \setminus B = A \cap \overline{B}$ (relative to a universe $U$): difference can be expressed through intersection and complement. Union and intersection are commutative; difference is not.

2.4 Implementing a set without a built-in set type #

The rules forbid the language’s own set type (HashSet, set(), Set, …). Use a plain array/list and maintain the distinctness invariant yourself. Every operation reduces to one primitive — the membership test:

• membership ($x \in A$) — scan the list and compare elements (this is containsElement);
• insertion — append $x$ only if containsElement(A, x) is false;
• construction from a raw list — insert elements one by one, so duplicates drop out automatically.

2.5 Reference algorithms #

function contains(A, x):
    for y in A:
        if y == x: return true
    return false

function union(A, B):
    R ← copy of A
    for x in B:
        if not contains(R, x): append x to R
    return R

function intersection(A, B):
    R ← empty list
    for x in A:
        if contains(B, x): append x to R
    return R

function difference(A, B):        # A \ B
    R ← empty list
    for x in A:
        if not contains(B, x): append x to R
    return R

function complement(A, U):        # elements of U not in A
    return difference(U, A)

2.6 Complexity #

With a list representation, contains is $O(|A|)$, so union, intersection, and difference cost $O(|A| \cdot |B|)$. This is acceptable for the work. A hash-based or sorted representation would reduce membership to $O(1)$ or $O(\log n)$ respectively — which is precisely what the forbidden built-in set types do internally, and the reason for implementing the mechanism by hand here.

2.7 The expression evaluator (Tier 3) #

The final tier evaluates a string such as "A intersection B union C" given a dictionary that maps names to sets. A workable approach:

1. tokenise the string into names (A, B, C) and operator words (union, intersection, difference, complement);
2. look up each name in the dictionary to obtain its set;
3. fold the operators over the operands, applying them left to right.

Left-to-right evaluation reproduces the expected output of the example: A intersection B union C gives $(A \cap B) \cup C = \{3,5,6,7\}$ (see 4task.md). Reuse the Tier 1–2 functions inside the evaluator — do not re-implement the operations.

Laboratory/Laboratory1/2method.md · 6.3 KB · updated 2026-07-31 21:14