Assignment 2
• A source code file named “LCS99999999Z” plus a filename extension, e.g., “LCS99999999Z.c”, for the program in question 1. Include your name and student ID number in the source code.
• A .pdf-, .doc-, .docx-, .txt-, or .jpg-file containing a report with your solutions to questions 2–6. The filename should start with “A2 99999999Z”. Include your name and student ID number at the top of each page. Scanned, handwritten solutions are OK as long as they are easily readable.
• A file named “Max99999999Z.txt” with the extreme example you found in question 3.
1. Write a Java, Python, C, or C++ program that outputs a longest common subsequence of threeinput sequences X, Y , and Z of symbols from a fixed alphabet. For example, if the input is: X = hN,I,N,Ei,
3. When all three input sequences have the same length n, what is the largest n for which your program 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)
5. 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.
