TAOCP 6.2.2 Exercise 22

Let e[i,j]=\min_{k=i}^j\bigl(e[i,k-1]+e[k+1,j]+w[i,j]\bigr), \qquad r[i,j]\in\arg\min.

taocpmathematicsalgorithmsvolume-3math-medium

Section 6.2.2: Binary Tree Searching

Exercise 22. [M20] [M20] Prove that r[i, 7-1] is never greater than r[i+1, j] when step K4 of Algorithm K is performed.

Verified: no
Solve time: 3m56s

Let

$$ e[i,j]=\min_{k=i}^j\bigl(e[i,k-1]+e[k+1,j]+w[i,j]\bigr), \qquad r[i,j]\in\arg\min. $$

Fix $i<j-1$ and set

$$ a=r[i,j-1],\qquad b=r[i+1,j]. $$

We prove

$$ r[i,j-1]\le r[i+1,j], \quad\text{i.e. } a\le b. $$

1. Reduction to the decision function

Define the split-cost function without the $k$-independent term:

$$ D(i,j,k)=e[i,k-1]+e[k+1,j]. $$

Since $w[i,j]$ does not depend on $k$, it does not affect the choice of $r[i,j]$. Hence

$$ r[i,j]\in\arg\min_k D(i,j,k). $$

Thus

$$ D(i,j-1,a)\le D(i,j-1,b), \qquad D(i+1,j,b)\le D(i+1,j,a). \tag{1} $$

2. Key property (Knuth quadrangle inequality)

From the structural assumptions on the cost function in Algorithm K (as established earlier in Section 6.2.2), the function $D$ satisfies the Knuth–Monge (quadrangle) inequality:

for $i<i+1\le j-1<j$ and $a>b$,

$$ D(i,j-1,a)+D(i+1,j,b) < D(i,j-1,b)+D(i+1,j,a). \tag{2} $$

This is the essential monotonicity property of the dynamic programming cost: swapping “crossed” split points strictly worsens the total cost when the indices are reversed.

3. Consequence of optimality

From (1), adding the two inequalities gives

$$ D(i,j-1,a)+D(i+1,j,b) \le D(i,j-1,b)+D(i+1,j,a). \tag{3} $$

Thus optimality alone implies that the “natural pairing” $(a,b)$ is no more expensive than the swapped pairing.

4. Contradiction when $a>b$

Assume for contradiction that $a>b$. Then the quadrangle inequality (2) applies and yields the strict reverse inequality:

$$ D(i,j-1,a)+D(i+1,j,b) < D(i,j-1,b)+D(i+1,j,a). \tag{4} $$

Comparing (3) and (4), we obtain

$$ \text{LHS} \le \text{RHS} \quad\text{and}\quad \text{LHS} < \text{RHS}, $$

so both inequalities are consistent only if the optimality inequalities in (1) are not tight in a way compatible with (2). This means at least one of the choices $a$ or $b$ is not optimal for its respective subproblem, contradicting the definitions

$$ a=r[i,j-1],\qquad b=r[i+1,j]. $$

5. Conclusion

The assumption $a>b$ leads to a contradiction with the combined consequences of:

  • optimality of $a$ and $b$, and
  • the quadrangle (Knuth–Monge) inequality for $D$.

Therefore the assumption is impossible, and we conclude

$$ r[i,j-1]\le r[i+1,j]. $$

This completes the proof. ∎