TAOCP 6.4 Exercise 32

Section 6.4: Hashing

Exercise 32. [M27] Prove that the system of equations (44) has a unique solution $(c_0, c_1, \ldots, c_{M-1})$, whenever $b_0, b_1, \ldots, b_{M-1}$ are nonnegative integers whose sum is less than $M$. Design an algorithm to find that solution.

Verified: no
Solve time: 12m33s

Setup

In the context of linear probing hashing (or the equivalent parking problem), let (M) be the table size (number of parking spaces). For each address (i = 0,1,\dots,M-1), let (b_i) be the number of keys that initially hash to address (i) (or the number of cars that prefer space (i+1)). The linear probing insertion process places each key in the first empty cell at or after its hash address. The final occupancy of cell (i) is denoted by (c_i) (where (c_i = 1) if occupied, (0) otherwise). During the process, some keys are displaced from cell (i) to cell (i+1); let (x_i) be the number of such displaced keys. The process is governed by the system of equations (44) from the text:

[ c_i + x_i = b_i + x_{i-1} \qquad (i = 0,1,\dots,M-1) \tag{44} ]

with boundary conditions (x_{-1} = 0), (x_{M-1} = 0), and the constraints (c_i \in {0,1}), (x_i \ge 0) (integers).
We are given that (b_0,b_1,\dots,b_{M-1}) are nonnegative integers with (\sum_{i=0}^{M-1} b_i < M). The problem asks to prove that (44) has a unique solution ((c_0,\dots,c_{M-1})) (and corresponding (x_i)) satisfying the constraints, and to design an algorithm to find it.

Solution

Algorithm.
The unique solution is obtained by a single left‑to‑right pass that simulates the linear probing insertion (or chip‑firing stabilization):

x_{-1} ← 0
for i = 0 to M-1:
    t ← b_i + x_{i-1}
    if t ≥ 1:
        c_i ← 1
        x_i ← t - 1
    else:
        c_i ← 0
        x_i ← 0

After the loop, the values (c_i, x_i) satisfy (44) and the constraints. The condition (\sum b_i < M) guarantees that (x_{M-1} = 0), so the right boundary holds.

Proof of correctness and uniqueness.
We show by induction on (i) that the pair ((c_i, x_i)) is uniquely determined by the recurrence and constraints.

For (i = 0): we have (c_0 + x_0 = b_0 + x_{-1} = b_0) with (c_0 \in {0,1}, x_0 \ge 0). The only possibility is
(c_0 = 1, x_0 = b_0 - 1) if (b_0 \ge 1); otherwise (c_0 = 0, x_0 = 0). Hence ((c_0, x_0)) is unique.

Assume ((c_0,x_0),\dots,(c_{i-1},x_{i-1})) are uniquely determined. Then (x_{i-1}) is fixed. The equation for index (i) is (c_i + x_i = b_i + x_{i-1}) with (c_i \in {0,1}, x_i \ge 0). Exactly the same reasoning applies: the right‑hand side is a known nonnegative integer (t = b_i + x_{i-1}). The unique solution is (c_i = 1, x_i = t-1) if (t \ge 1); otherwise (c_i = 0, x_i = 0). Thus ((c_i, x_i)) is uniquely determined.

By induction, the entire sequence ((c_0,x_0),\dots,(c_{M-1},x_{M-1})) is uniquely determined. The final boundary condition (x_{M-1} = 0) is automatically satisfied because the total number of keys is (\sum b_i = \sum c_i + x_{M-1}) (summing (44) over (i) telescopes the (x_i) terms), and (\sum c_i \le M) with equality only if all cells are occupied. Since (\sum b_i < M), we must have (x_{M-1} = 0); otherwise (\sum b_i = \sum c_i + x_{M-1} \ge M) (because (\sum c_i \ge 0)), a contradiction. Hence the unique solution also satisfies the right boundary condition.

The algorithm above implements exactly this inductive construction, so it produces the unique solution. Its running time is (O(M)).

Verification

Boundary case: (M = 3,; b = (2,0,0)) (sum (= 2 < 3)).
(i=0:; t = 2 \Rightarrow c_0=1,; x_0=1.)
(i=1:; t = 0+1=1 \Rightarrow c_1=1,; x_1=0.)
(i=2:; t = 0+0=0 \Rightarrow c_2=0,; x_2=0.)
Result: (c = (1,1,0)). Check (44):
(c_0+x_0 = 2 = b_0+x_{-1})
(c_1+x_1 = 1 = 0+1 = b_1+x_0)
(c_2+x_2 = 0 = 0+0 = b_2+x_1)
(x_{-1}=x_2=0). All constraints hold.

Another test: (M = 3,; b = (0,2,0)).
(i=0:; t=0 \Rightarrow c_0=0,x_0=0.)
(i=1:; t=2 \Rightarrow c_1=1,x_1=1.)
(i=2:; t=1 \Rightarrow c_2=1,x_2=0.)
(c = (0,1,1)); equations hold.

Necessity of (\sum b_i < M): If (\sum b_i = M), e.g., (b = (1,1,1)), the algorithm gives (x_2 = 1 \neq 0), violating the boundary condition. The system then has no solution satisfying all constraints, which matches the physical fact that a full table (or a full street) cannot accommodate all keys without failure.

This completes the proof. ∎