TAOCP 2.3.2: Binary Tree Representation of Trees
Section 2.3.2 exercises: 22/22 solved.
Section 2.3.2. Binary Tree Representation of Trees
Exercises from TAOCP Volume 1 Section 2.3.2: 22/22 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [20] | medium | solved | 39s |
| 2 | [20] | medium | solved | 41s |
| 3 | [22] | medium | verified | 1m35s |
| 4 | [19] | medium | solved | 33s |
| 5 | [23] | medium | verified | 4m11s |
| 6 | [25] | medium | verified | 2m55s |
| 7 | [M20] | math-medium | verified | 1m07s |
| 8 | [M20] | math-medium | verified | 1m20s |
| 9 | [M21] | math-medium | verified | 2m27s |
| 10 | [M23] | math-medium | verified | 1m05s |
| 11 | [15] | simple | verified | 2m12s |
| 12 | [M21] | math-medium | verified | 4m07s |
| 13 | [26] | hard | verified | 1m40s |
| 14 | [M21] | math-medium | verified | 1m15s |
| 15 | [23] | medium | verified | 1m21s |
| 16 | [24] | medium | verified | 1m26s |
| 17 | [M40] | math-project | verified | 1m37s |
| 18 | [25] | medium | verified | 57s |
| 19 | [M35] | math-hard | verified | 1m33s |
| 20 | [M22] | math-medium | verified | 1m22s |
| 21 | [25] | medium | verified | 1m20s |
| 22 | [M26] | math-hard | verified | 3m01s |
TAOCP 2.3.2 Exercise 1
Let $B$ be a binary tree.
TAOCP 2.3.2 Exercise 2
Let a forest $F = (T_1, T_2, \dots, T_n)$ be given, with nodes numbered in Dewey decimal notation as in Section 2.
TAOCP 2.3.2 Exercise 3
Let the Dewey decimal notation of a node be d_1.
TAOCP 2.3.2 Exercise 4
We are asked to determine whether the statement > "The terminal nodes of a tree occur in the same relative position in preorder and postorder.
TAOCP 2.3.2 Exercise 5
Let the roots of the trees of the forest $F$ be regarded as siblings arranged from left to right.
TAOCP 2.3.2 Exercise 6
Let $T$ be a nonempty binary tree in which every node has either $0$ or $2$ children.
TAOCP 2.3.2 Exercise 7
Let the partial order on the nodes of a forest be defined by u < v whenever $v$ is a descendant of $u$.
TAOCP 2.3.2 Exercise 8
Let us reformulate the ordering of Exercise `2.
TAOCP 2.3.2 Exercise 9
Let $F$ be a forest containing $t$ trees.
TAOCP 2.3.2 Exercise 10
Let $F$ and $F'$ be forests whose nodes in preorder are $u_1, u_2, \dots, u_n$ and $u'_1, u'_2, \dots, u'_{n'}$, respectively.
TAOCP 2.3.2 Exercise 11
We are asked to draw trees analogous to those in `(7)` corresponding to the formula y = e^{-x^2}.
TAOCP 2.3.2 Exercise 12
We are asked to **give specifications for the routine `DIFF[8]`**, which handles differentiation of expressions of the form $u \uparrow v$ (exponentiation) in the context of the differentiation algori...
TAOCP 2.3.2 Exercise 13
The previous solution does not address the exercise.
TAOCP 2.3.2 Exercise 14
Exercise 14 asks for the running time of the `COPY` subroutine of Exercise 13.
TAOCP 2.3.2 Exercise 15
The routine `DIV` computes the derivative of a formula of the form $u / v$ with respect to the variable $x$, according to rule `(18)`: D(u/v) = D(u)/v - (u \times D(v))/(v \uparrow 2).
TAOCP 2.3.2 Exercise 16
Exercise `12` specifies `DIFF[8]` for exponentiation, corresponding to rule `(19)`: D(u \uparrow v) = D(u) \times \bigl(v \times (u \uparrow (v - 1))\bigr) +
TAOCP 2.3.2 Exercise 17
The exercise asks for a program that performs algebraic simplification on the tree representation of formulas described in Section 2.
TAOCP 2.3.2 Exercise 18
Let the nodes be numbered $1,2,\ldots,n$ in their location order.
TAOCP 2.3.2 Exercise 19
Let $R(X,Y)$ denote the statement X \succeq Y.
TAOCP 2.3.2 Exercise 20
Let $F$ be a forest and let $u, v$ be nodes in $F$.