Exercise 39. ▶ [M21] $[M21]$ Experiment with exact cover problems that are defined by $m$ random options on $n$ items. (Each option is generated independently, with repetitions permitted.)

a) Use a fixed probability $p$ that item $i$ is included in any given option.

b) Let every option be a random sample of $r$ distinct items.

Verified: no
Solve time: 1m57s

Solution

Let $m$ be the number of options and let $n$ be the number of items. The experiment consists of generating an exact cover instance, running Algorithm X with the dancing-links representation of Section 7.2.2.1, and recording quantities that measure the difficulty of the search. The useful statistics are the number of recursive calls, the maximum recursion depth, the number of item choices made, and the number of solutions found.

For each generated instance, the exact-cover database is initialized with the $m$ options. Algorithm X selects an item $i$ as in step X2, covers it by the operation $\text{cover}(i)$ of equation (12), recursively explores the remaining options, and restores the data structure by $\text{uncover}(i)$ of equation (14). The number of recursive calls is counted once for each execution of step X2.

For part (a), each option is generated by including each item independently with probability $p$. Thus an option has random size

$$ |O|\sim\operatorname{Binomial}(n,p), $$

and the expected number of items in one option is

$$ E(|O|)=np. $$

For a fixed item $i$, the probability that a generated option contains $i$ is $p$. Hence the number of options containing $i$ is

$$ \operatorname{Binomial}(m,p), $$

with expected value

$$ E(\deg(i))=mp. $$

The initial vertical list length $\operatorname{LEN}(i)$ in Table 1 therefore has expected value $mp$. The probability that an item has no available options at the beginning is

$$ (1-p)^m. $$

A large value of $(1-p)^m$ produces many immediate failures at step X2, while a small value means that more branching occurs. Therefore the experiment varies $p$ for fixed $m$ and $n$, and records the search tree size. The hardest region is expected near the transition where neither immediate failure nor nearly unique forced choices dominate.

For part (b), each option is generated by choosing exactly $r$ distinct items from the $n$ items. The size of every option is therefore

$$ |O|=r. $$

For a fixed item $i$, the probability that $i$ is included in a random option is

$$ \frac{\binom{n-1}{r-1}}{\binom nr}

\frac rn. $$

Consequently the number of options containing $i$ is

$$ \operatorname{Binomial}\left(m,\frac rn\right), $$

and its expected value is

$$ E(\deg(i))=m\frac rn. $$

The probability that an item initially has no options is

$$ \left(1-\frac rn\right)^m. $$

The experiment for this model fixes $m,n,r$ and generates many independent instances. For every instance, Algorithm X is run until all branches have been exhausted. The recorded averages are

$$ \overline{C}

\frac1T\sum_{t=1}^{T} C_t, $$

where $C_t$ is the number of recursive calls in trial $t$, and

$$ \overline{S}

\frac1T\sum_{t=1}^{T} S_t, $$

where $S_t$ is the number of exact covers found in trial $t$. Increasing $T$ reduces random fluctuation in these estimates.

The two models can be compared by matching the expected option size. In part (a), choose

$$ p=\frac rn, $$

so that

$$ E(|O|)=np=r. $$

The two experiments then have the same average number of items per option. The difference is that part (a) allows repeated option sizes, including empty options and large options, whereas part (b) fixes every option size exactly.

A complete experiment therefore consists of generating instances for chosen values of $m,n,p$ in part (a) and $m,n,r$ in part (b), executing Algorithm X with the dancing-links operations (12) and (14), and averaging the recorded search statistics. The final quantities predicted by the generation models are

$$ \boxed{E(|O|)=np,\qquad E(\deg(i))=mp,\qquad P(\deg(i)=0)=(1-p)^m} $$

for part (a), and

$$ \boxed{|O|=r,\qquad E(\deg(i))=\frac{mr}{n},\qquad P(\deg(i)=0)=\left(1-\frac rn\right)^m} $$

for part (b).

TAOCP 7.2.2.1 Exercise 39

Solution

$$ \frac{\binom{n-1}{r-1}}{\binom nr}

$$ \overline{C}

$$ \overline{S}