Data Structure Questions and Answers-Wagner-Fischer Algorithm

DOWNLOAD FREE PDF <<CLICK HERE>>

Data Structure Questions and Answers-Wagner-Fischer Algorithm

Congratulations - you have completed Data Structure Questions and Answers-Wagner-Fischer Algorithm.

You scored %%SCORE%% out of %%TOTAL%%.

Your performance has been rated as %%RATING%%


Your answers are highlighted below.
Question 1 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Wagner-Fischer is a ..... algorithm.
A
Brute force
B
Greedy
C
Dynamic programming
D
Recursive
Question 1 Explanation: 
Wagner-Fischer belongs to the dynamic programming type of algorithms.

Question 2 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Wagner-Fischer algorithm is used to find .....
A
Longest common subsequence
B
Longest increasing subsequence
C
Edit distance between two strings
D
All of the mentioned
Question 2 Explanation: 
Wagner-Fischer algorithm is used to find the edit distance between two strings.

Question 3 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
What is the edit distance between the strings "abcd" and "acbd" when the allowed operations are insertion, deletion and substitution?
A
1
B
2
C
3
D
4
Question 3 Explanation: 
The string "abcd" can be changed to "acbd" by substituting "b" with "c" and "c" with "b". Thus, the edit distance is 2.

Question 4 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
For which of the following pairs of strings is the edit distance maximum?
A
sunday & monday
B
monday & tuesday
C
tuesday & wednesday
D
wednesday & thursday
Question 4 Explanation: 
The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and thursday.

Question 5 [CLICK ON ANY CHOICE TO KNOW MCQ multiple objective type questions RIGHT ANSWER]
Consider the following implementation of the Wagner-Fischer algorithm:

int get....min(int a,  int b) { if(a < b) return a; return b; } int edit....distance(char *s1,  char *s2) { int len1, len2, i, j, min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get....min(arr[i-1][j], arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) .....; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; }

Which of the following lines should be inserted to complete the above code?

A
arr[i][j] = min
B
min = arr[i-1][j-1] - 1;
C
min = arr[i-1][j-1].
D
min = arr[i-1][j-1] + 1;
Question 5 Explanation: 
The line min = arr[i-1][j-1] completes the above code.

Once you are finished, click the button below. Any items you have not completed will be marked incorrect. Get Results
There are 5 questions to complete.

DOWNLOAD FREE PDF <<CLICK HERE>>