# Data Structure Questions and Answers – Catalan Number using Dynamic Programming

This set of Data Structure Multiple Choice Questions & Answers focuses on “Catalan Number using Dynamic Programming”.

1. Which of the following is NOT a Catalan number?
a) 1
b) 5
c) 14
d) 43

Explanation: 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.

2. Which of the following numbers is the 6th Catalan number?
a) 14
b) 429
c) 132
d) 42

Explanation: 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.

3. Which of the following is not an application of Catalan Numbers?
a) Counting the number of Dyck words
b) Counting the number of expressions containing n pairs of parenthesis
c) Counting the number of ways in which a convex polygon can be cut into triangles by connecting vertices with straight lines
d) Creation of head and tail for a given number of tosses

Explanation: 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.

4. Which of the following methods can be used to find the nth Catalan number?
a) Recursion
b) Binomial coefficients
c) Dynamic programming
d) Recursion, Binomial Coefficients, Dynamic programming

Explanation: All of the mentioned methods can be used to find the nth Catalan number.

5. The recursive formula for Catalan number is given by Cn = ∑Ci*C(n-i).
Consider the following dynamic programming implementation for Catalan numbers:

Note: Join free Sanfoundry classes at Telegram or Youtube
```#include<stdio.h>
int cat_number(int n)
{
int i,j,arr[n],k;
arr[0] = 1;
for(i = 1; i < n; i++)
{
arr[i] = 0;
for(j = 0,k = i - 1; j < i; j++,k--)
______________________;
}
return arr[n-1];

}
int main()
{
int ans, n = 8;
ans = cat_number(n);
printf("%d\n",ans);
return 0;
}```

Which of the following lines completes the above code?
a) arr[i] = arr[j] * arr[k];
b) arr[j] += arr[i] * arr[k];
c) arr[i] += arr[j] * arr[k].
d) arr[j] = arr[i] * arr[k];

Explanation: The line arr[i] += arr[j] * arr[k] reflects the recursive formula Cn = ∑Ci*C(n-i).

6. Which of the following implementations of Catalan numbers has the smallest time complexity?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal time complexity

Explanation: The time complexities are as follows:
Dynamic programming: O(n2)
Recursion: Exponential
Binomial coefficients: O(n).

7. What is the output of the following code?

```#include<stdio.h>
int cat_number(int n)
{
int i,j,arr[n],k;
arr[0] = 1;
for(i = 1; i < n; i++)
{
arr[i] = 0;
for(j = 0,k = i - 1; j < i; j++,k--)
arr[i] += arr[j] * arr[k];
}
return arr[n-1];
}
int main()
{
int ans, n = 8;
ans = cat_number(n);
printf("%d\n",ans);
return 0;
}```

a) 42
b) 132
c) 429
d) 1430

Explanation: The program prints the 8th Catalan number, which is 429.

8. Which of the following implementations of Catalan numbers has the largest space complexity(Don’t consider the stack space)?
a) Dynamic programming
b) Binomial coefficients
c) Recursion
d) All have equal space complexities

Explanation: The space complexities are as follows:
Dynamic programming: O(n)
Recursion: O(1)
Binomial coefficients: O(1).

9. What will be the value stored in arr[5] when the following code is executed?

```#include<stdio.h>
int cat_number(int n)
{
int i,j,arr[n],k;
arr[0] = 1;
for(i = 1; i < n; i++)
{
arr[i] = 0;
for(j = 0,k = i - 1; j < i; j++,k--)
arr[i] += arr[j] * arr[k];
}
return arr[n-1];
}
int main()
{
int ans, n = 10;
ans = cat_number(n);
printf("%d\n",ans);
return 0;
}```

a) 14
b) 42
c) 132
d) 429

Explanation: The 6th Catalan number will be stored in arr[5], which is 42.

10. Which of the following errors will occur when the below code is executed?

```#include<stdio.h>
int cat_number(int n)
{
int i,j,arr[n],k;
arr[0] = 1;
for(i = 1; i < n; i++)
{
arr[i] = 0;
for(j = 0,k = i - 1; j < i; j++,k--)
arr[i] += arr[j] * arr[k];
}
return arr[n-1];
}
int main()
{
int ans, n = 100;
ans = cat_number(n);
printf("%d\n",ans);
return 0;
}```

a) Segmentation fault
b) Array size too large
c) Integer value out of range
d) Array index out of range

Explanation: The 100th Catalan number is too large to be stored in an integer. So, the error produced will be integer value out of range.(It will be a logical error and the compiler wont show it).

Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.

To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]