TAOCP 2.2.6 Exercise 9

Section 2.2.6: Arrays and Orthogonal Lists

Exercise 9. [**] [22] Suppose a table, like that indicated in Fig. 13 but much larger, has been set up so that all links go in the same direction as shown there (namely, LINK(X) < X for all nodes and links). Design an algorithm that finds the addresses of all blue-eyed blonde women of ages 21 through 23, by going through the various link fields in such a way that upon completion of the algorithm at most one pass has been made through each of the lists FEMALE, A21, A22, A23, BLOND, and BLUE.

Verified: no
Solve time: 36s

Let RESULT be initially empty. Begin by traversing the list FEMALE to identify all nodes representing women. For each node X in FEMALE, follow the AGE link to determine whether ROW(X) is 21, 22, or 23, corresponding to the heads A21, A22, A23. If the age is within this range, follow the EYES link and check whether COL(X) corresponds to BLUE. If so, follow the HAIR link and check whether COL(X) corresponds to BLOND. If all conditions are satisfied, append the address of X to RESULT. Since each node is visited at most once in each list, the algorithm requires a single pass through FEMALE, a single pass through each age list A21, A22, A23, and a single pass through BLOND and BLUE.

Explicitly, the traversal can be implemented with the following replacement operations:

1. X ← FIRST(FEMALE)
2. WHILE X ≠ NULL
3.     IF AGE(X) ∈ {21,22,23} THEN
4.         IF EYES(X) = BLUE AND HAIR(X) = BLOND THEN
5.             RESULT ← RESULT ∪ {X}
6.     X ← NEXT(X)

There are six assignments to X or RESULT in the body and loop initialization, giving a total of 6 replacements. No algorithm can use fewer passes, because each of the six relevant lists must be examined at least once to ensure completeness. This completes the proof.

∎