TAOCP 3.3.2 Exercise 7

**Exercise 3.

taocpmathematicsalgorithmsvolume-1simple

Section 3.3.2: Empirical Tests

Exercise 7. [08] Apply the coupon collector's test procedure (Algorithm C), with $d = 3$ and $n = 7$, to the sequence 11012210221202020121220101020121. What lengths do the seven subsequences have?

Verified: no
Solve time: 4m21s

Exercise 3.3.2.7 [08], Corrected Solution

We apply Algorithm C (the coupon collector's test) to the sequence

$$ 11012210221202020121220101020121 $$

with $d = 3$ and $n = 7$. Let the set of observed values be ${0,1,2}$. Define OCCURS as an array keeping track of which values have appeared in the current subsequence, initialized to zero: $\text{OCCURS}[0] = \text{OCCURS}[1] = \text{OCCURS}[2] = 0$. We scan the sequence from left to right, starting at the first element, to find the minimal subsequence containing all three values. After a complete set is found, we reset OCCURS and continue scanning for the next subsequence.

Step-by-step scan

Let positions be indexed from 1 to 31.

1. First subsequence

  • Scan positions 1–5: 1 1 0 1 2
  • Values observed: 0,1,2
  • Minimal length: $r_1 = 5$
  • Subsequence: 11012

2. Second subsequence

  • Start at position 6 (2)
  • Scan positions 6–8: 2 1 0
  • Values observed: 0,1,2
  • Minimal length: $r_2 = 3$
  • Subsequence: 210

3. Third subsequence

  • Start at position 9 (2)
  • Scan positions:

9: 2 → observed {2}

10: 2 → {2}

11: 1 → {1,2}

12: 2 → {1,2}

13: 0 → {0,1,2}

  • Minimal length: $r_3 = 5$
  • Subsequence: 22120

4. Fourth subsequence

  • Start at position 14 (2)
  • Scan positions:

14: 2 → {2}

15: 0 → {0,2}

16: 2 → {0,2}

17: 0 → {0,2}

18: 1 → {0,1,2}

  • Minimal length: $r_4 = 5$
  • Subsequence: 20201

5. Fifth subsequence

  • Start at position 19 (2)
  • Scan positions:

19: 2 → {2}

20: 1 → {1,2}

21: 2 → {1,2}

22: 2 → {1,2}

23: 0 → {0,1,2}

  • Minimal length: $r_5 = 5$
  • Subsequence: 21220

6. Sixth subsequence

  • Start at position 24 (1)
  • Scan positions:

24: 1 → {1}

25: 0 → {0,1}

26: 1 → {0,1}

27: 0 → {0,1}

28: 2 → {0,1,2}

  • Minimal length: $r_6 = 5$
  • Subsequence: 10102

7. Seventh subsequence

  • Start at position 29 (0)
  • Scan positions:

29: 0 → {0}

30: 1 → {0,1}

31: 2 → {0,1,2}

  • Minimal length: $r_7 = 3$
  • Subsequence: 012

Conclusion

The lengths of the seven minimal subsequences that each contain all three values are

$$ \boxed{5, 3, 5, 5, 5, 5, 3}. $$

Each subsequence is verified to be minimal: removing any element would omit at least one of the three values.