Extra information: sample input and output: 1. Design, code, and test a C program to compute the

Extra information:

sample input and output:

 
 
  

Transcribed Image Text:

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(i) is a subsequence of another integer sequence A. The input will be formatted as follows: a. Two integers giving the number of integers in sequences A and X (i.e. A and X). b. Each integer of A, one per line. c. The number -999999999 on a line by itself. d. Each integer of X, one per line. e. 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(i) for a sequence X and an interleave factor i 2 0 results from repeating each element of X exactly i times "in place". So, if X = abbeda, x(2) is aabbbbeeddaa and x(3) is aaabbbbbbcccdddaaa. x(0) is always the empty sequence. (Aside for those with CSE 3315 background: X is the ith power of sequence X. So, if X= abbeda, X² is abbedaabbcda and X³ is abbedaabbcdaabbeda 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 = abcabcabe by performing these deletions from Vabcabeabe. 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. 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(i) is a subsequence of another integer sequence A. The input will be formatted as follows: a. Two integers giving the number of integers in sequences A and X (i.e. A and X). b. Each integer of A, one per line. c. The number -999999999 on a line by itself. d. Each integer of X, one per line. e. 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(i) for a sequence X and an interleave factor i 2 0 results from repeating each element of X exactly i times "in place". So, if X = abbeda, x(2) is aabbbbeeddaa and x(3) is aaabbbbbbcccdddaaa. x(0) is always the empty sequence. (Aside for those with CSE 3315 background: X is the ith power of sequence X. So, if X= abbeda, X² is abbedaabbcda and X³ is abbedaabbcdaabbeda 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 = abcabcabe by performing these deletions from Vabcabeabe. 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.