Answer Happy

Do NOT write pseudocode when describing your dynamic programs. Rather give the Bellman Equation, describe the matrix, its axis and how to derive the desired solution from it.
1. Kleinberg, Jon. Algorithm Design (p. 329, q. 19). We say that a string s is an interleaving of x and y if its symbols can be partitioned into two (not necessarily contiguous) subsequences s' and s", so that s' is a repetition of x and s" is a repetition of y. Give an efficient algorithm that takes strings s, x, and y and decides if s is an interleaving of x and y. Note: We write xk to denote k copies of a concatenated together. We say that a string r' is a repetition of x if it is a prefix of rk for some number k. So ' = 10110110110 is a repetition of x = 101.