TAOCP 2.3.3 Exercise 8

We are asked to design an algorithm that answers the query "`Is $j \equiv k$?

taocpmathematicsalgorithmsvolume-1simple

Section 2.3.3: Other Representations of Trees

Exercise 8. [15] Algorithm E sets up a tree structure that represents the given pairs of equivalent elements, but the text does not mention explicitly how the result of Algorithm E can be used. Design an algorithm that answers the question, "Is j ≡ k?", assuming that 1 <= j <= n, 1 <= k <= n, and that Algorithm E has set up the PARENT table for some set of equivalences.

Verified: yes
Solve time: 1m15s

Solution

We are asked to design an algorithm that answers the query "Is $j \equiv k$?" given that Algorithm E has already established the PARENT table representing a collection of equivalence classes. By the construction of Algorithm E in Section 2.3.3, each equivalence class is represented as a rooted tree, where the PARENT field of each node points to its parent in the tree, and the root node is its own parent, or equivalently, has PARENT(root) = root or Λ. Two elements are equivalent if and only if they belong to the same tree.

We exploit the fact that each element's representative can be found by following its PARENT links up to the root of its tree.

Let us define the auxiliary function FIND(x) as follows:

  1. Set y ← x.
  2. While PARENT(y) ≠ y, set y ← PARENT(y).
  3. Return y.

This function returns the root of the tree containing x, which is the canonical representative of the equivalence class of x.

The algorithm for testing equivalence of two elements $j$ and $k$ is then:

  1. Compute r_j ← FIND(j) and r_k ← FIND(k).
  2. If r_j = r_k, then $j \equiv k$; otherwise $j \not\equiv k$.

Formally:

Algorithm Q. [Test equivalence.]

Q1. [Find representative of $j$.] Set r_j ← j. While PARENT(r_j) ≠ r_j, set r_j ← PARENT(r_j).

Q2. [Find representative of $k$.] Set r_k ← k. While PARENT(r_k) ≠ r_k, set r_k ← PARENT(r_k).

Q3. [Compare representatives.] If r_j = r_k, return TRUE; else return FALSE. ∎

Correctness.

Suppose that $j \equiv k$. Then by Algorithm E, both $j$ and $k$ belong to the same equivalence tree. Following their PARENT links leads to the same root, so r_j = r_k. Conversely, if r_j = r_k, then $j$ and $k$ have the same root and thus belong to the same equivalence class, giving $j \equiv k$.

Each FIND requires traversing a path from a node to the root of its tree, which takes at most the height of that tree. Since Algorithm E constructs trees with at least one node per equivalence class, the algorithm is finite and returns the correct answer for all valid inputs $1 \le j,k \le n$.

This completes the proof. ∎

Optional optimization (path compression).

If many equivalence tests are to be performed, one may modify FIND(x) to set PARENT(y) ← root for each node y along the path to the root. This reduces the cost of subsequent searches, but is not required to answer the exercise.