brain

We analyze a 2–3 tree built by inserting a random permutation of $n$ distinct keys, using the standard top-down insertion algorithm with node splitting.

Let $M$ be the number of hash addresses and let $n$ be the number of occupied cells at the moment a new key $K$ is inserted by Algorithm C.

**Exercise 5.

We work in the setting of Algorithm C, where each key $x$ is inserted into a singly linked chain for bucket $h(x)$ by _inserting at the head_.

Let the sequence maintained by the Garsia–Wachs algorithm be $L = (l_1, l_2, \dots, l_m)$ in symmetric order.

**Corrected Solution to Exercise 5.

The reviewer is correct: the proposed solution does not address the problem at all.

The error in the proposed solution occurs at the change of variables and the resulting failure to preserve the structure needed for an incomplete gamma representation.

Let $T$ be a full binary tree with $n$ leaves, and let $D(T)$ and $E(T)$ be the two weighted path functionals defined in Section 5.

We construct a deterministic comparison algorithm and verify a uniform worst-case bound of $6$ comparisons.

We restart from the definition of the objective and avoid assuming any unverified identity between $E(T)$ and $D(T)$.

The issue is not merely tree degeneracy at $P=2$, but the fact that Algorithm R implicitly assumes the existence of at least one comparison.

The previous solution fails because it replaces MIX instruction semantics with an unsupported linear model and ignores control flow.

Let the hash table contain $M$ locations and let $N$ be the number of keys currently stored.

The proof of Theorem K is carried out by verifying that a proposed closed form agrees with the values of the adversary functions $_M(m,n)$ defined by the recurrence inequalities coming from Strategies...

Let $m=101$.

A B-tree can be adapted to support retrieval by position in a linear list by augmenting each node with information about subtree sizes, so that navigation is driven by rank rather than key comparison.

Let a fixed permutation of the records be given, and let $\pi(i)\in{1,\dots,N}$ denote the position of record $R_i$ in the array.

We restart from the correct structural interpretation of $S'(k)$ as an optimal **merging-based sorting cost**, and we avoid assuming any fixed decomposition into prescribed sizes.

Let $R_1, R_2, \dots, R_N$ be a table of records with corresponding keys $K_1, K_2, \dots, K_N$.

Let the radix be $M$ and let keys be written as $(a_1,a_2,\dots,a_p)$ with digits $0 \le a_i < M$.

Let the Fibonacci rabbit model be the standard one: a single initial pair is present at month $0$; every pair produces exactly one new pair in each month starting from its second month of life; no pai...

A multireel file consists of a finite sequence of reels, each reel being a sequential medium on which records are read and written in forward order, with a forced change of reel when an end is reached...

Let $M(m,n)$ denote the minimum number of comparisons required to merge two increasing sequences of lengths $m$ and $n$.

The previous solution fails because it tries to reduce structural equality of binary search trees to inorder equality and informal “locality” arguments.

Let $T=5$ and hence $P=4$.

Let $I_n$ denote the internal path length of the random BST built from $n$ keys.

Let $P$ be the tableau corresponding to a permutation $a_1 a_2 \dots a_m$.

We restart from a correct decision-tree formulation and remove the unverified state model.

For each entry $a_i$ of the permutation, let $t_i$ be the class defined in the text.

Let $T_N$ be the Coffman–Eve $M$-ary digital search tree built from $N$ independent random infinite strings over an alphabet of size $M>2$.

Let $S$ be the total number of runs in the file.

Let Algorithm L be the straight two-way merge sort in which the initial step L1 sets the system so that every record $R_i$ forms a run of length $1$, and later steps repeatedly merge runs of fixed siz...

Let $I(T)$ denote the internal path length of a tree $T$, defined as the sum of the depths of all internal nodes of $T$, where the root has depth $0$ and each child increases depth by $1$.

We give a clean decision-tree argument that avoids the gap in the previous solution and directly relates worst-case depths.

Patricia trees represent a set of strings by a compressed trie in which each branching decision is determined by inspecting selected character positions, and in which nodes are arranged so that every...

Let the input to the merge network be two sorted sequences of lengths $m=3$ and $n=5$: (x_1,x_2,x_3) \quad \text{and} \quad (y_1,y_2,y_3,y_4,y_5).

From the definition in (3), the procedures `SORTOO`, `SORT11`, `SORT01`, and `SORT10` differ only by a swap of tape roles.

Let $n$ be the total number of distinct elements.

Let the search tree be built by inserting keys in the order $K_1, K_2, \dots, K_n$, where the access probabilities satisfy $p_1 > p_2 > \cdots > p_n.$ The structure of Algorithm $T$ depends only on ke...

Let $a_1,\dots,a_n$ be the preferred parking positions, where each $a_j \in {1,\dots,n}$ and $n=m$.

The error in the previous solution is the assumption that column-wise uniformity of the permutations implies optimality of all coefficients $c_k$.

Let $B$ denote the binomial transform operator acting on sequences $x = (x_n)_{n \ge 0}$ by (Bx)_n = \sum_{k=0}^{n} \binom{n}{k} x_k .

Let $H(m,n)$ denote the number of comparisons performed by Hwang and Lin’s binary merging algorithm when merging $A_1<\cdots<A_m$ with $B_1<\cdots<B_n$ under worst-case behavior.

Let the original order-$P$ bubble sort be defined as in Section 5.

The previous solution fails because it never uses the actual cascade operator.

Assume an open addressing scheme using Algorithm L or Algorithm D.

The key issue is the conditioning of the truncation point.

The proposed interchange is not valid in general, because it violates a dependency in the control flow of Program C.

The failure in the previous solution is the incorrect introduction of an inhomogeneous “deviation dynamics.

Let $d$ be fixed.

We restart the argument from the correct structural relationship between comparison trees and comparison–exchange trees, and avoid any “locking” interpretation of swaps.

Let $Q$ be the node selected for deletion, chosen uniformly from the $N$ nodes of a binary search tree formed by random insertion of $N$ keys.

Let $a_k$ and $b_k$ denote the numbers of internal and external nodes on level $k$, respectively.

Let $l$ and $u$ be the current indices in Algorithm B (binary search on a sorted table $K_1 < \cdots < K_n$), with sentinels $K_0 = -\infty$ and $K_{n+1} = +\infty$.

The original argument fails because it never establishes a real comparison between the two quantities $M(k+m,n)$ and $M(k,n)+M(m,n)$.

The original argument fails because it assumes a uniform “shift” of depths along the entire search path from $x$ to the chosen replacement node.

Algorithm F forecasts the next input operation by examining the last records currently present in the active buffers.

Let $T_n$ denote the set of binary search trees on $n$ distinct keys, and consider the Markov process in which at each step an insertion of a random key and a deletion of a uniformly chosen node are p...

Let the hash table have $M$ locations.

Let the 31 keys be the most common English words in Fig.

The key fix is to discard the incorrect “uniform random cycle” model and replace it with a correct symmetry argument for double hashing: the probe sequence is not uniform over all permutations, but it...

Let $T$ be the binary search tree shown in Fig.

We correct the proof by replacing the invalid greedy lemma with a precise structural argument based on inorder intervals.

Let $r$ denote the current odd integer under consideration and let $H$ be a priority queue keyed by the first unprocessed odd composite associated with each prime.

In Case 2 the symmetric order of the keys is determined by the in-order sequence of the subtrees: all keys in the left subtree of $A$ precede $\text{KEY}(A)$, all keys in the left subtree of $B$ that...

The previous solution failed because it replaced the combinatorial snowplow construction with an ungrounded probabilistic model and used undefined parameter substitutions.

The original attempt fails mainly because it mixes abstract register notation with MIX conventions and omits the actual pointer manipulation required by Algorithm D.

The previous solution fails because it attempts to repair the situation by adding an external phase.

Let $x = a_i$ and $y = a_j$ with $i < j$ and $x > y$.

Algorithm R and radix exchange sorting both exploit the representation of keys as digit sequences and avoid direct key-to-key comparison.

The odd-even merge network is composed of two independent recursive merge networks, one acting on the odd subsequences and one acting on the even subsequences, followed by a single layer of comparison...

Working

Let $S$ be the root of a balanced binary tree in the sense of Section 6.

Algorithm R initializes the selection tree by filling all external nodes with the next input records.

Let each initial run $i$ have weight $w_i$.

The reviewer is correct that the previous response never engages with the actual mathematical content of equations (8), (9), and (10).

At initialization $i \leftarrow 1$.

The previous solution fails because it treats the problem as one of extracting information from a fixed probabilistic comparison outcome, whereas the task is a deterministic decision problem in the co...

Let \Delta[j]=\left\lfloor \frac{N+2^{j-1}}{2^j}\right\rfloor,\qquad 1\le j\le k,\quad k=\lfloor \lg N\rfloor+2.

Equation (39) expresses the probability that $N$ distinct keys $K_1,\dots,K_N$ hash into $N$ distinct table positions when each key is assumed to be mapped independently and uniformly into a hash tabl...

The error in the previous solution occurs at exactly one decisive point: the computation of m_k=\left\lfloor \frac{r_k}{2}\right\rfloor from the binary expansion of $N$.

Let the $P$ runs be $R_1,\dots,R_P$.

Let a 2-3 tree be defined as in Section 6.

Let a rooted ordered tree $T$ have $n$ leaves.

In step D3, Program D performs three actions before any comparison outcome is known: it sets $i = j - h$, it loads $K = K_j$, and it loads $R = R_j$.

Let $T_n$ be a binary search tree formed by inserting $n$ distinct keys in random order, each of the $n!$ permutations equally likely, using Algorithm T of Section 6.

Let $P$ be a pointer to a record, with $FIRST$ pointing to the first record and the last record linked to the sentinel $A$.

The previous solution fails because it treats the weight data as missing.

Let $N$ denote the number of items stored.

A 2-3 tree is a rooted ordered tree in which every internal node has either two or three children and contains respectively one or two keys, and in which all external nodes occur at the same level.

Let $H$ be a matrix with $R$ rows and one column for every possible key $K$.

Let $T$ denote the balanced tree of Fig.

Let $X_M$ denote the number of probes required for an unsuccessful search in a linear probing table of size $M$ containing $N$ stored keys.

Let $S_M$ be the set of all permutations of $\{0,1,\dots,M-1\}$, and let $\mathbb{P}$ be a probability assignment on $S_M$ that is equivalent to uniform probing in the sense of Theorem U.

Start from the definition at the end of step D4: D[j] = a + A[j] - A[j+1], \qquad 1 \le j \le T, with $A[T+1]=0$.

Let the keys be $K_y, K_0, K_1, \dots, K_n$ with $K_y < K_0 < K_1 < \cdots < K_n.$ At every stage, Algorithm A inserts the new key as a leaf in the rightmost position of the current tree, since each n...

**Exercise 5.

Let $p_{ij} = \Pr(X = x_i, Y = y_j)$, $p_i = \Pr(X = x_i) = \sum_j p_{ij}$, and $q_j = \Pr(Y = y_j) = \sum_i p_{ij}$.

The previous solution failed because it tried to _postulate_ a kernel and then retrofit a “memoryless explanation” instead of deriving the joint law from the actual state evolution at the instants whe...