Given two strings (sequences of characters), the longest common subsequence (LCS) problem is to find the longest subsequence (not necessarily contiguous) that exists in both of the input strings. For example, given strings “mangoes” and “mementos”, the subsequence “mnos” is common in both and is in fact the longest common subsequence. Given two strings of sizes n1 and n2 respectively, find a dynamic programming algorithm to find the longest common subsequence in O(n1n2) time.

The [report] should include:

(1) Briefly describe the problem.

(2) Analyze the problem and give the algorithm to solve the problem. This algorithm should be based on Dynamic Programming. It is the most important part in this assignment, please describe this solution with your detailed and well-developed explanations and analysis.

(3) Introduce your program and describe how it implements the algorithm and solves the problem. Please do not copy all your codes on the report, but you could write some core codes with detailed annotations to help you illustrate your program.

(4) As a way to analyze your program/algorithm, please state the input and output of your program. And, you need to get numerous results for different input sizes.

(5) Briefly analyze the time complexity of your algorithm.

**Subject Computer Science Data Structures and Algorithms**