Lab Assignment 2 Solution

Description

Goals:

1. Understanding of binary search.

2. Understanding of subsequences.

Requirements:

1. Design, code, and test a C program to compute the maximum interleave factor i for an integer sequence X such that the resulting interleaved sequence X ⁽ⁱ⁾ is a subsequence of another integer sequence A. The input will be formatted as follows:

1. 1. Two integers giving the number of integers in sequences A and X (i.e. A and X ).

1. 2. Each integer of A, one per line.

1. 3. The number -999999999 on a line by itself.

   4. Each integer of X , one per line.

1. 5. The number -999999999 on a line by itself.

The input is to be read from standard input as one of 1) keyboard typing, 2) a shell redirect (<) from a file, or 3) cut-and-paste. Do NOT prompt for a file name!

The interleaved sequence X ⁽ⁱ⁾ for a sequence X and an interleave factor i ≥ 0 results from repeating each element of X exactly i times “in place”. So, if X = abbcda, X⁽²⁾ is aabbbbccddaa and

X⁽³⁾ is aaabbbbbbcccdddaaa. X⁽⁰⁾ is always the empty sequence. (Aside for those with CSE 3315 background: X ⁱ is the ith power of sequence X . So, if X = abbcda, X² is abbcdaabbcda and X ³ is abbcdaabbcdaabbcda by concatenation.)

A sequence U is a subsequence of a sequence V if there is at least one way to delete V − U

elements from V to leave the sequence U. So, U = cba is a subsequence of V = abcabcabc by performing these deletions from V = abcabcabc.

The output of your program is the trace of the successes and failures of a binary search (including “low”, “mid”, and “high”) for determining the maximum interleave factor that satisfies the subsequence condition. The last line output should provide the maximum interleave factor.

2. Submit your program on Blackboard by 10:45 am (section 004) or 1:45 pm (section 003) on October 4. One of the comment lines should indicate the compilation command used on OMEGA.

Getting Started:

1. Assumptions about the input file:

1. 1. A ≥ X

1. 2. The integers in the two sequences will appear on lines by themselves. You may, however, simply read input using scanf(“%d”,&num).

2. Arrays must be dynamically allocated based on the first line of the input.

3. Thoroughly debug your subsequence testing code before attempting to call it from your binary search code. Subsequence testing is easily performed in Ο( A ) time.

4. Test cases are available on the course web page. The GTA may use other cases when checking your submissions.

5. Your program must take time in Ο( A • log( A / X )), i.e. the subsequence test function will be called a logarithmic number of times in the controlling binary search code.

6. Note that if X ⁽ⁱ⁺¹⁾ is a subsequence of A, then X ⁽ⁱ⁾ is a subsequence of A. Likewise, if X⁽ⁱ⁾ is not

1. 1. subsequence of A, then X⁽ⁱ⁺¹⁾ is not a subsequence of A.