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

Ordered pairs and the Cartesian product #

1. What is an ordered pair? State the condition under which $(a,b) = (c,d)$, and explain why $(1,2) \neq (2,1)$ while $\{1,2\} = \{2,1\}$.
2. Define the Cartesian product $A \times B$. What is $|A \times B|$ in terms of $|A|$ and $|B|$?
3. Is $A \times B = B \times A$ in general? When are they equal?
4. What is $A \times \varnothing$? Justify your answer from the definition.

Relations #

5. Define a binary relation from $A$ to $B$. What does it mean for a relation to be a relation on a set $A$?
6. Exactly what does isRelationValid(relation, A, B) verify? Phrase your answer using the words subset and $A \times B$.
7. How many distinct relations exist from $A$ to $B$? Why? (Hint: a relation is any subset of $A \times B$.)
8. What does it mean to define a relation by a predicate $P(a,b)$? Write the set-builder form of such a relation.

Implementation and complexity #

9. How do you represent an ordered pair and a whole relation without using a built-in tuple/set type? How are two pairs compared for equality?
10. What is the time complexity of cartesianProduct? Why can it not be faster than $O(|A|\cdot|B|)$?
11. What is the cost of isRelationValid with a list-based membership test, and how would a hash-based test change it?
12. In findRelations, who decides whether the pair $(a,a)$ is included — the algorithm or the predicate? Explain.

Tasks by hand #

13. Compute $A \times B$ for $A = \{1,2\}$ and $B = \{x, y\}$. How many pairs do you get?
14. List the relation “$a < b$” on the set $A = \{1,2,3\}$ (pairs $(a,b)$ with $a,b \in A$ and $a < b$). How many pairs are there?
15. Let $A = \{2, 3\}$ and $B = \{6, 8, 9\}$. Using the predicate “$a$ divides $b$”, list the pairs of $A \times B$ that satisfy it.

Laboratory/Laboratory2/6questions.md · 1.9 KB · updated 2026-07-31 21:14