TAOCP 6.3: Digital Searching
Section 6.3 exercises: 40/40 solved.
Section 6.3. Digital Searching
Exercises from TAOCP Volume 3 Section 6.3: 40/40 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [00] | immediate | solved | 4m |
| 2 | [20] | medium | solved | 3m25s |
| 3 | [21] | medium | verified | 1m40s |
| 6 | [15] | simple | solved | 4m02s |
| 8 | [20] | medium | verified | 1m19s |
| 9 | [21] | medium | solved | 2m44s |
| 10 | [23] | medium | verified | 1m28s |
| 11 | [21] | medium | verified | 1m38s |
| 12 | [25] | medium | verified | 2m04s |
| 13 | [20] | medium | verified | 3m02s |
| 15 | [28] | hard | verified | 4m43s |
| 16 | [22] | medium | verified | 1m07s |
| 17 | [M25] | math-medium | solved | 4m59s |
| 18 | [M21] | math-medium | verified | 3m03s |
| 19 | [HM23] | hm-medium | solved | 3m31s |
| 20 | [M30] | math-hard | solved | 4m53s |
| 21 | [M25] | math-medium | verified | 1m42s |
| 22 | [M25] | math-medium | verified | 2m29s |
| 23 | [M26] | math-hard | verified | 1m23s |
| 24 | [M30] | math-hard | solved | 5m51s |
| 25 | [M24] | math-medium | solved | 4m46s |
| 26 | [23] | medium | verified | 3m40s |
| 27 | [HM31] | hm-hard | verified | 1m30s |
| 28 | [HM26] | hm-hard | solved | 4m54s |
| 29 | [HM40] | hm-project | solved | 6m13s |
| 30 | [M24] | math-medium | verified | 4m07s |
| 31 | [M21] | math-medium | solved | 4m43s |
| 32 | [M21] | math-medium | solved | 1m50s |
| 33 | [M30] | math-hard | verified | 4m37s |
| 34 | [HM40] | hm-project | solved | 4m41s |
| 36 | [M25] | math-medium | solved | 5m42s |
| 37 | [M22] | math-medium | solved | 5m53s |
| 38 | [M40] | math-project | solved | 4m50s |
| 39 | [M43] | math-project | verified | 4m28s |
| 40 | [25] | medium | solved | 4m58s |
| 41 | [HM28] | hm-hard | solved | 4m43s |
| 42 | [23] | medium | solved | 1m37s |
| 43 | [HM42] | hm-project | solved | 5m33s |
| 44 | [30] | hard | verified | 1m41s |
| 45 | [M25] | math-medium | verified | 1m24s |
TAOCP 6.3 Exercise 1
In a tree, leaves are nodes with no descendants.
TAOCP 6.3 Exercise 2
Let $K$ be the search argument, and assume it is represented as a sequence of characters ending with the blank symbol used in Algorithm T.
TAOCP 6.3 Exercise 3
Let each key $x$ in the set of 31 words have frequency $f(x)$ as given by Fig.
TAOCP 6.3 Exercise 6
Algorithm D inserts keys one at a time.
TAOCP 6.3 Exercise 8
Algorithm D maintains two variables during a descent in a digital search tree: $K$, the working copy of the search argument whose leading digit (or bit) determines the branching, and $K'$, a preserved...
TAOCP 6.3 Exercise 9
The original attempt fails mainly because it mixes abstract register notation with MIX conventions and omits the actual pointer manipulation required by Algorithm D.
TAOCP 6.3 Exercise 10
Let the keys be $n$-bit binary numbers.
TAOCP 6.3 Exercise 11
Algorithm 6.
TAOCP 6.3 Exercise 12
Let $T_n$ be a digital search tree constructed by Algorithm D from $n$ keys $K_1,\dots,K_n$, where the keys are independent infinite binary sequences with each bit independently $0$ or $1$ with probab...
TAOCP 6.3 Exercise 13
Let each key be a digit string over an alphabet of size $M$, K = k_1 k_2 \dots k_\ell, \qquad 0 \le k_i < M.
TAOCP 6.3 Exercise 15
The flaw in the previous argument is real: the insertion point cannot depend on the unknown divergence index $d$, so any attempt to define it during the initial search is circular.
TAOCP 6.3 Exercise 16
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...
TAOCP 6.3 Exercise 17
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 .
TAOCP 6.3 Exercise 18
Let the coupled recurrences (4) and (5) be written in vector form as \mathbf{z}_n = \begin{pmatrix} x_n\\ y_n
TAOCP 6.3 Exercise 19
The expression in the prompt is clearly truncated, but the surviving fragment “$k>2$” together with the parameters $s>0$, $m>1$, and the cross-reference to Exercise 5.
TAOCP 6.3 Exercise 20
We correct the analysis by keeping the Poissonized occupancy framework but fixing the asymptotic accuracy statements and making the sequential-search contribution explicit.
TAOCP 6.3 Exercise 21
Let $M \ge 2$ and consider a random $M$-ary trie built from $N$ keys, where each digit of each key is independently uniformly distributed in ${0,1,\dots,M-1}$.
TAOCP 6.3 Exercise 22
Let $X_l$ denote the number of trie nodes on level $l$ in a random $M$-ary trie containing $N$ keys.
TAOCP 6.3 Exercise 23
Let $N$ keys be stored in an $M$-ary trie under the uniform random model in which each digit of each key is independently uniformly distributed in ${0,1,\dots,M-1}$.
TAOCP 6.3 Exercise 24
The error in the previous solution is not a minor combinatorial slip.
TAOCP 6.3 Exercise 25
We now give a fully corrected TAOCP-style solution, aligning directly with recurrence (4) for $A_N$ and definition (5) for $C_N$, and avoiding heuristic arguments.
TAOCP 6.3 Exercise 26
The product is interpreted as P=\left(1-\frac{1}{5}\right)\prod_{k\ge 1}\left(1-\frac{1}{3^k}\right).
TAOCP 6.3 Exercise 27
Let $C_N$ denote the quantity defined in equation (14) of Section 6.
TAOCP 6.3 Exercise 28
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$.
TAOCP 6.3 Exercise 29
The previous argument failed because it replaced the actual recursive structure of a digital search tree by an unjustified occupancy limit.
TAOCP 6.3 Exercise 30
We restart from the actual structure of the defining equation (15) and avoid introducing any artificial kernel.
TAOCP 6.3 Exercise 31
Let $A_n$ be the expected cost of an $M$-ary digital search tree built from $n$ random keys, and let $P(z)$ be its Poisson transform.
TAOCP 6.3 Exercise 32
Let keys be infinite binary sequences generated by independent unbiased bits.
TAOCP 6.3 Exercise 33
Let (17) be written in its full binomial-convolution form as it appears in Section 6.
TAOCP 6.3 Exercise 34
The previous solution fails because it invents structure and singularities instead of deriving them from the actual expression in (18).
TAOCP 6.3 Exercise 36
We correct both parts, addressing the missing rigor in Algorithm D and completely rebuilding the Patricia argument using a valid global construction.
TAOCP 6.3 Exercise 37
Let $b_j$ be the number of external nodes at level $j$.
TAOCP 6.3 Exercise 38
The error in the previous solution is structural: it used an incorrect recurrence for the modified external path length and then built an unnecessary vector-valued dynamic program on top of it.
TAOCP 6.3 Exercise 39
We construct a fully rigorous solution by cleanly separating the structural lemma from the contraction argument, avoiding informal swapping arguments.
TAOCP 6.3 Exercise 40
The failure of the original solution is the artificial reduction to a fixed window $t_0,\dots,t_{2N-1}$.
TAOCP 6.3 Exercise 41
We rewrite the argument so that the missing link between the Nielsen condition and _prefix-deterministic behavior in the original free-group alphabet_ is made explicit.
TAOCP 6.3 Exercise 42
Let $K_1, K_2, \dots, K_r$ be the binary keys, each a finite string over ${0,1}$, and let $T$ be the binary trie formed by these keys.
TAOCP 6.3 Exercise 43
Working