Kleinberg, Jon. Algorithm Design $($p$.329,$ q$.19).$

String x$$ is a repetition of x if it is a prefix of xk $($k copies of x concatenated together$)$ for some integer k$.$ So x$=10110110110$ is a repetition of x $=101.$ 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 x$$ and y$,$ so that x$$ is a repetition of x and y$$ is a repetition of y$.$ For example, if x $=101$ and y $=00,$ then s $=100010010$ is an interleaving of x and y$,$ since characters $1,2,5,8,9$ form $10110$a repetition of x$$and the remaining characters $3,4,6,7$ form $0000$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 by answering the following:

$($a$)$ Give a recursive algorithm. $($The algorithm does not need to be efficient$)$

Solution:

$($b$)$ Give an efficient dynamic programming algorithm.

Solution:

Page $14$ of $17$

CS $577$ Assignment $4$ Dynamic Programming Summer $2024$

$($c$)$ Prove that the algorithm in part $($b$)$ is correct.

Solution: