For this dynamic programming problem and the next one be sur

For this dynamic programming problem and the next one, be sure to

(a) describe the subproblem

(b) give a recurrence for the subproblem

(c) provide pseudo-code showing how a table for the subproblems is filled

(d) give the time and space requirements of your method Suppose we have two transmitters, each of which sends out repetitions of some short string.

For example, transmitter 1 may repeat string x=101 over and over, so what we will hear from it will be a prefix of x k - that is, x concatenated to itself k times, possibly with a few bits chopped of the end (as in 10110110). Transmitter 2 repeats another string, y. Our job is to determine if a sequence s that we have heard is an interleaving of these two transmissions.

For example, suppose transmitter 1 repeats x=101 and transmitter 2 repeats y=01. The sequence 010111010101 can be unraveled into x and y: positions 1, 5, 9, and 12 contain 0101, a repetition of y, while the remainder of the string contains 10110110, a repetition of x.

Describe an efficient algorithm which takes a sequence s of length n, and two strings x and y, and determines if s is an interleaving of repetitions of x and y.

Solution

Let the length of X be m, length of Y be n and length of S be k. We can see that the given problem can be reduced to sub-problem s.

1a. If the current character at S matches with current character in both X and Y, then move one step ahead in X, Y, C and check recursively

1b. If the current character at S matches with current character at X and but not with the current character of Y, then move one step ahead in X, C and check recursively

1c. If the current character at S matches with current character at Y and but not with the current character of X, then move one step ahead in Y, C and check recursively

2. If X and Y are empty, then return true

3. If X is empty, then check if the current characters of Y and S matches, if yes, then move a step ahead in Y, S and check recursively, otherwise return false

4. If Y is empty, then check if the current characters of X and S matches, if yes, then move a step ahead in X, S and check recursively, otherwise return false

Recurrence Relation

                                           T[m-1, n-1] if X[m] == S[n+m] and Y[n] == S[n+m]

1. T[m, n]        =     T[m-1, n] if X[m] == S[n+m] and Y[n] != S[n+m]

                                           T[m, n-1] if Y[n] == S[n+m] and X[m] != S[n+m]

2. T[0, 0] = True if X and Y are empty

3. T[0, n] = T[0, n-1] if X is Empty and Y[n] == S[n]

4. T[m, 0] = T[m-1, 0] if Y is Empty and X[m] == S[m]

If we draw the recurrence tree for some specific problem, then we can see that there are many overlapping problems. So here we can use dynamic programming to store the intermediatory result.

PseudoCode

IsInterleaving(X, Y, S, m, n, k)
1. if (m+n != k)
2. return false
3. T[m+1][n+1] // Boolean matrix
4. for i=0 to m
5.        for j=0 to n
6.                if i==0 and j==0                            // Both X and Y are empty, Case - 2
7.                      T[i][j] = true
8.                else if i==0 and Y[j-1] == S[j-1]     // Case - 3
9.    T[i][j] = T[i][j-1]
10.              else if j==0 and X[i-1] == S[i-1]    // Case - 5
11.                    T[i][j] = T[i-1][j]
12.              else if X[i-1] == S[i+j-1] and Y[j-1] != S[i+j-1]    // Case - 1a
13                     T[i][j] = T[i-1][j]
14.              else if Y[j-1] == S[i+j-1] and X[i-1] != S[i+j-1]    // Case - 1b
15.                    T[i][j] = T[i][j-1]
16.              else if X[i-1] == S[i+j-1] and Y[j-1] == S[i+j-1] // Case - 1c
17.                    T[i][j] = T[i-1][j-1]
18 return T[m][n]