ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
7 practice sets · Page 1 of 1
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.
