# consider the strings “pqrstpqrs” and “pratpbrqrps”. what is the length of the longest common subsequence?

### Mohammed

Guys, does anyone know the answer?

get consider the strings “pqrstpqrs” and “pratpbrqrps”. what is the length of the longest common subsequence? from screen.

## Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence? 9 8 7 6. Data Structures and Algorithms Objective type Questions and Answers.

## Discussion Forum

Que. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

a. 9 b. 8 c. 7 d. 6 Answer:7

### Confused About the Answer? Ask for Details Here

### Know Explanation? Add it Here

### Similar Questions:

You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?

Find the maximum sub-array sum for the given elements.

{-2, -1, -3, -4, -1, -2, -1, -5, -4}

The edit distance satisfies the axioms of a metric when the costs are non-negative.

Which of these are core interfaces in the collection framework. Select the one correct answer.

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?

Which of the following methods can be used to find the nth Catalan number?

Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?

Longest palindromic subsequence is an example of ______________

Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

Which of the following methods can be used to solve the matrix chain multiplication problem?

There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?

Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?

You are given infinite coins of denominations 3, 5, 7. Which of the following sum CAN be achieved using these coins?

For every non-empty string, the length of the longest palindromic subsequence is at least one.

The 0-1 Knapsack problem can be solved using Greedy algorithm.

Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

What is the time complexity of the brute force implementation of the maximum sum rectangle problem?

In linear hashing, formula used to calculate number of records if blocking factor, loading factor and file buckets are known is as

## Longest Common Subsequence Questions and Answers

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Longest Common Subsequence”. 1. Which of the following methods can be used to solve the longest common subsequence problem? a) Recursion b) Dynamic programming c) Both recursion and dynamic programming d) Greedy algorithm 2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is ... Read more

## Data Structure Questions and Answers – Longest Common Subsequence

« Prev Next »

This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Longest Common Subsequence”.

1. Which of the following methods can be used to solve the longest common subsequence problem?

a) Recursion

b) Dynamic programming

c) Both recursion and dynamic programming

d) Greedy algorithm View Answer

2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

a) 9 b) 8 c) 7 d) 6 View Answer

3. Which of the following problems can be solved using the longest subsequence problem?

a) Longest increasing subsequence

b) Longest palindromic subsequence

c) Longest bitonic subsequence

d) Longest decreasing subsequence

View Answer

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

advertisement

4. Longest common subsequence is an example of ____________

a) Greedy algorithm

b) 2D dynamic programming

c) 1D dynamic programming

d) Divide and conquer

View Answer

5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?

a) O(n) b) O(n2) c) O(n3) d) O(2n) View Answer

Check this: Programming Books | Computer Science Books

6. Consider the following dynamic programming implementation of the longest common subsequence problem:

#include#includeint max_num(int a, int b)

{ if(a > b) return a; return b; }

int lcs(char *str1, char *str2)

{ int i,j,len1,len2;

len1 = strlen(str1);

len2 = strlen(str2);

int arr[len1 + 1][len2 + 1];

for(i = 0; i <= len1; i++)

arr[i][0] = 0;

for(i = 0; i <= len2; i++)

arr[0][i] = 0;

for(i = 1; i <= len1; i++)

{

for(j = 1; j <= len2; j++)

{

if(str1[i-1] == str2[j - 1])

______________; else

arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);

} }

return arr[len1][len2];

} int main() {

char str1[] = " abcedfg", str2[] = "bcdfh";

int ans = lcs(str1,str2);

printf("%d",ans); return 0; }

Which of the following lines completes the above code?

a) arr[i][j] = 1 + arr[i][j].

b) arr[i][j] = 1 + arr[i – 1][j – 1].

c) arr[i][j] = arr[i – 1][j – 1].

d) arr[i][j] = arr[i][j].

View Answer advertisement

7. What is the time complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

#includeadvertisement

#includeint max_num(int a, int b)

{ if(a > b) return a; return b; }

int lcs(char *str1, char *str2)

{ int i,j,len1,len2;

len1 = strlen(str1);

len2 = strlen(str2);

int arr[len1 + 1][len2 + 1];

for(i = 0; i <= len1; i++)

arr[i][0] = 0;

for(i = 0; i <= len2; i++)

arr[0][i] = 0;

for(i = 1; i <= len1; i++)

{

for(j = 1; j <= len2; j++)

{

if(str1[i-1] == str2[j - 1])

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

else

arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);

} }

return arr[len1][len2];

} int main() {

char str1[] = " abcedfg", str2[] = "bcdfh";

int ans = lcs(str1,str2);

printf("%d",ans); return 0; } a) O(n) b) O(m) c) O(m + n) d) O(mn) View Answer

8. What is the space complexity of the following dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

#include#includeint max_num(int a, int b)

{ if(a > b) return a; return b; }

int lcs(char *str1, char *str2)

{ int i,j,len1,len2;

len1 = strlen(str1);

len2 = strlen(str2);

int arr[len1 + 1][len2 + 1];

for(i = 0; i <= len1; i++)

arr[i][0] = 0;

for(i = 0; i <= len2; i++)

arr[0][i] = 0;

for(i = 1; i <= len1; i++)

{

for(j = 1; j <= len2; j++)

{

if(str1[i-1] == str2[j - 1])

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

else

arr[i][j] = max_num(arr[i - 1][j], arr[i][j - 1]);

} }

return arr[len1][len2];

} int main() {

char str1[] = " abcedfg", str2[] = "bcdfh";

int ans = lcs(str1,str2);

printf("%d",ans); return 0; } a) O(n) b) O(m) c) O(m + n) d) O(mn) View Answer

9. What is the output of the following code?

#include#includeint max_num(int a, int b)

{ if(a > b) return a; return b; }

int lcs(char *str1, char *str2)

{ int i,j,len1,len2;

len1 = strlen(str1);

len2 = strlen(str2);

int arr[len1 + 1][len2 + 1];

for(i = 0; i <= len1; i++)

arr[i][0] = 0;

for(i = 0; i <= len2; i++)

arr[0][i] = 0;

for(i = 1; i <= len1; i++)

{

for(j = 1; j <= len2; j++)

{

if(str1[i-1] == str2[j - 1])

## PT 2 Flashcards

Study with Quizlet and memorize flashcards containing terms like Which of the following methods can be used to solve the longest common subsequence problem? a) Recursion b) Dynamic programming c) Both recursion and dynamic programming d) Greedy algorithm, Consider the strings "PQRSTPQRS" and "PRATPBRQRPS". What is the length of the longest common subsequence? a) 9 b) 8 c) 7 d) 6, Which of the following problems can be solved using the longest subsequence problem? a) Longest increasing subsequence b) Longest palindromic subsequence c) Longest bitonic subsequence d) Longest decreasing subsequence and more.

## PT 2

Term 1 / 60

Which of the following methods can be used to solve the longest common subsequence problem?

a) Recursion

b) Dynamic programming

c) Both recursion and dynamic programming

d) Greedy algorithm

Click the card to flip 👆

Definition 1 / 60 c

Click the card to flip 👆

Created by Viet_Tung_N

### Terms in this set (60)

Which of the following methods can be used to solve the longest common subsequence problem?

a) Recursion

b) Dynamic programming

c) Both recursion and dynamic programming

d) Greedy algorithm c

Consider the strings "PQRSTPQRS" and "PRATPBRQRPS". What is the length of the longest common subsequence?

a) 9 b) 8 c) 7 d) 6 c

Which of the following problems can be solved using the longest subsequence problem?

a) Longest increasing subsequence

b) Longest palindromic subsequence

c) Longest bitonic subsequence

d) Longest decreasing subsequence

b

Longest common subsequence is an example of ____________

a) Greedy algorithm

b) 2D dynamic programming

c) 1D dynamic programming

d) Divide and conquer

b

What is the time complexity of the brute force algorithm used to find the longest common subsequence?

a) O(n) b) O(n^2) c) O(n^3) d) O(2^n) d

Which of the following is the longest common subsequence between the strings "hbcfgmnapq" and "cbhgrsfnmq" ?

a) hgmq b) cfnq c) bfmq d) fgmna d

Which of the following is/are property/properties of a dynamic programming problem?

a) Optimal substructure

b) Overlapping subproblems

c) Greedy approach

d) Both optimal substructure and overlapping subproblems

d

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

a) Overlapping subproblems

b) Optimal substructure

c) Memoization d) Greedy b

If a problem can be broken into subproblems which are reused several times, the problem possesses ____________ property.

a) Overlapping subproblems

b) Optimal substructure

c) Memoization d) Greedy a

If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

a) Dynamic programming

b) Greedy

c) Divide and conquer

d) Recursion c

When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don't take advantage of overlapping subproblems.

a) True b) False a

A greedy algorithm can be used to solve all the dynamic programming problems.

a) True b) False b

In dynamic programming, the technique of storing the previously calculated values is called ___________

a) Saving value property

b) Storing value property

c) Memoization d) Mapping c

When a top-down approach of dynamic programming is applied to a problem, it usually _____________

a) Decreases both, the time complexity and the space complexity

b) Decreases the time complexity and increases the space complexity

c) Increases the time complexity and decreases the space complexity

d) Increases both, the time complexity and the space complexity

b

Which of the following problems is NOT solved using dynamic programming?

a) 0/1 knapsack problem

b) Matrix chain multiplication problem

c) Edit distance problem

d) Fractional knapsack problem

d

Which of the following problems should be solved using dynamic programming?

a) Mergesort b) Binary search

c) Longest common subsequence

d) Quicksort c

Which of the following methods can be used to solve the matrix chain multiplication problem?

a) Dynamic programming

b) Brute force c) Recursion

d) Dynamic Programming, Brute force, Recursion

d

Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?

a) dp[i,j] = 1 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]}

b) dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]}

c) dp[i,j] = 1 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]**mat[k]**mat[j].

d) dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]**mat[k]**mat[j].

d

Consider the two matrices P and Q which are 10 x 20 and 20 x 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

a) 10*20 b) 20*30 c) 10*30 d) 10**20**30 d

Consider the matrices P, Q and R which are 10 x 20, 20 x 30 and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?

a) 18000 b) 12000 c) 24000 d) 32000 a

Consider the matrices P, Q, R and S which are 20 x 15, 15 x 30, 30 x 5 and 5 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the four matrices?

a) 6050 b) 7500 c) 7750 d) 12000 c

Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?

Guys, does anyone know the answer?