Department of Computer Science and Engineering (CSE)
UNIVERSITY INSTITUTE OF
ENGINEERING
COMPUTER SCIENCE
ENGINEERING
Bachelor of Engineering
Design and Analysis of
Algorithms(CSH-311/ITH-311)
Topic: Longest common Subsequence DISCOVER . LEARN . EMPOWER
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
Learning Objectives & Outcomes
Objective:
• To understand the concept of Longest common
Subsequence using dynamic programming
Outcome:
• Student will understand
Find the Longest common Subsequence using dynamic
programming
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
Longest common Subsequence
• If a set of sequences are given, the longest common
subsequence problem is to find a common subsequence
of all the sequences that is of maximal length.
• The longest common subsequence problem is a classic
computer science problem, the basis of data comparison
programs such as the diff-utility, and has applications in
bioinformatics. It is also widely used by revision control
systems, such as SVN and Git, for reconciling multiple
changes made to a revision-controlled collection of files.
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
Algorithm of Longest Common Sequence
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
Example 1
LCS-LENGTH on the
sequences:
X: A,B,C,B,D,A,B and
Y: B,D,C,A,B,A
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
Algorithm for printing LCS
This procedure prints BCBA (for given example 1)
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
REFERENCES
Text books:
•Cormen, Leiserson, Rivest, Stein, “Introduction to Algorithms”, Prentice Hall of
India, 3rd edition 2012. problem, Graph coloring.
Websites:
• https://www.javatpoint.com/longest-common-sequence-algorithm
•https://www.tutorialspoint.com/design_and_analysis_of_algorithms/
design_and_analysis_of_algorithms_longest_common_subsequence.htm
University Institute of Engineering (UIE)
Department of Computer Science and Engineering (CSE)
Summary
Dynamic programming:
• Longest Common Subsequence
University Institute of Engineering (UIE)
THANK YOU
University Institute of Engineering (UIE)
