1.
What is the space complexity of the above implementation of Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
A
O(1)
B
O(n+m)
C
O(mn)
D
O(nlogm)
Loading practice questions
157 practice sets · Page 1 of 8
What is the space complexity of the above implementation of Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
What is the time complexity of the Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
Which of the following lines should be inserted to complete the above code?
arr[i][j] = min
(min = arr[i-1][j-1] - 1);
min = arr[i-1][j-1].
(min = arr[i-1][j-1] + 1);
For which of the following pairs of strings is the edit distance maximum?
sunday & monday
monday & tuesday
tuesday & wednesday
wednesday & thursday
What is the edit distance between the strings "abcd" and "acbd" when the allowed operations are insertion, deletion and substitution?
1
2
3
4
Wagner-Fischer algorithm is used to find ____________
Longest common subsequence
Longest increasing subsequence
Edit distance between two strings
Longest decreasing subsequence
Wagner-Fischer is a ____________ algorithm.
Brute force
Greedy
Dynamic programming
Recursive
Which line will complete the ABOVE code?
prices[j-1] + max_val[tmp_idx]
prices[j] + max_val[tmp_idx]
prices[j-1] + max_val[tmp_idx - 1]
prices[j] + max_val[tmp_idx - 1]
For every rod cutting problem there will be a unique set of pieces that give the maximum price.
True
False
Complete the above code.
max_price, prices[i] + rod_cut(prices,len - i - 1)
max_price, prices[i - 1].
max_price, rod_cut(prices, len - i - 1)
max_price, prices[i - 1] + rod_cut(prices,len - i - 1)
Which of these pieces give the maximum price?
{1,2,7}
{10}
{2,2,6}
{1,4,5}
Consider the brute force implementation of the rod cutting problem in which all the possible cuts are found and the maximum value is calculated. What is the time complexity of this brute force implementation?
O(n^{2})
O(n^{3})
O(nlogn)
O(2^{n})
What is the maximum value that you can get after cutting the rod and selling the pieces?
10
11
12
13
Given a rod of length n and the selling prices of all pieces smaller than equal to n, find the most beneficial way of cutting the rod into smaller pieces. This problem is called the rod cutting problem. Which of these methods can be used to solve the rod cutting problem?
Brute force
Dynamic programming
Recursion
Brute force, Dynamic programming and Recursion
Which of the following "for" loops can be used instead of the inner for loop so that the output doesn't change?
for(j = 1; j < arr[idx] + len; j++)
for(j = 0; j < arr[idx] - len; j++)
for(j = idx + 1; (j < len && j <= arr[idx] + idx); j++)
No change is required
For any array, given that at most one element is non-zero, it is ALWAYS possible to reach the end of the array using minimum jumps.
True
False
For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
True
False
Which of these arguments should be passed by the min_jumps function represented by the blanks?
arr, strt + idx, end
arr + idx, strt, end
arr, strt, end
arr, strt, end + idx
Consider the following array: {1, 3, 5, 8, 9, 2, 6, 7, 6} What is the minimum number of jumps required to reach the end of the array?
1
2
3
4
You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem?
Dynamic Programming
Greedy Algorithm
Recursion
Recursion and Dynamic Programming