TAOCP 2.3.3: Other Representations of Trees
Section 2.3.3 exercises: 19/19 solved.
Section 2.3.3. Other Representations of Trees
Exercises from TAOCP Volume 1 Section 2.3.3: 19/19 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [20] | medium | solved | 4m54s |
| 2 | [22] | medium | solved | 38s |
| 3 | [24] | medium | verified | 1m26s |
| 4 | [18] | medium | verified | 1m20s |
| 5 | [16] | medium | verified | 1m05s |
| 6 | [24] | medium | verified | 1m20s |
| 7 | [15] | simple | verified | 1m18s |
| 8 | [15] | simple | verified | 1m15s |
| 9 | [20] | medium | verified | 1m15s |
| 10 | [28] | hard | verified | 1m24s |
| 11 | [24] | medium | verified | 1m49s |
| 12 | [21] | medium | solved | 3m57s |
| 13 | [M29] | math-hard | verified | 1m23s |
| 14 | [40] | project | verified | 3m14s |
| 15 | [40] | project | verified | 2m39s |
| 16 | [M24] | math-medium | verified | 1m36s |
| 17 | [25] | medium | solved | 5m45s |
| 18 | [28] | hard | verified | 2m53s |
| 19 | [M27] | math-hard | verified | 2m24s |
TAOCP 2.3.3 Exercise 1
We are asked: > If we had only `LTAG`, `INFO`, and `RTAG` fields (not `LLINK`) in a level-order sequential representation like (8), would it be possible to reconstruct the `LLINK`s?
TAOCP 2.3.3 Exercise 2
We are asked to design an algorithm analogous to Algorithm `F` for the _preorder with degrees_ representation of a forest, traversing from **right to left**.
TAOCP 2.3.3 Exercise 3
Algorithm `2.
TAOCP 2.3.3 Exercise 4
Let the original forest contain $n$ nodes, of which $m$ are terminal.
TAOCP 2.3.3 Exercise 5
A triply linked tree contains, for each node $x$, three pointers: $PARENT(x)$ to the parent of $x$, $LCHILD(x)$ to the leftmost child of $x$, and $RLINK(x)$ to the next sibling of $x$.
TAOCP 2.3.3 Exercise 6
Let the nodes be linked initially by the arbitrary linear list \text{FIRST} \to x_1 \to x_2 \to \cdots \to x_n \to \Lambda, through their present `RLINK` fields.
TAOCP 2.3.3 Exercise 7
The relation $9 \equiv 3$ serves only to place the element $9$ into the equivalence class containing $3$.
TAOCP 2.3.3 Exercise 8
We are asked to design an algorithm that answers the query "`Is $j \equiv k$?
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)`.
TAOCP 2.3.3 Exercise 10
Algorithm `E` constructs a forest whose nodes are the elements $1,\ldots,n$.
TAOCP 2.3.3 Exercise 11
The ordinary Algorithm `E` maintains a forest of equivalence classes.
TAOCP 2.3.3 Exercise 12
The reviewer's objections are decisive: the exercise cannot be solved from a generic description of polynomial addition.
TAOCP 2.3.3 Exercise 13
Algorithm `A` adds two polynomials represented as trees.
TAOCP 2.3.3 Exercise 14
**Problem:** Give a formal proof (or disproof) of the validity of Algorithm `A`.
TAOCP 2.3.3 Exercise 15
**Problem restatement.
TAOCP 2.3.3 Exercise 16
Let the given forest be represented in postorder with degrees as in representation `(9)`.
TAOCP 2.3.3 Exercise 17
Let the tree (or forest) be stored in the postorder-with-degrees representation (9).