brain

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

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

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

No.

The preorder successor is characterized as follows.

Algorithm `T` uses an auxiliary stack `A` in consecutive memory locations.

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.

We are asked to give an algorithm analogous to Algorithm `S` that determines the preorder successor `P*` of a node `P` in a threaded binary tree with a list head as in `(8), (9), (10)`.

Let a node $P$ of a threaded binary tree be given.

The double-order traversal visits each node twice.

Let `P` point to a node of a binary tree, and consider `Q = P*`, the successor of `NODE(P)` in preorder.

In the representation (2), each node contains exactly two links, `LLINK` and `RLINK`.

We aim to construct an algorithm analogous to Algorithm `T` that traverses a binary tree in _preorder_, visiting each node exactly once, and then prove its correctness by induction on the number of no...

A postorder traversal must process a node only after both of its subtrees have been traversed.

Let $B_n$ denote the number of binary trees with $n$ nodes.

Let the nodes of a binary tree be distinct.

The stack grows only in step `T3`, where the current value of `P` is pushed onto `A` and then `P` is replaced by `LLINK(P)`.

Let a binary tree with `n` nodes be traversed using Algorithm `T`.

Let a binary tree have $n$ nodes, with preorder sequence u_1 u_2 \dots u_n and inorder sequence

Let the representation of a node be the binary string $\alpha$, where the root is represented by `"1"`, the left child of $\alpha$ is $\alpha0$, and the right child is $\alpha1$.

Let the preorder of the binary tree be $u_1 u_2 \dots u_n$ and the inorder be $v_1 v_2 \dots v_n$.

Let us define the new traversal order recursively, as in the exercise: 1.

[Section 2.

Let `T` denote the root of the binary tree in the figure.

The statement claims that "The terminal nodes of a binary tree occur in the same relative position in preorder, inorder, and postorder.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

In a conventional tree diagram with the root drawn at the top, each node at level $k+1$ is placed below its parent at level $k$.

[Section 2.

Proceed by induction on the number of nodes in the tree.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

Circular lists are used in Fig.

We reorganize the personnel table so that every attribute list is an **inverted list sorted by a single fixed total order on persons**, for example by a unique person index $1,2,\dots,n$.

[Section 2.

Each of the $200$ rows contains at most $4$ nonzero entries, so the total number of nonzero matrix elements stored as nodes is at most 200 \cdot 4 = 800.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

[Section 2.

The lexicographic order used for $0 \le k \le j \le n$ is unchanged when the index set is shifted to $1 \le k \le j \le n$; only the origin of the indexing changes.

[Section 2.

The simulation program maintains two principal dynamic structures, `QUEUE[IN]` and `ELEVATOR`, in which individual users are inserted and later removed according to events generated by the coroutines.

Define new indices $I'_r = I_r - l_r$ for $1 \le r \le k$.

We are given a permutation of size $n$, and we need to consider every contiguous subarray. For each subarray, we take its elements and replace them with their relative ranks inside that subarray.

Let each node of $A$ occupy two consecutive memory words and suppose lexicographic (row-major) order is used.

Step `E8` is the action that occurs after the elevator has moved one floor in its current direction.

For each floor $j$, record the behavior of the elevator under the following circumstances: 1.

The `DECISION` subroutine is called whenever the elevator is in a dormant condition and a new request may require a change of state.

Let $V[1], \dots, V[n]$ be the variables of the system, and let a step of the simulation specify a small subset of these variables to be updated simultaneously.

The statement `JANZ CYCLE` at line 154 was intended to skip the "give up" activity `U4` for a user if the elevator had already arrived at the user's floor.

The desired change is that a user waiting on floor `IN` should enter the elevator only if the elevator is accepting passengers whose desired direction agrees with the user's destination.

The scenario given concerns the discrete simulation of the Caltech Mathematics building elevator, using the routines described in Section 2.

Activity `E9` in the elevator coroutine is a scheduled action that occurs after the completion of certain steps in the elevator's operation, specifically following step `E6` (door-closing and possible...

In representation (1) of a doubly linked list, there are distinguished variables `LEFT` and `RIGHT` giving the locations of the leftmost and rightmost nodes, respectively.

To demonstrate that the elevator system requires three independent binary variables per floor, we must exhibit sequences of button presses that show each variable can be set or cleared independently o...

A deque requires efficient insertion and deletion at both ends.

Each node $x_i$ stores a single link field $\mathrm{LINK}(x_i)$ defined as the exclusive-or of the addresses of its two neighbors in the circular order.

We are asked to design an efficient algorithm to "erase" an entire circular list by placing all its nodes onto the `AVAIL` stack.

Let a polynomial be represented as in Section 2.

Let $p$ denote the number of nonzero terms in $P$, $m$ the number of nonzero terms in $M$, and $q$ the number of nonzero terms in the initial polynomial stored in $Q$.

Let $P$ contain $n$ nonzero terms, and let $\operatorname{polynomial}(Q)=0$.

Let $P$ denote the pointer value initially in $rI1$, which points to a node of a circular list representation of a polynomial.

A polynomial equal to $0$ is represented by a single special node, called the terminating node, whose fields satisfy $\mathrm{COEF} = 0$ and $\mathrm{ABC} = -1$, and whose link field points to itself...

Algorithm `A` does **not** work properly when `P = Q`.

We wish to adapt Algorithms `A` (addition) and `M` (multiplication) for polynomials in a single variable $x$, allowing exponents up to $b^3 - 1$.

We are asked to create a subroutine `COPY` that produces a complete duplicate of a given polynomial represented as a circularly linked list with a sentinel node, preserving the original list and retur...

The list representation used in Algorithm $A$ is singly linked, so the link field of a node gives access only to its successor.

The previous solution used a linear NIL-terminated list, but in TAOCP Section 2.

The decreasing order of the `ABC` fields makes it possible to compare the current terms of two polynomials and determine immediately whether the exponents are equal, or whether one polynomial contains...