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.
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.
