South East University
CSE 376(Advance Algorithms)
Lab-9 Manual
(Implementation of LCS and LIS using Dynamic
Programming)
Course instructor
Dr. Md. Tauhid Bin Iqbal
Assistant Professor
Department of Computer Science & Engineering
Longest Common Subsequence (LCS)
Problem Statement
Given two sequences (often strings) X and Y, find the length of their Longest Common
Subsequence (LCS)—a subsequence that appears in the same relative order (not necessarily
contiguous) in both X and Y. Optionally, also output one such LCS.
Input: Two sequences X (length nnn) and Y (length mmm).
Output (minimum): An integer L = length of the LCS of X and Y.
Output (optional): One valid LCS string/sequence of length L.
example
Input:
X=X =X= "ABCBDAB", Y=Y =Y= "BDCABA"
Output:
Length = 4
One LCS = "BCBA" (others like "BDAB" are also valid)
Longest Common Subsequence (LCS)
Sudo code LCS-Length(X, Y)
m ← length(X)
n ← length(Y)
for i ← 0 to m do
c[i,0] ← 0
for j ← 0 to n do
c[0,j] ← 0
for i ← 1 to m do
for j ← 1 to n do
if X[i] = Y[j] then
c[i,j] ← c[i-1, j-1] + 1
else
c[i,j] ← max(c[i-1, j], c[i, j-1])
return c
Time Complexity of O(mn)
Longest Increasing Subsequence (LIS)
Problem Statement
Given a sequence of numbers A=[a1,a2,…,an]A = [a_1, a_2, \dots, a_n]A=[a1,a2,…,an], find the
length of the Longest Increasing Subsequence (LIS)—a subsequence where each next element
is strictly larger than the previous. Optionally, also output one such LIS.
Input: A sequence of n integers.
Output (minimum): An integer L = length of the LIS in A
Output (optional): One valid LIS of length L.
input:
A=[10,9,2,5,3,7,101,18]A = [10, 9, 2, 5, 3, 7, 101, 18]A=[10,9,2,5,3,7,101,18]
Output:
Length = 4
One LIS = [2, 3, 7, 18] (others like [2, 5, 7, 18] are also valid)
Sudo Code
Input: Array A[1..n]
Output: Length of the Longest Increasing Subsequence (LIS)
Initialize an array LIS[1..n]
For i from 1 to n:
LIS[i] ← 1 // Every element is a subsequence of length 1
For i from 2 to n:
For j from 1 to i-1:
If A[i] > A[j] then
LIS[i] ← max(LIS[i], LIS[j] + 1)
max_length ← 0
For i from 1 to n:
max_length ← max(max_length, LIS[i])
Return max_length
