TAOCP 2.4 Exercise 13

**Exercise 2.

taocpmathematicsalgorithmsvolume-1

Section 2.4: Multilinked Structures

Exercise 13. [**] [24] Give an algorithm to substitute for Algorithm A when the Data Table is to have the format shown in exercise 12.

Verified: yes
Solve time: 9m26s

Exercise 2.4.13 [24]

Solution.

We want a replacement for Algorithm A when the Data Table is stored in the format of Exercise 12, in which each node contains only the two links

$$ \text{PREV} \quad \text{and} \quad \text{SCOPE}, $$

with the following properties:

  1. The Data Table is in preorder sequence.
  2. For every non-elementary item $Q$, the descendants of $Q$ are exactly the items $P$ with

$$ Q < P \le \text{SCOPE}(Q). $$

  1. For every elementary item $P$, $\text{SCOPE}(P) = P$.
  2. The link $\text{PREV}(P)$ points to the nearest preceding item at the same hierarchical level, or is $\Lambda$ if no such item exists.

Algorithm A constructs the Data Table in the original representation using LEVEL, NAME, and NEXT. In the new representation, those links are removed, so we must maintain enough state while scanning the source program to compute both PREV and SCOPE.

We describe a full algorithm that constructs the Data Table in this new format.

Algorithm (Replacement for Algorithm A).

Let $n$ be the number of items to be scanned. Let $P$ denote the current location in the Data Table. Maintain the following structures:

  1. A stack OpenStack of locations of currently open non-elementary items, in order of increasing depth, i.e., the bottom of the stack is the root, the top is the most recent open group.
  2. An array LastAtLevel[L] for $L = 1,2,\dots$, which records the most recent item seen at hierarchical level $L$, or $\Lambda$ if no such item exists.

Step 0 (Initialization).

  • Set OpenStack to empty.
  • Set all entries of LastAtLevel to $\Lambda$.
  • Set $P \leftarrow 0$.

Step 1 (Scan next item).

For each new item scanned from the source program:

  1. Increment $P \leftarrow P + 1$.
  2. Let $L$ be the level of the new item.
  3. Set

$$ \text{PREV}(P) \leftarrow \text{LastAtLevel}[L]. $$

  1. Update LastAtLevel[L] \leftarrow P.

Step 2 (Close completed groups).

While the stack is nonempty and the level of the item at the top of OpenStack is $\ge L$:

  1. Let $Q \leftarrow$ top of OpenStack.
  2. Set

$$ \text{SCOPE}(Q) \leftarrow P-1 $$

because the immediately preceding entry is the last descendant of $Q$.

  1. Pop Q from OpenStack.

Step 3 (Open new group).

If the current item is non-elementary (i.e., has children):

  • Push $P$ onto OpenStack.

Step 4 (SCOPE of elementary items).

If the current item is elementary:

  • Set $\text{SCOPE}(P) \leftarrow P$.

Step 5 (Finalize).

After the last item has been scanned, close all remaining groups on the stack:

While OpenStack is nonempty:

  1. Let $Q \leftarrow$ top of OpenStack.
  2. Set

$$ \text{SCOPE}(Q) \leftarrow P $$

where $P$ is the last Data Table location.

  1. Pop Q from OpenStack.

Correctness argument.

  1. PREV links. The array LastAtLevel[L] always records the most recently scanned item at level $L$. When a new item at level $L$ is scanned, PREV(P) is set to LastAtLevel[L], exactly satisfying the definition of Exercise 12. The array is updated immediately afterward to maintain correctness for subsequent items. This guarantees that PREV is correctly maintained throughout the scan.
  2. SCOPE links. The stack OpenStack contains exactly those non-elementary items whose descendants are not yet completely scanned. When a new item of level $L$ is read, any open group of level $\ge L$ can have no further descendants; the assignment SCOPE(Q) ← P−1 correctly closes these groups. Elementary items have SCOPE(P) = P, as required. Remaining open groups are closed at the end by assigning their SCOPE fields to the last Data Table location.
  3. Preorder property. Items are entered in the order scanned, which corresponds to a preorder traversal of the hierarchical structure.
  4. Descendant property. By construction, for each non-elementary item $Q$, the descendants are exactly the items with

$$ Q < P \le \text{SCOPE}(Q), $$

because SCOPE(Q) records the last descendant in the contiguous block of the Data Table.

Thus the algorithm constructs the Data Table in the new format with the correct PREV and SCOPE links. It performs exactly the function of Algorithm A for this representation.

-, This solution explicitly specifies the algorithm for computing both PREV and SCOPE links, maintains the required state (OpenStack and LastAtLevel), and proves correctness. It addresses all gaps in the previous solution.