TAOCP 7.2.2.1 Exercise 82

Section 7.2.2.1: Dancing Links

Exercise 82. [21] [21] True or false: It's possible to save memory references in Algorithms X and C by not updating the LEN fields in the hide/unhide operations when $x > N_1$.

Verified: yes
Solve time: 1m41s

Solution

The statement is true.

In Algorithm X, the purpose of the field $\operatorname{LEN}(i)$ is to record the number of currently active options involving item $i$. The only time Algorithm X needs these values is when it chooses an item to cover. The choice step considers only items that still need to be covered. In the version with primary and secondary items, the primary items are numbered $1,\ldots,N_1$, while the secondary items are numbered $N_1+1,\ldots,N$. Secondary items are not selected for branching, because they are not required to be covered exactly once.

During $\operatorname{hide}(p)$, the code in (13) decreases $\operatorname{LEN}(x)$ whenever the hidden node belongs to item $x$:

$\operatorname{LEN}(x)\leftarrow \operatorname{LEN}(x)-1.$

During $\operatorname{unhide}(p)$, the inverse operation restores those values. For $x\leq N_1$, these updates are necessary because the values of $\operatorname{LEN}(x)$ determine future choices of items. For $x>N_1$, the values are never inspected by Algorithm X when making a choice, because no secondary item is ever chosen as the next item to cover.

The same argument applies to Algorithm C. The color mechanism changes the conditions under which an option can be selected, but the branching decisions are still made using the primary items. The fields $\operatorname{LEN}(x)$ for secondary items do not influence any subsequent selection or feasibility test. Therefore changing

$\operatorname{LEN}(x)\leftarrow\operatorname{LEN}(x)-1$

and its corresponding restoration during $\operatorname{unhide}$ into a no-op whenever $x>N_1$ cannot change the sequence of choices or the set of solutions found.

The modification saves memory references because every occurrence of a node belonging to a secondary item no longer requires the two memory references needed to read and write $\operatorname{LEN}(x)$. Since those values are not used, omitting these updates preserves the invariants required by both algorithms.

Hence the proposed optimization is valid.

$$ \boxed{\text{true}} $$