Scribd
Upload
17 views13 pages

Longest Common Subsequence Algorithm

The document discusses the longest common subsequence problem. It provides an introduction to the problem, describes the iterative process to solve it with an example, and runs in O(N^2) time complexity. Binary search is also briefly discussed, outlining the basic steps, advantages of being faster than linear search and requiring sorted data, and potential disadvantages if random access is not supported.

Uploaded by

Mehedi Hasan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
17 views13 pages

Longest Common Subsequence Algorithm

The document discusses the longest common subsequence problem. It provides an introduction to the problem, describes the iterative process to solve it with an example, and runs in O(N^2) time complexity. Binary search is also briefly discussed, outlining the basic steps, advantages of being faster than linear search and requiring sorted data, and potential disadvantages if random access is not supported.

Uploaded by

Mehedi Hasan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd

Welcome

Longest Common Subsequence


Presented By Presented To

Mehedi Hasan
ID: 213002089

Meherin Islam
ID: 213002125

Moinul Hassan Md. Rafiqul Islam


ID: 213002013 Lecturer
Department of CSE
Green University of Bangladesh
TABLE OF CONTENTS

01 02 03

Iteration
Introduction Algorithm
process
Longest common subsequence

Given two sequences X and


Time Y over a set S, the longest
complexity common subsequence
problem asks to find a
common subsequence of X
O(N ^ 2) and T that is of maximum
length.
Given string X Given string Y

CDDCDC DDDCDC
Iteration
Process

X C D D C D C If Match found
1+ value
X 0 0 0 0 0 0 0
D 0 0 1 1 1 1 1
If not a match
D 0 0 1 1 2 2 2
D
/
0 0 1 2 2 3 3 Value from the
table
C 0 1 1 2 3 3 4
D 0 1 2 3 3 4 4
C 0 1 2 3 4 4 5
Result DDC
DC
Binary
Search
1. Begin with the mid element of the whole array
as a search key.

2. If the value of the search key is equal to the item


then return an index of the search key.

3. Or if the value of the search key is less than the


item in the middle of the interval, narrow the
interval to the lower half.

4. Otherwise, narrow it to the upper half.

5. Repeatedly check from the second point until the


value is found or the interval is empty.
ADVANTAGES DISADVANTAGES
LESS COMPARISONS REQUIRE THE DATA TO BE
THAN LINEAR SORTED
SEARCHING ALGORITHM
IF RANDOM ACCESS IS NOT
IT WORKS ON DIVIDE & SUPPORTED TEN EFFICIENCY
CONQUER PRINCIPLE MIGHT BE LOST

FASTER THAN LINEAR IT CAN BE INPLEMENTED ONLY


SEARCHING ALGORITHM FOR TWO WAY TRAVERSAL DATA
STRUCTURES
Example
THANK YOU
ANY QUESTIONS?

You might also like