ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?
3
6
12
18
Since all the elements of the 2×3 matrix are positive, the maximum sum rectangle is the matrix itself and the sum of elements is 12.
Consider a matrix in which all the elements are non-zero(at least one positive and at least one negative element). In this case, the sum of the elements of the maximum sum rectangle cannot be zero.
True
False
If a matrix contains all non-zero elements with at least one positive and at least on negative element, then the sum of elements of the maximum sum rectangle cannot be zero.
Consider the following statements and select which of the following statement are true. Statement 1: The maximum sum rectangle can be 1X1 matrix containing the largest element If the matrix size is 1X1 Statement 2: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are zero Statement 3: The maximum sum rectangle can be 1X1 matrix containing the largest element If all the elements are negative
Only statement 1 is correct
Only statement 1 and Statement 2 are correct
Only statement 1 and Statement 3 are correct
Statement 1, Statement 2 and Statement 3 are correct
If the matrix size is 1×1 then the element itself is the maximum sum of that 1×1 matrix. If all elements are zero, then the sum of any submatrix of the given matrix is zero. If all elements are negative, then the maximum element in that matrix is the highest sum in that matrix which is again 1X1 submatrix of the given matrix. Hence all three statements are correct.
In which of the following cases, the maximum sum rectangle is the 2D matrix itself?
When all the elements are negative
When all the elements are positive
When some elements are positive and some negative
When diagonal elements are positive and rest are negative
When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.
Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?
Brute force
Recursion
Dynamic programming
Brute force, Recursion, Dynamic programming
Brute force, Recursion and Dynamic programming can be used to find the submatrix that has the maximum sum.
Which of the following implementations of Catalan numbers has the largest space complexity(Don't consider the stack space)?
Dynamic programming
Binomial coefficients
Recursion
All have equal space complexities
The space complexities are as follows:
Dynamic programming: O(n)
Recursion: O(1)
Binomial coefficients: O(1).
Which of the following implementations of Catalan numbers has the smallest time complexity?
Dynamic programming
Binomial coefficients
Recursion
All have equal time complexity
The time complexities are as follows:
Dynamic programming: O(n^{2})
Recursion: Exponential
Binomial coefficients: O(n).
Which of the following lines completes the above code?
arr[i] = arr[j] * arr[k];
arr[j] += arr[i] * arr[k];
arr[i] += arr[j] * arr[k].
arr[j] = arr[i] * arr[k];
The line arr[i] += arr[j] * arr[k] reflects the recursive formula (Cn = \sumCi*C(n-i)).
Which of the following methods can be used to find the nth Catalan number?
Recursion
Binomial coefficients
Dynamic programming
Recursion, Binomial Coefficients, Dynamic programming
All of the mentioned methods can be used to find the nth Catalan number.
Which of the following is not an application of Catalan Numbers?
Counting the number of Dyck words
Counting the number of expressions containing n pairs of parenthesis
Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines
Creation of head and tail for a given number of tosses
Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines are the applications of Catalan numbers where as creation of head and tails for a given number of tosses is an application of Pascal's triangle.
Which of the following numbers is the 6th Catalan number?
14
429
132
42
Catalan numbers are given by: (2n!)/((n+1)!n!).
First Catalan number is given by n = 0.
So the 6th Catalan number will be given by n = 5, which is 42.
Which of the following is NOT a Catalan number?
1
5
14
43
Catalan numbers are given by: (2n!)/((n+1)!n!).
For n = 0, we get C0 = 1.
For n = 3, we get C3 = 5.
For n = 4, we get C4 = 14.
For n = 5, we get C3 = 42.
Which of the following lines should be added to complete the code?
arr[len][len]
len + arr[len][len]
len
len - arr[len][len]
arr[len][len] contains the length of the longest palindromic subsequence. So, len - arr[len][len] gives the minimum number of insertions required to form a palindrome.
Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?
Minimum number of jumps problem
Longest common subsequence problem
Coin change problem
Knapsack problems
A variation of longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.
Consider the string "abbccbba". What is the minimum number of insertions required to make the string a palindrome?
0
1
2
3
The given string is already a palindrome. So, no insertions are required.
Consider the string "efge". What is the minimum number of insertions required to make the string a palindrome?
0
1
2
3
The string can be converted to "efgfe" by inserting "f" or to "egfge" by inserting "g". Thus, only one insertion is required.
In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to the length of the string.
True
False
In the worst case, the minimum number of insertions to be made to convert the string into a palindrome is equal to length of the string minus one. For example, consider the string "abc". The string can be converted to "abcba" by inserting "a" and "b". The number of insertions is two, which is equal to length minus one.
In which of the following cases the minimum no of insertions to form palindrome is maximum?
String of length one
String with all same characters
Palindromic string
Non palindromic string
In string of length one, string with all same characters and a palindromic string the no of insertions is zero since the strings are already palindromes. To convert a non-palindromic string to a palindromic string, the minimum length of string to be added is 1 which is greater than all the other above cases. Hence the minimum no of insertions to form palindrome is maximum in non-palindromic strings.
Given a string, you have to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome. Which of the following methods can be used to solve the problem?
Greedy algorithm
Recursion
Dynamic programming
Both recursion and dynamic programming
Dynamic programming and recursion can be used to solve the problem.
Who created the Rabin-Karp Algorithm?
Joseph Rabin and Michael Karp
Michael Rabin and Joseph Karp
Richard Karp and Michael Rabin
Michael Karp and Richard Rabin
Rabin-Karp algorithm was invented by Richard Karp and Michael Rabin in 1987 for pattern searching in strings.
