[Solved] 605.621 Foundations of Algorithms Programming Assignment 2

These programming problems are not collaborative assignments. You are required to follow the Programming Assignment Guidelines and the Pseudocode Restrictions (Blackboard page Syllabus & Course Information ) when

preparing your solutions to these problems.

For small input instances, n30, you may output your results to the command window. Larger input instances must be written to a file. In either case, you may need to produce an output file for trace runs or asymptotic performance analysis.

1. Programming (non-collaborative): 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 receiving is simply an interweaving of these two emissions, with nothing extra added in. The short sequence emitted by each ship is known to the ship and to you, the receiver.

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⁰ =101101101 is a repetition of x=101.

We say that a string s is an interweaving 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. Each symbol in s must belong to exactly one of s⁰ of s⁰⁰. For example, if x = 101 and y = 0, then s = 100010101 is an interweaving of x and y since characters 1,2,5,7,8, and 9 form 101101 a repetition of x and the remaining characters 3,4,6 form 000 a 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 receiving. We want to make sure s unravels into simple repetitions of x and y.

You want a fast algorithm for untangling a superposition of two known signals, x and y. You receive some set of symbols s. You do not know if the signal you receive has its first symbol in x, y, or a symbol that is extra and added in. You need to use your knowledge of x and y and the received signal s to determine if s consists only of valid interwoven symbols from x and y. That may require your solution to discard some symbols at the beginning or end of s to get to at least a full match of x and a full match of y. The received signal could be too short to do this. If you cant determine that the signal is an interweaving of x and y, either because s is not long enough to do so or because s contains symbols not in x or y then you cannot decide that s is an interweaving of x and y.

• [50 points] Give an efficient algorithm that takes strings s, x, and y and decides if s is an interweaving of x and y. Derive the computational complexity of your algorithm.
• [50 points] Implement your algorithm and test its run time to verify your complexity 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