COMP3011 Assignment 2

MA Mingyu (Derek) | Oct 22, 2017
derek.ma | derek.ma@connect.polyu.hk

Question 2

In my program, I use String to store sequences \(X\), \(Y\) and \(Z\). These three strings will be read from the input file and saved in the strings and pass in functions. I use multi-dimensional arrays to save tables.

My solution uses bottom-up dynamic programming. Using bottom-up DP can let my algorithm avoid recursion and save the memory cost that recursion incurs when it builds up the call stack.

I use four integers in table \(b\) to show the directions. They are \(1\), \(2\), \(3\) and \(8\).

In this program, I use two tables to store the situations in the processing. Table \(c\) is for saving the length of an LCS of corresponding subsequence, table \(b\) is for saving the subproblem in the \(c\) table which gives the maximum value. The table \(c\) can let me know the length of LCS. According to the value in table \(b\), I can use direction in table \(b\) to retrieve a LCS. The process is shown in my printLCS3 function.

Question 3

The time complexity of my algorithm is \(O(mno)\) if \(m\), \(n\) and \(o\) stands for the length of sequences of \(X\), \(Y\) and \(Z\).

The space complexity of my algorithm is \(O(mno)\) if \(m\), \(n\) and \(o\) stands for the length of sequences of \(X\), \(Y\) and \(Z\).

Largest \(n\) that my program can manages to compute a solution is 592. The calculation time is around 5.88s. (on Macbook) In my opinion, the running out of memory is the main issue. All calculation within memory limit can be finished in reasonable time, i.e. less than or around 6s.

Question 4

An example:

X: 00000000
Y: 00000010
Z: 00000001

The LCS \(W\) of \(Y\) and \(Z\) can be either 000 0000 or 000 0001.

My program based on dynamic programming gives the result of \(W\): 000 0001. The the LCS of \(X\) and \(W\) is 00 0000 with length 6.

While, the optimal solution for LCS of these three strings should be 000 0000 with length 7. This optimal solution can be retrieved using the program in Question 1.

Check this result by running this program:
https://github.com/derekmma/lcs-dp-java/blob/master/LCS_2Str.java

Optimal solution can be got from the LCS algorithm for three strings in Question 1:
https://github.com/derekmma/lcs-dp-java/blob/master/LCS14110562D.java

Question 5

The table shows the result of the experiments:

# \(n\) \(A(n)\) \(A(n)/n\)
1 40 27.3 .6825
2 100 71.2 .712
3 160 113.9 .711875
4 220 158.5 .720454545
5 280 204.8 .731428571
6 340 245.7 .722647059
7 400 294.5 .73625
8 460 337.4 .733478261
9 520 382.4 .735384615
10 580 427.2 .736551724

We can conclude from the table that \(A(n)/n\) seems converge to a constant around \(0.74\). While due to the largest number in my experiment is only 580, the converge number may larger than \(0.74\) when the \(n\) is even larger.