 # Java Implementation for Longest Common Subsequence Problem (LCS) and Analysis of the Algorithm

Subject Computer Science Data Structures and Algorithms

## Question

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.

## Solution Preview

This material may consist of step-by-step explanations on how to solve a problem or examples of proper writing, including the use of citations, references, bibliographies, and formatting. This material is made available for the sole purpose of studying and learning - misuse is strictly forbidden.

Description of the Problem – in this assignment it is intended to find the length of the longest common subsequence of two strings. It is not compulsory for the searched subsequence to be contiguous, but it needs to have the same relative order in both input strings. The scope of the problem is not to check all letters from one string against the letters of the other string, but to identify efficient ways for evaluating the common sub-sequences....

This is only a preview of the solution. Please use the purchase button to see the entire solution

## Related Homework Solutions

Huffman Coding Java Implementation and Performance Report \$35.00
Huffman
Coding
Report
Symbol
Frequency
Binary
Code
Prefix
Weighted
Length
Chart
Complexity
Java
Algorithm
Path
Tree
NP-Complete & Polynomial-Reducible Problems \$50.00
Computer Science
Data Structures
Algorithm
Design
NP
NP-Complete
NP-Hard
Polynomial Reducible
Bin Packing
Partition
Sum
Longest Path
Shortest Path
Instance
Reduction
Capacity
Edge
Weight
Subset
Two Dynamic Programming Algorithms: Rod Cutting & Minimum Number of Coins Change \$18.00
Dynamic
Programming
Algorithm
Complexity
Recurrence
Rod
Cut
Coin
Change
Amount
Integer
Denomination
Pseudocode
Maximum
DP
Sale
Unit
Piece
Price
Table
Bottom-up
Example
Analysis
Base
Case
Network Model Estimation Based on Linearity of Expectation and Randomization \$15.00
Network
Incoming
Outgoing
P2P
Peer-to-peer
Random
Node
Protocol
Overlay
Physics
Internet
Edge
Connection
Process
Expected
Matrix Chain Multiplication Using Dynamic Programming Algorithm \$18.00
Matrix
Chain
Multiplication
Dynamic
Programming
Algorithm
Optimal
Product
Dimension
Matrix-chain-order
Technique
Live Chats