brain

Let the extended $t$-ary tree contain $n$ circular (internal) nodes and $s$ square (external) nodes.

Let $T$ be a binary tree with left subtree $T_L$ and right subtree $T_R$.

For an extended binary tree, each external node corresponds to a unique path from the root, and thus to a binary string of length $l_j$ in which each left edge is encoded by $0$ and each right edge by...

Let $T$ be a binary tree with $n=12$ internal nodes and minimal internal path length $I$.

Each configuration counted by $r(n,q)$ consists of a directed acyclic graph on ${1,2,\ldots,n}$ in which every designated vertex has outdegree $1$ and every nondesignated vertex has outdegree $0$, wit...

The $( (3,2,4),(1,4,2) )$-construction in the notation of the section determines a decomposition in which the first index sequence selects the root structure at level $t=8$, while the subsequent index...

An ordered tree with $n$ vertices determines, by the correspondence in Section 2.

Let the vertices be ${1,2,\ldots,n}$ and let the oriented tree be directed toward its root $r$.

By the correspondence of equation (16), every labeled oriented tree on ${1,\ldots,n}$ corresponds uniquely to an $(n-1)$-tuple $(x_1,\ldots,x_{n-1})$, where each $x_i$ is an integer between $1$ and $n...

Let $x_1,x_2,\ldots,x_{n-1}$ be given and define $V_1,V_2,\ldots,V_n$ inductively by selecting at each stage the smallest vertex not yet chosen that does not appear in the corresponding suffix of the...

After $n-2$ deletions in the construction, exactly two vertices remain: the root and $V_{n-1}$.

Suppose the canonical representation of an oriented tree with $n$ vertices is given as the sequence $x_1,x_2,\ldots,x_{n-1}$, where $1\le x_j\le n$.

Let $G$ be the complete graph on the labeled vertices ${1,2,\ldots,n}$, and orient every edge toward the specified root, say vertex $1$.

Let the two centroids be $C_1$ and $C_2$.

Let $G(z)=\sum_{n\ge1} g_n z^n$ denote the generating function for oriented binary trees, where each vertex has in-degree $0,1,$ or $2$; equivalently, in the rooted orientation used in Section 2.

Let $C(z)=\sum_n c_n z^n$.

A program based on exercise 2 computes the coefficients $a_n$ recursively from na_{n+1}=\sum_{k=1}^{n}k\,a_k\,s_{nk}, \qquad s_{nk}=\sum_{1\le j\le n/k}a_{n+1-jk},

We have $A(z)=\sum_{n\ge1} a_n z^n$ and we seek a recurrence for $a_{n+1}$ in terms of previous $a_j$.

Assume that for every positive integer $N$ there exists a partition of ${1,2,\ldots,N}$ into $k$ sets $S_1^{(N)},\ldots,S_k^{(N)}$ such that none of the sets contains an arithmetic progression of leng...

Suppose $k$ sets $S_1,\ldots,S_k$ of positive integers cover all positive integers.

Assume, to obtain a contradiction, that there exists an infinite _bad_ sequence T_1,T_2,T_3,\ldots such that $T_j\not\subseteq T_k$ whenever $j<k$.

The given 92 tetrad types implement a hierarchical constraint system in which every $\beta$-tetrad forces $\alpha$-tetrads on both horizontal sides and $\delta$-tetrads vertically, while the internal...

For each positive integer $n$, let $T_n$ be the finite set of all legal tilings of the $n\times n$ torus by the given tetrad types, where legality means adjacency constraints hold and opposite edges m...

Yes, it is always possible.

Stopped thinking

The closure property (i) ensures that whenever a sequence $(x_1,\ldots,x_n)$ lies in $S$, its initial segment of length $0$ also lies in $S$.

Let $A=(a_{ij})$ be the transition matrix.

Each arc $e$ of the directed graph is represented by a node whose identity is $e$ itself, with fields $\text{ALINK}$, $\text{BLINK}$ and one-bit tags $\text{ATAG}$, $\text{BTAG}$.

Let $G$ be a directed graph with $n+1$ vertices $V_0,V_1,\ldots,V_n$, and let $A$ be the matrix defined in the statement of the exercise.

False.

By Exercise 16, the game is won if and only if the digraph on $V_1,\ldots,V_{13}$ determined by the bottom cards is an oriented tree.

The exercise depends essentially on the specific digraph in Fig.

For each vertex $V\ne R$, choose one oriented path from $V$ to $R$, which exists because $R$ is a root.

Let $T$ be an oriented tree with root $R$.

Let $v_0=\operatorname{init}(e_1)$ and for $1\le k\le n$ let $v_k=\operatorname{fin}(e_k)$, so $v_k=\operatorname{init}(e_{k+1})$ for $1\le k<n$ and $v_n=v_0$.

False.

Let the vertex set be ${V_1,V_2,V_3}$ and let the arc set consist of e_1: V_1 \to V_2, \qquad e_2: V_1 \to V_3.

Suppose first that the graph is connected.

Let P=(e_1,e_2,\ldots,e_n) be an oriented walk from $V$ to $V'$.

The construction extends naturally to a multigraph, where several edges may join the same pair of vertices and loops are also permitted.

The terminals $T_1,T_2,\ldots,T_n$ correspond naturally to the vertices of a graph, and the wires correspond to edges connecting pairs of vertices.

Let $e=T_{n-1}T_n$ be an edge of minimum cost among all edges incident with $T_n$, so that $c(n-1,n)=\min_{1\le i<n}c(i,n)$.

Let the original flow chart have vertex set $V$ and edge set $E$, and let the reduced chart be obtained by partitioning $V$ into disjoint blocks $V^{(1)},\ldots,V^{(r)}$ and replacing each block by a...

Let $G'$ be the chosen free subtree and let the independent variables be the values assigned to the non-tree edges $E_2,E_5,\ldots,E_{25}$, as in Eq.

The construction in this exercise depends on the exact adjacency structure of the flow chart in Fig.

Construct an adjacency representation of the graph from the pairs $(a_1,b_1),\ldots,(a_m,b_m)$, interpreting each edge $e_i$ as joining $V_{a_i}$ to $V_{b_i}$.

Let $(V_0,V_1,\ldots,V_n)$ be a walk from $V$ to $V'$.

The fundamental path from Start to Stop is the path in the free subtree determined by the cycle $C_0$ with $e_0$ omitted: e_1+e_3+e_4+e_6+e_7+e_9+e_{10}+e_{11}+e_{12}+e_{14}.

Let $G'$ be a finite free tree with $n$ vertices and $n-1$ edges, and assume Kirchhoff’s law (1) holds at every vertex with all vertex values equal to $0$, so that at each vertex the sum of $E$’s ente...

We are asked to reason about **descendant number sequences** in preorder.

In Fig.

[Section 2.

Let the forest be given in preorder sequential representation: - `INFO1[j]` contains the node information.

[Section 2.

[Section 2.

Let the given forest be represented in postorder with degrees as in representation `(9)`.

Step `A8` is reached only when Algorithm `A` has determined that the two terms currently under consideration correspond to the same power of the same variable, so that their coefficients must be combi...

The ordinary Algorithm `E` maintains a forest of equivalence classes.

[Section 2.

Associate with each root $r$ an integer $\mathrm{SIZE}(r)$ equal to the number of nodes in its tree.

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

The relation $9 \equiv 3$ serves only to place the element $9$ into the equivalence class containing $3$.

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)`.

Algorithm `2.

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.

Let the original forest contain $n$ nodes, of which $m$ are terminal.

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$.

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?

Yes.

[Section 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**.

For every pair of subformulas $(A,B)$ occurring in $X$ and $Y$, define a Boolean value T(A,B).

Represent every expression by a tree whose internal nodes are only the operators `$+$`, `$\times$`, and `$\ln$`.

Let $F$ be a forest and let $u, v$ be nodes in $F$.

Let the nodes be numbered $1,2,\ldots,n$ in their location order.

[Section 2.

Exercise 14 asks for the running time of the `COPY` subroutine of Exercise 13.

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).

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) + \bigl((\ln u) \times D(v)\bigr)\times(u \u...

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.

We are asked to draw trees analogous to those in `(7)` corresponding to the formula y = e^{-x^2}.

[Section 2.

Let us reformulate the ordering of Exercise `2.

Let $T$ be a nonempty binary tree in which every node has either $0$ or $2$ children.

Let the partial order on the nodes of a forest be defined by u < v whenever $v$ is a descendant of $u$.

Let $F$ be a forest containing $t$ trees.

We are asked to determine whether the statement > "The terminal nodes of a tree occur in the same relative position in preorder and postorder.

Let the Dewey decimal notation of a node be d_1.

[Section 2.

Let a binary tree have $n$ nodes.

Let $(S, \prec)$ be a well-ordered set.

Let $B$ be a binary tree.

Let a forest $F = (T_1, T_2, \dots, T_n)$ be given, with nodes numbered in Dewey decimal notation as in Section 2.

The fundamental concepts of traversal extend immediately.

Let `X` be the new node to insert, and `T` be a pointer to the root of the tree.

Let the right-threaded binary trees use the conventions of the section: - `LLINK(P)` is either a left child or `\Lambda`.

Algorithm `C` is intended to construct a new binary tree whose nodes contain the same information as the original tree and whose link structure is identical, regardless of whether a field represents a...

Let `T` be the pointer to the right-threaded binary tree, and let `AVAIL` be the head of the list of available nodes.

Let `T` be an unthreaded binary tree, represented in the standard form of (2), and let `P` be a pointer to a node of `T`.

Exercise 31 refers to Algorithm `I` for insertion into a right-threaded binary tree.