brain

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

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

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

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

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

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

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

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

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

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

False.

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

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

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

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.

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

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.

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

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

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

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

[Section 2.

In Fig.

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

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

[Section 2.

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

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

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

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

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

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

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

Algorithm `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**.

[Section 2.

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.

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

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 the nodes be numbered $1,2,\ldots,n$ in their location order.

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

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

[Section 2.

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

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 $F$ be a forest containing $t$ trees.

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

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

Let us reformulate the ordering of Exercise `2.

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 $(S, \prec)$ be a well-ordered set.

Let a binary tree have $n$ nodes.

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

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

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

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

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 $D(T)$ denote the double-order sequence of a binary tree $T$, as defined in exercise 18.

[Section 2.

[Section 2.

We first interpret the definition of $\preceq$ as a recursive lexicographic comparison of trees: the empty tree precedes every tree; among nonempty trees, the roots are compared first; if the roots ag...

No.

A _right-threaded_ binary tree contains ordinary left links and either ordinary right links or right threads.

We are asked to write a MIX program that implements the algorithm of Exercise 21, which traverses an unthreaded binary tree in inorder _without using any auxiliary stack_, modifying the `LLINK` and `R...

We employ the _threading during traversal_ method, also known as the _Morris traversal_, which creates temporary links to predecessors during the traversal to avoid using a stack.

The preorder successor is characterized as follows.