The goal of the longest common subsequence (LCS) problem is to find the longest subsequence that is common to each member of a given set of sequences. LCS is useful for making comparisons and finding differences. The LCS prob- lem is NP-hard for an arbitrary number of inputs, but is O(n2) for two inputs, which is the problem we will solve, using an adaptation of the traditional dy- namic programming algorithm. Since a problem that can be solved by dynamic programming tends to easily be broken down into subproblems, the longest common subsequence problem will work well as a parallel program. Full Parallel Proposal (Pdf)
Viewing entries in
Parallel