[39] Consider the SCS problem defined in Section 6.7. Prove by incompressibility the following: Let S be a set of n sequences of

[39] Consider the SCS problem defined in Section 6.7. Prove by incompressibility the following: Let S ⊆ Σ∗ be a set of n sequences of length n, and let δ = √

2/2 ≈ 0.707. Let scs(S) be the length of an SCS of S. The following algorithm majority-merge produces a common supersequence of length scs(S) + O(scs(S)δ) on the average.

Algorithm majority-merge {Input: n sequences, each of length n}

Step 1. Set supersequence s := . { is the null string}

Step 2. {Let the letters a form a majority among the leftmost letters of the remaining sequences} Set s := sa and delete the front a from these sequences. Repeat this step until no sequences are left.

Step 3. Output s.

Comments. Source: [T. Jiang and M. Li, SIAM J. Comput., 24:5(1995), 1122–1139]. Part of the proof was from [D. Foulser, M. Li, and Q. Yang, Artificial Intelligence, 57(1992), 143–181].