SRL Archive - Other

http://villavu.com/forum/showthread.php?t=108634&p=1291200#post1291200

Will pay $10 for this.

Thanks, really do need!! (Thursday is deadline :(..)

Really need it and maximum of two days to go… Looks like it would take longer than an hour so I would up the 10$.

I don't have any time myself though just saying. Gotta hand in two projects Friday.

From: J J
Really need it and maximum of two days to go… Looks like it would take longer than an hour so I would up the 10$.

I don't have any time myself though just saying. Gotta hand in two projects Friday.

:l It's exam week here.. Exam on Thursday. Really though, it looks like a lot! Not sure there are going to be many takers on this one..


Anyway, after reading: http://en.wikipedia.org/wiki/Longest_common_subsequence_problem it doesn't seem too hard.. I think..


Since we are doing LCS.. the fastest possible algorithm is one that calculates the value at compile time rather than at run-time..

template<std::size_t M, std::size_t N>
struct CompileTimeLCS
{
    static constexpr int value(const char(&X)[M], const char(&Y)[N], int m = M - 1, int n = N - 1)
    {
        return (m == 0 || n == 0) ? 0 : (X[m - 1] == Y[n - 1]) ? LCS(X, Y, m - 1, n - 1) + 1 : std::max(LCS(X, Y, m, n - 1), LCS(X, Y, m - 1, n));
    }
};

const char A[] = "TGACTA";
const char B[] = "GTGCATG";
const int len = CompileTimeLCS<7, 8>::value(A, B);

int main()
{
    std::cout<<len;
}

The above is recursive and is as fast it can possibly get.. The assembly generated for the above is just the value alone. Nothing more.. Can also generate the matrix and string at compile time with little effort and some meta-templates..



Now for doing this crap in Java without recursion since Java doesn't have compile time templates or const expressions and recursion gives worse complexity..

package lcstest;

public class LCSTest {

    public static void main(String[] args) {
        String A = "TGACTA";
        String B = "GTGCATG";

        int[][] Mat = LCSMatrix(A, B);
        String result = LCSMatrixToString(Mat, A, B);
        System.out.println(result);
    }

    /**
     * Creates a Longest Common SubSequence Matrix using the Bottom-Up dynamic
     * programming approach.
     *
     * @param A First String containing a sequence.
     * @param B Second String containing a sequence.
     * @return A matrix with the Longest Common Subsequence length stored at
     * Result[A.length()][B.length()].
     */
    public static int[][] LCSMatrix(String A, String B) {
        int m = A.length() + 1;
        int n = B.length() + 1;
        int Mat[][] = new int[m][n];

        for (int I = 0; I < m; ++I) {
            for (int J = 0; J < n; ++J) {
                Mat[I][J] = (I == 0 || J == 0) ? 0 : A.charAt(I - 1) == B.charAt(J - 1) ? Mat[I - 1][J - 1] + 1 : Math.max(Mat[I - 1][J], Mat[I][J - 1]);
            }
        }
        return Mat;
    }

    /**
     * Converts a Longest Common SubSequence Matrix to a string.
     *
     * @param Mat An LCS Matrix from which to retrieve the max sequence.
     * @param A First String containing a sequence.
     * @param B Second String containing a sequence.
     * @return A string representation of the Longest Common Subsequence of A
     * and B.
     */
    public static String LCSMatrixToString(int Mat[][], String A, String B) {
        StringBuilder builder = new StringBuilder();

        for (int I = A.length(), J = B.length(); I > 0 && J > 0;) {
            if (Mat[I][J] == Mat[I - 1][J]) {
                --I;
            } else if (Mat[I][J] == Mat[I][J - 1]) {
                --J;
            } else {
                builder.append(A.charAt(I - 1));
                --I;
                --J;
            }
        }

        return builder.reverse().toString();
    }

    /**
     * Calculates the Levenshtein edit distance.
     * @param first The first string to compare.
     * @param second The second string to compare.
     * @return The amount of transformations required to transform 
     *         one string into another.
     */
    public static int levenshteinDistance(String first, String second) {
        int current[] = new int[second.length() + 1];
        int previous[] = new int[second.length() + 1];

        for (int i = 0; i < previous.length; ++i) {
            previous[i] = i;
        }

        for (int i = 0; i < first.length(); ++i) {
            current[0] = i + 1;
            for (int j = 0; j < second.length(); ++j) {
                int Cost = first.charAt(i) == second.charAt(j) ? 0 : 1;
                current[j + 1] = Math.min(Math.min(current[j] + 1, previous[j + 1] + 1), previous[j] + Cost);
            }

            int[] temp = current;
            current = previous;
            previous = temp;
        }
        return previous[second.length()];
    }
}

The above isn't that slow. It's ok I guess..

I tried to use the levenshstein edit distance to optimize the algorithm for optimal complexity using this formula I found on wiki: http://en.wikipedia.org/wiki/Hirschberg%27s_algorithm

It's just too much work.. I also don't know what is with my algorithm.. that picture you linked shows TGCA as the longest but mine prints TGAT which is one of your options in the OP.. Not sure but I think I got it right..

Using:

for (int i = 0; i < Mat.length; ++i) {
    for (int j = 0; j < Mat[0].length; ++j) {
        System.out.print(Mat[i][j] + " ");
    }
    System.out.println();
}

to print the subproblems, it prints:

0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 
0 1 1 2 2 2 2 2 
0 1 1 2 2 3 3 3 
0 1 1 2 3 3 3 3 
0 1 2 2 3 3 4 4 
0 1 2 2 3 4 4 4 

The size of the array used is [StringOne.length() + 1][StringTwo.length() + 1] or [0.. m - 1][0.. n - 1].

Tbh.. @OP, you could have done at least some of the work.. Prioritizing one assignment over another :l

I'm not going to attempt to do the whole thing or answer every question.. way too much thinking required..

Whoever wants the reward can use the above to complete it.. I got exams to study for…

Thanks for the help brandon! Willing to increase the payment to $20, the reason I didn't even look at this assignment until yesterday was because I thought it would be easy in comparison to my other assignment which it is but… way more work than I assumed.