ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
For which of the following inputs would Kadane's algorithm produce a WRONG output?
{1,0,-1}
{-1,-2,-3}
{1,2,3}
{0,0,0}
Kadane's algorithm doesn't work for all negative numbers. So, the answer is {-1,-2,-3}.
For which of the following inputs would Kadane's algorithm produce the INCORRECT output?
{0,1,2,3}
{-1,0,1}
{-1,-2,-3,0}
{-4,-3,-2,-1}
Kadane's algorithm works if the input array contains at least one non-negative element. Every element in the array {-4,-3,-2,-1} is negative. Hence Kadane's algorithm won't work.
Kadane's algorithm uses which of the following techniques?
Divide and conquer
Dynamic programming
Recursion
Greedy algorithm
Kadane's algorithm uses dynamic programming.
Kadane's algorithm is used to find ____________
Longest increasing subsequence
Longest palindrome subsequence
Maximum sub-array sum
Longest decreasing subsequence
Kadane's algorithm is used to find the maximum sub-array sum for a given array.
Which technique is used by line 7 of the above code?
Greedy
Recursion
Memoization
Overlapping subproblems
Line 7 stores the current value that is calculated, so that the value can be used later directly without calculating it from scratch. This is memoization.
Which property is shown by line 7 of the above code?
Optimal substructure
Overlapping subproblems
Both overlapping subproblems and optimal substructure
Greedy substructure
We find the nth fibonacci term by finding previous fibonacci terms, i.e. by solving subproblems. Hence, line 7 shows the optimal substructure property.
What is the space complexity of the recursive implementation used to find the nth fibonacci term?
O(1)
O(n)
O(n^{2})
O(n^{3})
The recursive implementation doesn't store any values and calculates every value from scratch. So, the space complexity is O(1).
Which property is shown by the above function calls?
Memoization
Optimal substructure
Overlapping subproblems
Greedy
From the function calls, we can see that fibonacci(4) is calculated twice and fibonacci(3) is calculated thrice. Thus, the same subproblem is solved many times and hence the function calls show the overlapping subproblems property.
What is the time complexity of the recursive implementation used to find the nth fibonacci term?
O(1)
O(n^{2})
O(n!)
Exponential
The recurrence relation is given by (fibo(n) = fibo(n - 1) + fibo(n - 2)). So, the time complexity is given by:
(T(n) = T(n - 1) + T(n - 2))
Approximately,
T(n) = 2 * T(n - 1)
= 4 * T(n - 2)
= 8 * T(n - 3)
:
:
:
= 2^{k} * T(n - k)
This recurrence will stop when n - k = 0
i.e. n = k
Therefore, (T(n) = 2^{n} * O(0) = 2^{n})
Hence, it takes exponential time.
It can also be proved by drawing the recursion tree and counting the number of leaves.
Which line would make the implementation complete?
fibo(n) + fibo(n)
fibo(n) + fibo(n - 1)
fibo(n - 1) + fibo(n + 1)
fibo(n - 1) + fibo(n - 2)
Consider the first five terms of the fibonacci sequence: 0,1,1,2,3. The 6th term can be found by adding the two previous terms, i.e. fibo(6) = fibo(5) + fibo(4) = 3 + 2 = 5. Therefore,the nth term of a fibonacci sequence would be given by:
fibo(n) = fibo(n-1) + fibo(n-2).
The following sequence is a fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21,..... Which technique can be used to get the nth fibonacci term?
Recursion
Dynamic programming
A single for loop
Recursion, Dynamic Programming, For loops
Each of the above mentioned methods can be used to find the nth fibonacci term.
Which of the following lines should be added to complete the above code?
arr[i-1][j] = min
arr[i][j-1] = min
arr[i-1][j-1] = min
arr[i][j] = min
The line arr[i][j] = min completes the above code.
Consider the two strings ""(empty string) and "abcd". What is the edit distance between the two strings?
0
4
2
3
The empty string can be transformed into "abcd" by inserting "a", "b", "c" and "d" at appropriate positions. Thus, the edit distance is 4.
Consider the strings "monday" and "tuesday". What is the edit distance between the two strings?
3
4
5
6
"monday" can be converted to "tuesday" by replacing "m" with "t", "o" with "u", "n" with "e" and inserting "s" at the appropriate position. So, the edit distance is 4.
Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.
True
False
Consider the strings "abcd" and "efghi". The string "efghi" can be converted to "abcd" by deleting "i" and converting "efgh" to "abcd". The cost of transformation is 5, which is equal to the length of the larger string.
In which of the following cases will the edit distance between two strings be zero?
When one string is a substring of another
When the lengths of the two strings are equal
When the two strings are equal
The edit distance can never be zero
The edit distance will be zero only when the two strings are equal.
Which of the following is an application of the edit distance problem?
Approximate string matching
Spelling correction
Similarity of DNA
Approximate string matching, Spelling Correction and Similarity of DNA
All of the mentioned are the applications of the edit distance problem.
The edit distance satisfies the axioms of a metric when the costs are non-negative.
True
False
d(s,s) = 0, since each string can be transformed into itself without any change.
d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.
d(s1, s2) = d(s2, s1)
(d(s1, s3) <= d(s1, s2) + d(s2, s3))
Thus, the edit distance satisfies the axioms of a metric.
Which of the following methods can be used to solve the edit distance problem?
Recursion
Dynamic programming
Both dynamic programming and recursion
Greedy Algorithm
Both dynamic programming and recursion can be used to solve the edit distance problem.
Which of the following problems should be solved using dynamic programming?
Mergesort
Binary search
Longest common subsequence
Quicksort
The longest common subsequence problem has both, optimal substructure and overlapping subproblems. Hence, dynamic programming should be used the solve this problem.
