[go: up one dir, main page]
Scribd
Upload
15 views8 pages

B306 DAA Lab Manual Exp 7

The document is a lab manual for an experiment on the implementation and analysis of the Dynamic Approach Design paradigm through the Longest Common Subsequence (LCS) problem. It outlines the aim, prerequisites, expected outcomes, and provides a theoretical background along with a brute-force and dynamic programming approach to solve the LCS problem. Additionally, it includes software code, input/output examples, observations, practice questions, and sections for student conclusions and curiosities.

Uploaded by

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

B306 DAA Lab Manual Exp 7

The document is a lab manual for an experiment on the implementation and analysis of the Dynamic Approach Design paradigm through the Longest Common Subsequence (LCS) problem. It outlines the aim, prerequisites, expected outcomes, and provides a theoretical background along with a brute-force and dynamic programming approach to solve the LCS problem. Additionally, it includes software code, input/output examples, observations, practice questions, and sections for student conclusions and curiosities.

Uploaded by

deoreg1386
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

SVKM’s NMIMS

MPSTME/School of Technology Management & Engineering,


Computer Engineering Department
Program: MBA Tech/BTECH. Sem IV

Design and Analysis of Algorithms


LAB Manual
PART A
(PART A: TO BE REFERRED BY STUDENTS)

Experiment No.07
A.1 Aim:
Implementation and Analysis of Dynamic Approach Design paradigm-
through Longest Common Subsequence problem. Find the longest
common subsequence among the two given strings X [1 . . . m] and y [1 . .
. n].

A.2 Prerequisite:
1. Knowledge of Array Handling and

2. Concept of Dynamic Approach.

3. Knowledge of recursive programming.

A.3 Outcome:
After successful completion of this experiment students will be able to,

1. Understanding the dynamic programming strategy significance

2. Analyse the time and space complexities of the dynamic programming approach for the LCS
problem

3. With Implementation finds the longest common subsequence of the given two strings.
A.4 Theory:
Given two sequences X[1 . . m] and Y[1 . . n], find a longest subsequence common to them
both.

Brute-force LCS algorithm


Check every subsequence of X [1…m] to see if it is also a subsequence of Y[1 . . n].
Analysis

 Checking = O (n) time per subsequence.


 2m2m
Sub-sequences of X (each bit-vector of length m determines a distinct subsequence of x).
 Worst-case running time = O(n∗2m)
= exponential time.

Towards a better algorithm Simplification: Dynamic programming based


LCS
1. Look at the length of a longest-common subsequence.
2. Extend the algorithm to find the LCS itself
Strategy: Consider prefixes of X and Y.
• Define c [i, j] = | LCS(X [1 . . i], Y[1 . . j])|.
• Then, c [m, n] = | LCS(X, Y)|.
Recursive formulation

For instance:

If x and y values are equal then


Otherwise

Max of these two locations.

LCS Bottom Approach

LCS-Length(X, Y)

1. m = length(X) // get the # of symbols in X

2. n = length(Y) // get the # of symbols in Y

3. for i = 1 to m c[i,0] = 0 // special case: Y0

4. for j = 1 to n c[0,j] = 0 // special case: X0

5. for i = 1 to m // for all Xi

6. for j = 1 to n // for all Yj

7. if ( Xi == Yj )

8. c[i,j] = c[i-1,j-1] + 1

9. else c[i,j] = max( c[i-1,j], c[i,j-1] )

10. return c
Numerical based example:

X = ABCB; m = |X| = 4

Y = BDCAB; n = |Y| = 5

Allocate array c[5,4]

Step 3 Step4

Repeat step 3 and 4 to fill the all the elements in matrix


PART B
(PART B : TO BE COMPLETED BY STUDENTS)

(Students must submit the soft copy as per following segments within two hours of the
practical.
The soft copy must be uploaded on the Portal.)

Program: B-Tech CE 2nd year Sem: 4th

Roll No. B306 Name: Bhargav Patil

Division: B Batch : B1

Date of Experiment: Date of Submission:

Grade :

B.1 Software Code written by student:


#include <iostream>

#include <vector>

#include <string>

using namespace std;

string findLCS(string X, string Y) {

int m = X.length();

int n = Y.length();

vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));


for (int i = 1; i <= m; i++) {

for (int j = 1; j <= n; j++) {

if (X[i - 1] == Y[j - 1]) {

dp[i][j] = dp[i - 1][j - 1] + 1;

} else {

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

int i = m, j = n;

string lcs_str = "";

while (i > 0 && j > 0) {

if (X[i - 1] == Y[j - 1]) {

lcs_str = X[i - 1] + lcs_str;

i--;

j--;

} else if (dp[i - 1][j] > dp[i][j - 1]) {

i--;

} else {

j--;

return lcs_str;

int main() {

string X = "ABCB";

string Y = "BDCAB";
string lcs_result = findLCS(X, Y);

cout << "Longest Common Subsequence: " << lcs_result <<


endl;

cout << "Length of LCS: " << lcs_result.length() << endl;

return 0;

B.2 Input and Output:

B.3 Observations and learning:


(Students are expected to comment on the output obtained with clear observations and
learning for each task/ sub part assigned)

B.4. Practice Questions:


1. Implement and analyze the time and space complexity of the longest common subsequence
problem through the dynamic approach.
2. Find the longest common subsequence’s for below given input strings and compare your
solution with output of above code.
a. X= [E, B, T, B, C, A, D, F] and Y= [A, B, B, C, D, G, F]
b. X= [A, B, C, B, D, A, B] and Y= [B, D, C, A, B, A]
c. X=your name and Y= your best friend's name

B.5 Conclusion:

B.6 Question of Curiosity


(To be answered by student based on the practical performed and
learning/observations)
1. How to find the longest palindromic sequence in a given string through
LCS.
2. Enlist the solution approaches to find the longest common sequences.

************************

You might also like