81.
Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
A
5
B
2
C
3
D
4
Answer and explanation
Correct Answer: C — 3
level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).
ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
Given an input arr = {2,5,7,99,899}; key = 899; What is the level of recursion?
5
2
3
4
level 1: mid = 7
level 2: mid = 99
level 3: mid = 899(this is the key).
What is the advantage of recursive approach than an iterative approach?
Consumes less memory
Less code and easy to implement
Consumes more memory
More code has to be written
A recursive approach is easier to understand and contains fewer lines of code.
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)
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)
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);
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
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
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
Wagner-Fischer algorithm is used to find the edit distance between two strings.
Wagner-Fischer is a ____________ algorithm.
Brute force
Greedy
Dynamic programming
Recursive
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]
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
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)
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}
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})
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
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
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
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
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
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.