TAOCP 6.4: Hashing

Section 6.4 exercises: 62/62 solved.

62 items

Section 6.4. Hashing

Exercises from TAOCP Volume 3 Section 6.4: 62/62 solved.

#	Rating	Category	Status	Time
1	[20]	medium	solved	4m16s
2	[20]	medium	solved	3m58s
3	[23]	medium	solved	2m30s
4	[**]		solved	1m15s
5	[15]	simple	verified	1m20s
6	[15]	simple	solved	2m14s
7	[**]		solved	3m32s
8	[M34]	math-hard	solved	2m37s
9	[M30]	math-hard	solved	1m22s
10	[M38]	math-project	solved	6m14s
11	[16]	medium	solved	3m47s
14	[24]	medium	solved	5m15s
15	[16]	medium	verified	1m19s
16	[10]	simple	verified	1m02s
17	[15]	simple	solved	1m19s
19	[40]	project	solved	2m34s
20	[M25]	math-medium	verified	4m18s
22	[27]	hard	solved	2m58s
24	[M20]	math-medium	verified	1m05s
25	[M19]	math-medium	verified	1m09s
26	[M20]	math-medium	solved	1m10s
27	[M27]	math-hard	solved	4m11s
28	[M30]	math-hard	verified	1m22s
29	[M21]	math-medium	solved	47s
30	[M38]	math-project	solved	1m12s
41	[M40]	math-project	solved	5m05s
42	[M20]	math-medium	verified	1m21s
43	[**]		solved	1m06s
44	[M43]	math-project	solved	5m06s
45	[M43]	math-project	verified	4m25s
46	[M42]	math-project	solved	4m55s
47	[M25]	math-medium	solved	5m17s
49	[HM24]	hm-medium	solved	4m50s
50	[M20]	math-medium	verified	1m27s
51	[**]		solved	3m37s
52	[HM20]	hm-medium	verified	1m03s
53	[HM20]	hm-medium	verified	2m47s
54	[HM28]	hm-hard	solved	4m03s
55	[HM43]	hm-project	solved	5m
56	[HM43]	hm-project	solved	4m21s
57	[M47]	math-research	verified	1m33s
58	[M21]	math-medium	verified	1m16s
59	[M25]	math-medium	verified	2m37s
60	[M47]	math-research	solved	2m40s
61	[M46]	math-research	solved	4m39s
62	[M49]	math-research	solved	4m44s
63	[M25]	math-medium	verified	1m12s
64	[**]		verified	2m41s
65	[20]	medium	verified	1m15s
66	[25]	medium	solved	9m25s
67	[M41]	math-project	solved	4m38s
68	[**]		verified	1m09s
69	[M25]	math-medium	solved	4m16s
70	[HM43]	hm-project	solved	4m35s
71	[40]	project	verified	1m12s
72	[M28]	math-hard	solved	3m46s
73	[M26]	math-hard	verified	1m12s
74	[M29]	math-hard	verified	1m16s
75	[M26]	math-hard	verified	1m10s
76	[M21]	math-medium	verified	1m14s
77	[M22]	math-medium	solved	4m49s
78	[M26]	math-hard	verified	4m06s

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 1

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 2

The previous solution fails because it never executes the MIX program in Table 1 and never derives an actual address from the algorithm.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

The proposed program computes a hash address using only a very small and fixed portion of each key $K$, namely the characters accessed by the instructions $LDI\ K(1!:!1)$ or $LDIN\ K(4!:!1)$, $LD2\ K(...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 4

Let $N = 365$ and let $n$ be the number of people.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 5

Let a FORTRAN identifier be a string $K = c_1 c_2 \dots c_n$ with $1 \le n \le 10$, and let the proposed hash function be h(K) = \text{leftmost byte of } K.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 6

In MIX arithmetic, the instruction `DIV d` interprets the concatenation $AX$ as a single signed integer formed with $A$ as the high-order word and $X$ as the low-order word.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 7

Let $F = \mathrm{GF}(2^n)$, and let $a \in F$ be an element of order $n$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 8

We restart from the correct structure and avoid any use of invalid fractional-part algebra.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 9

Let $\theta \in (0,1)$ be irrational, and let the sequence of points ${n\theta}$ be inserted into $[0,1]$ as in Theorem S of Section 6.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 10

Let \[ S_j=\{\,\{n\theta+a_j\}:0\le n<N_j\,\},\qquad 1\le j\le d, \] and let $S=\bigcup_{j=1}^d S_j$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 11

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 14

The previous solution fails because it replaces the problem with a partitioned memory model.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 15

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 16

The computation performed by Program L does not fail arithmetically when $K = 0$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 17

In double hashing with open addressing, a key $K$ is examined in the sequence of table positions h_1(K),\; h_1(K) + h_2(K),\; h_1(K) + 2h_2(K),\; \dots \pmod{M}, so that $h_2(K)$ determines the step s...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 19

The previous solution failed in two fundamental ways: it did not perform an empirical investigation and it misinterpreted the constraint $1 < h_2(K) < r$ for small $r$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 20

In the modified Algorithm D, step D3 sets c\leftarrow0, and each time step D4 is entered, the counter is first increased:

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 22

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 24

Let the sample space consist of all sequences $(K_1,\dots,K_7)$ of seven distinct keys chosen from the set of $MP$ possible keys, with each such sequence having equal probability under successive unif...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 25

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 26

Let the hash table be initially empty and let linear probing be used for collision resolution.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 27

The previous argument failed because it replaced both the definition of $s(n,\alpha,y)$ and Abel’s identity with unverified variants.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 28

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.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 29

Working

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 30

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 41

Let $M$ be the table size and $N$ the number of occupied cells under simple uniform hashing, so that all $\binom{M}{N}$ occupied sets are equally likely.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 42

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.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 43

Let $N$ denote the number of items stored.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 44

The previous solution failed because it replaced the actual dependent probing process by an unjustified permutation model.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 45

We restart from the actual stochastic structure of tertiary clustering and keep track of the dependence that was incorrectly removed in the previous solution.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 46

Let the table size be $M$, with $n$ stored keys and load factor $p=n/M$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 47

Let the table have size $M$, with $n$ stored keys and load factor $\alpha=n/M$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 49

Let $K$ be the number of records in a fixed bucket.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 50

By equation (42), the quantity $Q_o(M,N)$ satisfies Q_o(M,N) = 1 + \frac{N}{M} Q_o(M,N-1).

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 51

Let $X(a,n)$ denote the random variable whose expectation is $R(a,n)$ as defined in (55).

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 52

From equation (42), $Q_o(M,N)$ is given by the finite sum Q_o(M,N)=\sum_{k=0}^{N} \binom{N}{k}\frac{k!

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 53

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.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 54

Start from Eq.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 55

The previous argument failed at the very start because it assumed a functional equation without deriving the Schay–Spruth state recursion.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 56

Let $n = Mb$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 57

Let the table have size $M$, and let $n$ records be present, so exactly $M-n$ locations are empty.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 58

Uniform probing, in the sense of Theorem U, corresponds to generating a probe sequence by selecting a permutation of the table addresses ${0,1,2,3,4}$ uniformly from the set of all $5!$ permutations.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 59

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.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 60

Let $M$ be the table size and let $n$ keys be stored, with load factor $\alpha = \frac{n}{M}.$ A single-hashing scheme assigns to each key $K$ a home address $h(K)\in{0,\dots,M-1}$, and associates wit...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 61

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 62

The previous solution incorrectly assumed that the cost functional decomposes as C_y = \frac{1}{M}\sum_K C(K), with each $C(K)$ depending only on the increment sequence assigned to $K$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 63

Let the hash table have $M$ locations.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 64

Let $M$ be the table size and $\alpha=n/M$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 65

Let a variable-length key $K$ be a finite sequence of MIX characters $K = c_1 c_2 \dots c_\ell,$ where each $c_i$ is an element of a fixed alphabet of radix $r$ (for MIX, typically $r = 64$ or $r = 10...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 66

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 67

Linear probing with a full table and distinct home addresses is not governed by “cyclic inversion geometry” in the way the previous solution assumed.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 68

Let $S_N = d_1 + d_2 + \cdots + d_N$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 69

The review identifies three genuine failures: an unjustified symmetry factor, an unsupported intermediate bound, and a mismatch between the run decomposition and the claimed inequality.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 70

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 71

Let $M$ denote the number of hash addresses and let $N$ denote the number of keys stored, with load factor $\alpha = \frac{N}{M}.$ Algorithm C is the separate chaining method described in Section 6.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 72

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

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 73

Let $M$ be the range of hash values $\{0,1,\dots,M-1\}$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 74

Let $H$ be a matrix whose rows are hash functions $h : \mathcal{K} \to {0,1,\dots,M-1}$, and whose columns correspond to keys.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 75

Let ${h_i}_{i=1}^R$ be independent random functions, each mapping the set of keys into ${0,1,\dots,M-1}$, and each value $h_i(K)$ is uniformly distributed over ${0,1,\dots,M-1}$ for every fixed key $K...

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 76

Let a key $K$ be a variable-length sequence $K = (x_0, x_1, \dots, x_{\ell-1}),$ where each $x_i$ is an integer digit in ${0,1,\dots,r-1}$, and $\ell \ge 0$ depends on $K$.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 77

We address the two failures in the original argument: 1.

Practice › Mathematics › TAOCP › TAOCP Vol 3: Sorting and Searching › TAOCP 6.4: Hashing ›

TAOCP 6.4 Exercise 78

Let $w>m>0$, $L=2^{w-m}$, and work modulo $2^w$.