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)
Correct Answer: C — O(mn)
Explanation:
The space complexity of the above Wagner-Fischer algorithm is O(mn).
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)
Correct Answer: C — O(mn)
Explanation:
The time complexity of the Wagner-Fischer algorithm is O(mn).
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);
Correct Answer: C — min = arr[i-1][j-1].
Explanation:
The line min = arr[i-1][j-1] completes the above code.
For which of the following pairs of strings is the edit distance maximum?
sunday & monday
monday & tuesday
tuesday & wednesday
wednesday & thursday
Correct Answer: D — wednesday & thursday
Explanation:
The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and 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
Correct Answer: B — 2
Explanation:
The string "abcd" can be changed to "acbd" by substituting "b" with "c" and "c" with "b". Thus, the edit distance is 2.
Wagner-Fischer algorithm is used to find ____________
Longest common subsequence
Longest increasing subsequence
Edit distance between two strings
Longest decreasing subsequence
Correct Answer: C — Edit distance between two strings
Explanation:
Wagner-Fischer algorithm is used to find the edit distance between two strings.
Wagner-Fischer is a ____________ algorithm.
Brute force
Greedy
Dynamic programming
Recursive
Correct Answer: C — Dynamic programming
Explanation:
Wagner-Fischer belongs to the dynamic programming type of algorithms.
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]
Correct Answer: A — prices[j-1] + max_val[tmp_idx]
Explanation:
prices[j-1] + max_val[tmp_idx] completes the code.
For every rod cutting problem there will be a unique set of pieces that give the maximum price.
True
False
Correct Answer: B — False
Explanation:
Consider a rod of length 3. The prices are {2,3,6} for lengths {1,2,3} respectively. The pieces {1,1,1} and {3} both give the maximum value of 6.
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)
Correct Answer: A — max_price, prices[i] + rod_cut(prices,len - i - 1)
Explanation:
max_price, prices[i] + rod_cut(prices,len - i - 1) completes the above code.
Which of these pieces give the maximum price?
{1,2,7}
{10}
{2,2,6}
{1,4,5}
Correct Answer: C — {2,2,6}
Explanation:
The pieces {2,2,6} give the maximum value of 27.
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})
Correct Answer: D — O(2^{n})
Explanation:
The brute force implementation finds all the possible cuts. This takes O(2^{n}) time.
What is the maximum value that you can get after cutting the rod and selling the pieces?
10
11
12
13
Correct Answer: C — 12
Explanation:
The pieces {1,2 2} give the maximum value of 12.
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
Correct Answer: D — Brute force, Dynamic programming and Recursion
Explanation:
Brute force, Dynamic programming and Recursion can be used to solve the rod cutting problem.
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
Correct Answer: D — No change is required
Explanation:
None of the above mentioned "for" loops can be used instead of the inner for loop. Note, for(j = idx + 1; (j < len && j <= arr[idx] + idx); j++) covers the same range as the inner for loop but it produces the wrong output because the indexing inside the loops changes as "j" takes different values in the two "for" loops.
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
Correct Answer: B — False
Explanation:
Consider the array {1,0,2,3,4}.
In this case, only one element is 0 but it is not possible to reach the end of the array.
For a given array, there can be multiple ways to reach the end of the array using minimum number of jumps.
True
False
Correct Answer: A — True
Explanation:
Consider the array {1,2,3,4,5}. It is possible to reach the end in the following ways: {1 -> 2 -> 3 -> 5} or {1 -> 2 -> 4 -> 5}.
In both the cases the number of jumps is 3, which is minimum. Hence, it is possible to reach the end of the array in multiple ways using minimum number of jumps.
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
Correct Answer: A — arr, strt + idx, end
Explanation:
arr, strt + idx, end should be passed as arguments.
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
Correct Answer: C — 3
Explanation:
The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.
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
Correct Answer: D — Recursion and Dynamic Programming
Explanation:
Both recursion and dynamic programming can be used to solve minimum number of jumps problem.
