TAOCP 2.3.3 Exercise 9

We are asked to give a table analogous to `(15)` and a diagram analogous to `(16)` showing the trees present after Algorithm `E` has processed all equivalences in `(11)`.

taocpmathematicsalgorithmsvolume-1medium

Section 2.3.3: Other Representations of Trees

Exercise 9. [20] Give a table analogous to (15) and a diagram analogous to (16) that shows the trees present after Algorithm E has processed all of the equivalences in (11) from left to right.

Verified: yes
Solve time: 1m15s

Solution

We are asked to give a table analogous to (15) and a diagram analogous to (16) showing the trees present after Algorithm E has processed all equivalences in (11). Let us proceed step by step, following the conventions of Section 2.3.3.

Let the set of elements be ${1,2,\dots,9}$ and the equivalences given in (11) be processed from left to right. Algorithm E constructs a forest in which each tree represents an equivalence class, with PARENT links pointing upward toward the root. Initially, each element is in a singleton tree, i.e., PARENT(j) = Λ for all $j$.

We now process each equivalence pair $(a,b)$ in (11):

  1. (1 ≡ 2): Since both 1 and 2 have no parent, we make PARENT(2) ← 1. The root of the new tree is 1.
  2. (3 ≡ 6): Both have no parent, so set PARENT(6) ← 3. The root of this tree is 3.
  3. (2 ≡ 4): Find the root of 2, which is 1. 4 has no parent, so set PARENT(4) ← 1. The tree rooted at 1 now contains ${1,2,4}$.
  4. (5 ≡ 7): Both have no parent, so set PARENT(7) ← 5. Root is 5.
  5. (8 ≡ 9): Both have no parent, so set PARENT(9) ← 8. Root is 8.
  6. (1 ≡ 4): The roots of 1 and 4 are both 1. No action needed; the equivalence is already represented.
  7. (3 ≡ 6): Already processed; roots of 3 and 6 are both 3. No action needed.
  8. (5 ≡ 7): Already processed; roots of 5 and 7 are both 5. No action needed.
  9. (6 ≡ 9): Root of 6 is 3. Root of 9 is 8. Merge the trees by making PARENT(8) ← 3. The tree rooted at 3 now contains ${3,6,8,9}$.
  10. (2 ≡ 7): Root of 2 is 1. Root of 7 is 5. Merge by PARENT(5) ← 1. The tree rooted at 1 now contains ${1,2,4,5,7}$.

After processing all equivalences, the forest consists of two trees: one rooted at 1 containing ${1,2,4,5,7}$, and another rooted at 3 containing ${3,6,8,9}$.

The resulting PARENT table analogous to (15) is

$$ \begin{array}{c|ccccccccc} j & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \ \hline \text{PARENT}(j) & Λ & 1 & Λ & 1 & 1 & 3 & 5 & 3 & 8 \end{array} $$

Here, Λ denotes the root of a tree.

The corresponding tree diagram analogous to (16) is

$$ \begin{array}{c} 1 \ ├─ 2 \ ├─ 4 \ └─ 5 \ └─ 7 \end{array} \quad \begin{array}{c} 3 \ ├─ 6 \ ├─ 8 \ └─ 9 \end{array} $$

Each node points upward in the PARENT table; the diagram represents the same structure with roots at the top.

This completes the solution. ∎