8.1 (Action!)

Find all the occurrences of the string with jokers ab b ab in the text bababbaabbaba.

Find all the occurrences of the string with jokers ab b a in the text with jokers bababb ab aba.

8.2

Find all the occurrences with at most two mismatches of the string ACGAT in the text GACGATATATGATAC.

8.3 (Costs)

What costs should we attribute to the edit operations for realizing the following operations? For x, y ? A ⁺ and ? ? N:

• find the string x in the text y,

• search for the subsequences of y that are equal to x,

• search for the subsequences of y of the form x ₀ u ₀ x ₁ u ₁ u _{k ?1} x _{k ? 1} where x = x ₀ x ₁ x _{k ?1}, and u _i ? ? for i = 0 , 1 , , k ? 1.

8.4

Find all the occurrences with at most two differences of the string ACGAT in the text GACGATATATGATAC using the algorithm K-DIFF-DP.

Solve the same question using the algorithms K-diff-cut-off and K-diffdiag.

8.5 (Savings)

Describe an implementation of the algorithm K-DIFF-DIAG that runs in space O( m). ( Hint: swap the loops on q and d