Project Proposal by Laura Wieme and Karl Voelker Problem Description: 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 problem 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 dynamic 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. [3] [2] [1]

Download full proposal(pdf)