CSE431/531 Project 2
You need to implement the dynamic programming algorithm for the longest common subsequence problem. You can use C++, Java or Python to implement the algorithm.
Input You need to read the input graph from the file “input.txt”. The file contains two lines,
each containing one string. You can assume each string only contains upper and lower case
letters and numbers; the length of each string is at most 1000.
Output You need to output to the file “output.txt”. The first line of the file is an integer
indicating the length of the longest common subsequence between the two strings. The second
line contains the longest common subsequence (which may not be unique).
Sample input (from the course slides)
bacdca
adbcda
Output for sample input
4
adca
Grading Here is how we grade your project. We shall post some sample test cases soon.
If you passed the sample test cases (without cheating), you will get 30% of the points. We
have some hidden test cases. These test cases are worth another 30% of the points. For the
remaining 40%, we will read your code and see if your implementation is correct (e.g., whether
your algorithm runs in quadratic time). For each test case, your algorithm needs to terminate
in reasonable amount of time (say, 5 seconds).
Submission Submit your source file via UBlearns. For convenience, please only submit one
source file, with the name LCS hfirstnamei hlastnamei hUBIDi.{cpp|py|java}, where hfirstnamei
is your first name (with initial letter capitalized) and hlastnamei is your last name (with initial
letter capitalized) and hUBIDi is your UB netID (your email address without “@buffalo.edu”).
The extension of the source file is cpp, py, or java, depending on the programming language
you use.
