Programming Assignment: Foundations of Algorithms

The following is a problem to be completed by the individual (i.e., it is not collaborative) and then implemented. You may use any programming language you wish. Follow the requirements provided under Syllabus & Course Information under the link Programming Assignment Requirements.

1. Programming (non-collaborative)Due at the end of Module 13. 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 xk to denote k copies of x concatenated together. We say that string x′ is a repetition of x if it is a prex of xk 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.