Foundations of Algorithms

Programming Assignment #3

The following is a problem to be completed by the individual (i.e., it is not collaborative) and then implemented.

Please follow the requirements provided under Syllabus & Course Information under the link Programming Assignment Requirements.

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 hearing is simply an interweaving 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 0 is a repetition of x if it is a prefix of x k for some number k.

So, x 0 = 10110110110 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 0 and s 00 so that s 0 is a repetition of x and s 00 is a repetition of y.
(So each symbol in s must belong to exactly one of s 0 of s 00.)

For example, if x = 101 and y = 00, 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 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.

Solution PreviewSolution Preview

These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice. Unethical use is strictly forbidden.

import java.util.HashMap;

* Programming Assignment #3
public class ProgrammingAssignment3 {

// Counter to keep track of comparisons
private static int comparisonCounter;

// Method to check if String s is an Interleaving of String x and String y
public static boolean isInterleave(String s, String x, String y) {
    // Set comparison counter to zero
    comparisonCounter = 0;
    // Extend the length of x to s by duplicating...

By purchasing this solution you'll be able to access the following files:
Solution.docx, and OUTPUT.png.

for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Upload a file
Continue without uploading

We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats