Description
- Write a Java, Python, C, or C++ program that outputs a longest common subsequence of three input sequences X, Y , and Z of symbols from a fixed alphabet. For example, if the input is:
X = ⟨N,I,N,E⟩,
Y = ⟨S,I,N,G,I,N,G⟩, Z = ⟨N,I,N,J,A,S⟩then the output should be ⟨N, I, N⟩. For this input, the optimal solution is unique. For inputs where the optimal solution is not unique, your program may output any longest common subsequence. (If you want to use another programming language, get the instructors’ approval first.) (4 marks)
- In the report, briefly explain how your program works and analyze its time and space complexity. Also, show a small example input created by you and the corresponding output. (2 marks)
- Whenallthreeinputsequenceshavethesamelengthn,whatisthelargestnforwhichyourprogram manages to compute a solution in less than one minute? Is the execution time or running out of memory the main issue here? Put this “extreme” example in “Max99999999Z.txt”. (1 mark)
- A binary sequence is a sequence over the alphabet {0, 1}. For example, ⟨0, 1, 0, 1, 1, 0, 0, 0⟩ is a binary sequence. Give an example of three binary sequences X, Y, Z, each of length 8, such that the length of a longest common subsequence of X and W, where W is a longest common subsequence of Y and Z, is different from the length of a longest common subsequence of X, Y , Z. You may use your program to find such an example. (2 marks)
- For 10 different values of n selected by you, use your program to compute A(n), defined as follows. A(n) is the average length of a longest common subsequence of three randomly generated binary sequences X, Y , Z of length n, where all symbols in the sequences are chosen independently and uniformly at random from {0,1} and the average is taken over 10 independent runs. In other words, you need to run your program 10 times for each n and therefore 100 times in total.
Present your results in a table with ten rows and three columns: one column for n, one column for A(n), and one column for the ratio A(n)/n. According to your experiments, does A(n)/n seem converge to any constant, and if so, what is its value? (3 marks)
- This question concerns the case of two input sequences. Prove that every algorithm that outputs all longest common subsequences of two input sequences has a worst-case running time that is expo- nential. To do so, show how to define, for every positive integer n, two length-n sequences Xn, Yn having Ω(cn) different longest common subsequences, where c is a constant. You are allowed to use an alphabet of size n, i.e., the symbols in Xn, Yn can come from a set {a1, a2, . . . , an}. (3 marks)
