TAOCP 6.2.1: Searching an Ordered Table
Section 6.2.1 exercises: 29/29 solved.
Section 6.2.1. Searching an Ordered Table
Exercises from TAOCP Volume 3 Section 6.2.1: 29/29 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | [21] | medium | verified | 2m30s |
| 2 | [22] | medium | solved | 4m17s |
| 3 | [15] | simple | verified | 1m03s |
| 5 | [M24] | math-medium | verified | 2m29s |
| 6 | [28] | hard | solved | 4m41s |
| 7 | [M22] | math-medium | verified | 3m04s |
| 8 | [M20] | math-medium | solved | 4m15s |
| 9 | [20] | medium | verified | 1m21s |
| 10 | [21] | medium | solved | 4m15s |
| 11 | [M26] | math-hard | solved | 2m44s |
| 12 | [20] | medium | verified | 1m42s |
| 13 | [M24] | math-medium | solved | 4m33s |
| 14 | [21] | medium | verified | 1m23s |
| 15 | [M19] | math-medium | verified | 1m36s |
| 16 | [21] | medium | solved | 1m58s |
| 17 | [M21] | math-medium | solved | 5m13s |
| 18 | [M30] | math-hard | solved | 4m18s |
| 19 | [M42] | math-project | solved | 4m29s |
| 20 | [M22] | math-medium | verified | 1m17s |
| 21 | [20] | medium | solved | 4m10s |
| 22 | [M41] | math-project | solved | 4m46s |
| 23 | [25] | medium | solved | 5m08s |
| 24 | [23] | medium | verified | 4m11s |
| 25 | [M25] | math-medium | verified | 1m42s |
| 26 | [22] | medium | solved | 3m47s |
| 27 | [M30] | math-hard | verified | 4m15s |
| 28 | [M23] | math-medium | solved | 2m42s |
| 29 | [22] | medium | solved | 2m49s |
| 30 | [27] | hard | solved | 5m10s |
TAOCP 6.2.1 Exercise 1
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$.
TAOCP 6.2.1 Exercise 2
We analyze the modified versions of Algorithm B under the assumption that the table is sorted strictly increasing, k_1 < k_2 < \cdots < k_n, and that the key $K$ is present, with unique index $p$ such...
TAOCP 6.2.1 Exercise 3
The statement “What searching method corresponds to the tree ?
TAOCP 6.2.1 Exercise 5
We restart from the correct inequality and determine the full integer solution set carefully.
TAOCP 6.2.1 Exercise 6
We consider successful search in a sorted table of size $N$, with all keys equally likely.
TAOCP 6.2.1 Exercise 7
The flaw in the previous solution is that it replaces Algorithm U’s interval invariant with a “reachability” heuristic.
TAOCP 6.2.1 Exercise 8
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.
TAOCP 6.2.1 Exercise 9
Let Algorithm B denote the standard binary search of Section 6.
TAOCP 6.2.1 Exercise 10
We restart from the definition of Algorithm C as the binary search procedure on an ordered table $A[1],\dots,A[N]$, using repeated halving of the interval of possible locations of the search key $K$.
TAOCP 6.2.1 Exercise 11
We restart from the actual structure of Program C and compute the averages directly from the frequency model, without introducing non-uniform quantities as constants.
TAOCP 6.2.1 Exercise 12
Let $N=12$.
TAOCP 6.2.1 Exercise 13
Shar’s method in this exercise is the standard binary search method on an ordered table.
TAOCP 6.2.1 Exercise 14
Let $N>1$ be arbitrary.
TAOCP 6.2.1 Exercise 15
Let $T_k$ denote the Fibonacci tree of order $k$.
TAOCP 6.2.1 Exercise 16
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...
TAOCP 6.2.1 Exercise 17
Let the Fibonacci tree of order $k$ be defined as usual: a node of order $t$ has a left child of order $t-1$ and a right child of order $t-2$.
TAOCP 6.2.1 Exercise 18
The reviewer is correct that the previous solution replaced Program F’s frequency model with an unjustified uniform-visitation assumption.
TAOCP 6.2.1 Exercise 19
We restart the analysis from the structure actually used in Algorithm F (as modified in Exercise 14): a Fibonacci tree representation where the search space consists of all internal and external nodes...
TAOCP 6.2.1 Exercise 20
Let $C(N)=\log_b N$ for a constant $b>1$ to be determined.
TAOCP 6.2.1 Exercise 21
Let the keys be K_1<K_2<\cdots<K_{10}, and let the unsuccessful-search intervals (gaps) be
TAOCP 6.2.1 Exercise 22
We reconstruct the argument in a fully standard comparison-model framework and remove all heuristic claims.
TAOCP 6.2.1 Exercise 23
Let the given search algorithm be represented by a finite decision tree $T$.
TAOCP 6.2.1 Exercise 24
We construct a correct solution directly from the complete binary tree representation, without relying on any claim about equivalence with ordinary binary search.
TAOCP 6.2.1 Exercise 25
Let $a_k$ and $b_k$ denote the numbers of internal and external nodes on level $k$, respectively.
TAOCP 6.2.1 Exercise 26
A correct proof must specify an invariant state of the polyphase algorithm and show that this invariant is exactly the Fibonacci decomposition encoded by Fibonacci trees.
TAOCP 6.2.1 Exercise 27
The error in the previous solution is not cosmetic.
TAOCP 6.2.1 Exercise 28
Let $T_0(x)=x*x$, $T_1(x)=x$, and for $n \ge 0$, T_{n+2}(x)=T_{n+1}(x) * T_n(x).
TAOCP 6.2.1 Exercise 29
Let $A_i = K_i$.
TAOCP 6.2.1 Exercise 30
The previous solution fails because it leaves the comparison model (all information must be in the relative order of the $N$ keys) and because it never constructs a single coherent global ordering tha...