You are consulting for a group of people (who would prefer not to be mentioned here by name) whose job consists of monitoring and analyzing electronic signals coming from ships in the Atlantic ocean. They want a fast algorithm for a basic primitive that arises frequently: untangling a superposition of two known signals. Specifically, they are picturing a situation in which each of two ships is emitting a short sequence of 0s and 1s over and over, and they want to make sure that the signal they are hearing is simply an interleaving of these two emissions, with nothing extra added in. This describes the whole problem; we can make it a little more explicit as follows. Given a string x consisting of 0s and 1s, we write x k to denote k copies of x concatenated together. We say that string x ? is a repetition of x if it is a prefix of x k for some number 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) subsequence s ? and s ?? so that s ? is a repetition of x and s ?? is a repetition of y. (So each symbol in s must belong to exactly one of s ? and s ??.) For example, if x = 101 and y = 00, then s = 100010101 is an interleaving of x and y since characters 1, 2, 5, 7, 8, and 9 form 101101a repetition of xand the remaining characters 3, 4, 6 form 000a repetition of y. In terms of our application, x and y are the repeating sequences from the two ships, and s is the signal we are listening to. We want to make sure s unravels into simple repetitions of x and y.

(a) Give an efficient algorithm that takes strings s, x, and y and decides if s is an interleaving of x and y. Derive the computational complexity of your algorithm.

(b) Implement your algorithm above and test its run time to verify your analysis. Remember that CPU time is not a valid measure for testing run time. You must use something such as the number of comparisons.

1. Programming You are consulting for a group of people (who would prefer not to be mentioned here by name) whose job consists of monitoring and analyzing electronic signals coming from ships in the Atlantic ocean. They want a fast algorithm for a basic primitive that arises frequently: "untangling, a superposition of two known signals. Specif. ically, they are picturing a situation in which each of two ships is emitting a short sequence of 0s and ls over and over, and they want to make sure that the signal they are hearing is simply an interleaving of these two emissions, with nothing extra added in. This describes the whole problem; we can make it a little more explicit as follows. Given a string r consisting of Os and 1s, we write r*to denote k copies of concatenated together. We say that string r is a repetition of if it is a prefix of *umk 10110110110 is a repetition of z 101 We say that a string s is an interleaving of r and y if its symbols can be partitioned into two (not necessarily contiguous) subsequence s' and s" so that s' is a repetition of r and s" is a repetition of y. (So each symbol in s must belong to exactly one of s' and s".) For example, if 101 and y 00 then s 100010101 is an interleaving of r and y since characters 1, 2, 5, 7, 8, and 9 form 101101-a repetition of z -and the remaining characters 3, 4, 6 form 000-a repetition of y. In terms of our application, r and y are the repeating sequences from the two ships, and s is the signal we are listening to. We want to make sure s "unravels" into simple repetitions of r and y Give an efficient algorithm that takes strings s, , and y and decides if s is an inter- leaving of z and y. Derive the computational complexity of your algorithm. Implement your algorithm above and test its run time to verify your analysis. Remem- ber that CPU time is not a valid measure for testing run time. You must use something such as the number of comparisons