TAOCP 6.5: Retrieval on Secondary Keys
Section 6.5 exercises: 20/20 solved.
Section 6.5. Retrieval on Secondary Keys
Exercises from TAOCP Volume 3 Section 6.5: 20/20 solved.
| # | Rating | Category | Status | Time |
|---|---|---|---|---|
| 1 | ▶ [M27] | math-hard | solved | 15m57s |
| 2 | [M25] | math-medium | solved | 5m25s |
| 3 | [19] | medium | solved | 3m30s |
| 4 | [M30] | math-hard | verified | 3m46s |
| 5 | [40] | project | verified | 55s |
| 6 | ▶ [M20] | math-medium | solved | 1m51s |
| 7 | [M24] | math-medium | solved | 3m59s |
| 8 | [M32] | math-hard | solved | 4m26s |
| 9 | [M20] | math-medium | verified | 1m24s |
| 10 | [M32] | math-hard | solved | 1m09s |
| 11 | [M25] | math-medium | verified | 1m08s |
| 12 | [M23] | math-medium | solved | 4m56s |
| 13 | [M25] | math-medium | verified | 2m25s |
| 14 | [28] | hard | solved | 3m35s |
| 15 | [HM30] | hm-hard | solved | 4m36s |
| 16 | ▶ [25] | medium | verified | 2m31s |
| 17 | ▶ [M30] | math-hard | solved | 24m33s |
| 18 | ▶ [M35] | math-hard | solved | 19m53s |
| 19 | [M22] | math-medium | verified | 3m54s |
| 20 | [M47] | math-research | solved | 9m38s |
TAOCP 6.5 Exercise 1
Let $0 \le k \le n/2$.
TAOCP 6.5 Exercise 2
Let the eight records be identified with binary triples 000,001,010,011,100,101,110,111.
TAOCP 6.5 Exercise 3
The previous attempt failed because it replaced the signature analysis required by Table 2 with informal guesses.
TAOCP 6.5 Exercise 4
We restart from a correct event decomposition and avoid any use of the flawed distribution of $Q$.
TAOCP 6.5 Exercise 5
Let a composite file consist of two disjoint bit fields of lengths $m_1$ and $m_2$, so that $m = m_1 + m_2$.
TAOCP 6.5 Exercise 6
We consider a composite hash function on an \((m_1+m_2)\)-bit field.
TAOCP 6.5 Exercise 7
The fundamental issue in the proposed solution is not computational but logical: it replaces the given combinatorial specification with an invented complete function.
TAOCP 6.5 Exercise 8
A correct solution requires fixing the structural error in the treatment of the interaction between $S_0$ and $S_1$, and then proving that the minimizer has enough regularity (lexicographic initial se...
TAOCP 6.5 Exercise 9
Let the point set be $V = {0,1,2}^n$.
TAOCP 6.5 Exercise 10
Let a Kirkman triple system of order $v$ consist of $v+1$ objects $\{x_0,x_1,\dots,x_v\}$ and a family of triples such that every unordered pair of distinct objects occurs in exactly one triple, excep...
TAOCP 6.5 Exercise 11
A complemented triple system of order $v$ can be reformulated as a decomposition of the edge set of a graph on $2v$ vertices into triples (triangles) with the following structure.
TAOCP 6.5 Exercise 12
Let $X=\{x_i,\bar x_i\mid i\in\mathbb Z_7\}$.
TAOCP 6.5 Exercise 13
Let $m = 2n$ and let $V = \mathbb{F}_2^m$, so $|V| = 2^m = 4^n$.
TAOCP 6.5 Exercise 14
The three structures all support dynamic sets of points in the plane, but they differ in what is structurally invariant.
TAOCP 6.5 Exercise 15
The original proof fails because it attempts to collapse the search to a single decoded bucket.
TAOCP 6.5 Exercise 16
Let $(V,\mathcal{B})$ be a Steiner triple system of order $v$, so each block $B \in \mathcal{B}$ has $|B|=3$ and every 2-element subset of $V$ lies in exactly one block.
TAOCP 6.5 Exercise 17
We need to solve exercise 17 from section 6.
TAOCP 6.5 Exercise 18
An ABD$(m,n)$ is a set of $2^n$ rows, each an $m$-tuple over $\{0,1,*\}$ with exactly $m-n$ asterisks, satisfying: 1.