# Dynamic Programming MCQ

1. Which of the following is/are property/properties of a dynamic programming problem?

a) Optimal substructure

b) Overlapping subproblems

c) Greedy approach

d) Both optimal substructure and overlapping subproblems

Answer: d

A problem that can be solved using dynamic programming possesses overlapping subproblems as well as optimal substructure properties.

2. If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses ____________ property.

a) Overlapping subproblems

b) Optimal substructure

c) Memoization

d) Greedy

Answer: b

If an optimal solution can be created for a problem by constructing optimal solutions for its subproblems, the problem possesses the Optimal substructure property.

The optimal substructure is the property in which an optimal solution is found for the problem by constructing optimal solutions for the subproblems.

3. If a problem can be broken into subproblems that are reused several times, the problem possesses ____________ property.

a) Overlapping subproblems

b) Optimal substructure

c) Memoization

d) Greedy

Answer: a

If a problem can be broken into subproblems that are reused several times, the problem possesses the Overlapping subproblems property.

Overlapping subproblems is the property in which the value of a subproblem is used several times.

4. If a problem can be solved by combining optimal solutions to non-overlapping problems, the strategy is called _____________

a) Dynamic programming

b) Greedy

c) Divide and conquer

d) Recursion

Answer: c

In divide and conquer, the problem is divided into smaller non-overlapping subproblems and an optimal solution for each of the subproblems is found. The optimal solutions are then combined to get a globally optimal solution. For example, mergesort uses a divide and conquer strategy.

5. When dynamic programming is applied to a problem, it takes far less time as compared to other methods that don’t take advantage of overlapping subproblems.

a) True

b) False

Answer: a

Dynamic programming calculates the value of a subproblem only once, while other methods that don’t take advantage of the overlapping subproblems property may calculate the value of the same subproblem several times. So, dynamic programming saves the time of recalculation and takes far less time as compared to other methods that don’t take advantage of the overlapping subproblems property.

6. A greedy algorithm can be used to solve all the dynamic programming problems.

a) True

b) False

Answer: b

A greedy algorithm gives an optimal solution for all subproblems, but when these locally optimal solutions are combined it may NOT result in a globally optimal solution.

Hence, a greedy algorithm CAN NOT be used to solve all the dynamic programming problems.

7. In dynamic programming, the technique of storing the previously calculated values is called ___________

a) Saving value property

b) Storing value property

c) Memoization

d) Mapping

Answer: c

Memoization is the technique in which previously calculated values are stored, so that, these values can be used to solve other subproblems.

8. When a top-down approach of dynamic programming is applied to a problem, it usually _____________

a) Decreases both, the time complexity and the space complexity

b) Decreases the time complexity and increases the space complexity

c) Increases the time complexity and decreases the space complexity

d) Increases both, the time complexity and the space complexity

Answer: b

The top-down approach uses the memoization technique which stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.

9. Which of the following problems is NOT solved using dynamic programming?

a) 0/1 knapsack problem

b) Matrix chain multiplication problem

c) Edit distance problem

d) Fractional knapsack problem

Answer: d

The fractional knapsack problem is solved using a greedy algorithm.

10. Which of the following problems should be solved using dynamic programming?

a) Mergesort

b) Binary search

c) Longest common subsequence

d) Quicksort

Answer: c

The longest common subsequence problem has both, optimal substructure and overlapping subproblems. Hence, dynamic programming should be used the solve this problem.

1. 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?

a) Recursion

b) Dynamic programming

c) A single for loop

d) Recursion, Dynamic Programming, For loops

Answer: d

Recursion, Dynamic Programming, and For loops can be used to find the nth Fibonacci term.

2. Consider the recursive implementation to find the nth Fibonacci number:

int fibo(int n) if n <= 1 return n return __________

Which line would make the implementation complete?

a) fibo(n) + fibo(n)

b) fibo(n) + fibo(n – 1)

c) fibo(n – 1) + fibo(n + 1)

d) fibo(n – 1) + fibo(n – 2)

Answer: d

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).

3. What is the time complexity of the recursive implementation used to find the nth Fibonacci term?

a) O(1)

b) O(n2)

c) O(n!)

d) Exponential

Answer: d

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)

:

:

:

= 2k * T(n – k)

This recurrence will stop when n – k = 0

i.e. n = k

Therefore, T(n) = 2n * O(0) = 2n

Hence, it takes exponential time.

It can also be proved by drawing the recursion tree and counting the number of leaves.

4. Suppose we find the 8th term using the recursive implementation. The arguments passed to the function calls will be as follows:

fibonacci(8) fibonacci(7) + fibonacci(6) fibonacci(6) + fibonacci(5) + fibonacci(5) + fibonacci(4) fibonacci(5) + fibonacci(4) + fibonacci(4) + fibonacci(3) + fibonacci(4) + fibonacci(3) + fibonacci(3) + fibonacci(2) : : :

Which property is shown by the above function calls?

a) Memoization

b) Optimal substructure

c) Overlapping subproblems

d) Greedy

Answer: c

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.

5. What is the output of the following program?

#include int fibo(int n) { if(n<=1) return n; return fibo(n-1) + fibo(n-2); } int main() { int r = fibo(50000); printf("%d",r); return 0; }

a) 1253556389

b) 5635632456

c) Garbage value

d) Runtime error

Answer: d

The value of n is 50000. The function is recursive and its time complexity is exponential. So, the function will be called almost 250000 times.

Now, even though NO variables are stored by the function, the space required to store the addresses of these function calls will be enormous.

Stack memory is utilized to store these addresses and only a particular amount of stack memory can be used by any program.

So, after a certain function call, no more stack space will be available and it will lead to stack overflow causing a runtime error.

6. What is the space complexity of the recursive implementation used to find the nth Fibonacci term?

a) O(1)

b) O(n)

c) O(n2)

d) O(n3)

Answer: a

The recursive implementation doesn’t store any values and calculates every value from scratch. So, the space complexity is O(1).

8. What is the time complexity of the following for loop method used to compute the nth Fibonacci term?

int fibo(int n) if n == 0 return 0 else prevFib = 0 curFib = 1 for i : 1 to n-1 nextFib = prevFib + curFib prevFib = curFib curFib = nextFib return curFib

a) O(1)

b) O(n)

c) O(n2)

d) Exponential

Answer: b

To calculate the nth term, the for loop runs (n – 1) times, and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

9. What is the space complexity of the following for loop method used to compute the nth Fibonacci term?

int fibo(int n) if n == 0 return 0 else prevFib = 0 curFib = 1 for i : 1 to n-1 nextFib = prevFib + curFib prevFib = curFib curFib = nextFib return curFib

a) O(1)

b) O(n)

c) O(n2)

d) Exponential

Answer: a

To calculate the nth term, we just store the previous term and the current term and then calculate the next term using these two terms. It takes a constant space to store these two terms and hence O(1) is the answer.

12. Consider the following code to find the nth Fibonacci term using dynamic programming:

1. int fibo(int n) 2. int fibo_terms[100000] //arr to store the fibonacci numbers 3. fibo_terms[0] = 0 4. fibo_terms[1] = 1 5. 6. for i: 2 to n 7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2] 8. 9. return fibo_terms[n]

Which technique is used by line 7 of the above code?

a) Greedy

b) Recursion

c) Memoization

d) Overlapping subproblems

Answer: c

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 memorization.

13. What is the time complexity of the following dynamic programming implementation used to compute the nth Fibonacci term?

1. int fibo(int n) 2. int fibo_terms[100000] //arr to store the fibonacci numbers 3. fibo_terms[0] = 0 4. fibo_terms[1] = 1 5. 6. for i: 2 to n 7. fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2] 8. 9. return fibo_terms[n]

a) O(1)

b) O(n)

c) O(n2)

d) Exponential

Answer: b

To calculate the nth term, the for loop runs (n – 1) times, and each time a for loop is run, it takes a constant time. Therefore, the time complexity is of the order of n.

14. What is the space complexity of the following dynamic programming implementation used to compute the nth Fibonacci term?

int fibo(int n) int fibo_terms[100000] //arr to store the fibonacci numbers fibo_terms[0] = 0 fibo_terms[1] = 1 for i: 2 to n fibo_terms[i] = fibo_terms[i - 1] + fibo_terms[i - 2] return fibo_terms[n]

a) O(1)

b) O(n)

c) O(n2)

d) Exponential

Answer: b

To calculate the nth term, we store all the terms from 0 to n – 1. So, it takes O(n) space.

1. You are given infinite coins of denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. This problem can be solved using ____________

a) Greedy algorithm

b) Dynamic programming

c) Divide and conquer

d) Backtracking

Answer: b

The coin change problem has overlapping subproblems(same subproblems are solved multiple times) and optimal substructure(the solution to the problem can be found by finding optimal solutions for subproblems). So, dynamic programming can be used to solve the coin change problem.

2. Suppose you have coins of denominations 1, 3, and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm NOT produce an optimal answer?

a) 20

b) 12

c) 6

d) 5

Answer: c

Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}.

3. Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?

a) 14

b) 10

c) 6

d) 100

Answer: d

- Using the greedy algorithm, three coins {4,1,1} will be selected to make a sum of 6. But, the optimal answer is two coins {3,3}.
- Similarly, four coins {4,4,1,1} will be selected to make a sum of 10. But, the optimal answer is three coins {4,3,3}.
- Also, five coins {4,4,4,1,1} will be selected to make a sum of 14. But, the optimal answer is four coins {4,4,3,3}.
- For a sum of 100, twenty-five coins {all 4’s} will be selected and the optimal answer is also twenty-five coins {all 4’s}.

5. You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?

a) O(N)

b) O(S)

c) O(N2)

d) O(S*N)

Answer: d

The time complexity of a dynamic programming implementation used to solve the coin change problem is O(S*N).

6. Suppose you are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the space complexity of a dynamic programming implementation used to solve the coin change problem?

a) O(N)

b) O(S)

c) O(N2)

d) O(S*N)

Answer: b

To get the optimal solution for a sum S, the optimal solution is found for each sum less than equal to S and each solution is stored. So, the space complexity is O(S).

7. You are given infinite coins of denominations 1, 3, 4. What is the total number of ways in which a sum of 7 can be achieved using these coins if the order of the coins is not important?

a) 4

b) 3

c) 5

d) 6

Answer: c

A sum of 7 can be achieved in the following ways:

{1,1,1,1,1,1,1}, {1,1,1,1,3}, {1,3,3}, {1,1,1,4}, {3,4}.

Therefore, the sum can be achieved in 5 ways.

8. You are given infinite coins of denominations 1, 3, 4. What is the minimum number of coins required to achieve a sum of 7?

a) 1

b) 2

c) 3

d) 4

Answer: b

A sum of 7 can be achieved by using a minimum of two coins {3,4}.

9. You are given infinite coins of denominations 5, 7, and 9. Which of the following sum CANNOT be achieved using these coins?

a) 50

b) 21

c) 13

d) 23

Answer: c

One way to achieve a sum of 50 is to use ten coins of 5. A sum of 21 can be achieved by using three coins of 7. One way to achieve a sum of 23 is to use two coins of 7 and one coin of 9. A sum of 13 cannot be achieved.

10. You are given infinite coins of denominations 3, 5, and 7. Which of the following sum CANNOT be achieved using these coins?

a) 15

b) 16

c) 17

d) 4

Answer: d

Sums can be achieved as follows:

15 = {5,5,5}

16 = {3,3,5,5}

17 = {3,7,7}

we can’t achieve sum=4 because our available denominations are 3,5,7 and the sum of any two denominations is greater than 4.

1. Given a one-dimensional array of integers, you have to find a sub-array with a maximum sum. This is the maximum sub-array sum problem. Which of these methods can be used to solve the problem?

a) Dynamic programming

b) Two for loops (naive method)

c) Divide and conquer

d) Dynamic programming, naïve method and Divide and conquer methods

Answer: d

Dynamic programming, naïve method and Divide and conquer methods can be used to solve the maximum subarray sum problem.

2. Find the maximum sub-array sum for the given elements.

{2, -1, 3, -4, 1, -2, -1, 5, -4}

a) 3

b) 5

c) 8

d) 6

Answer: b

The maximum sub-array sum for the given elements.

{2, -1, 3, -4, 1, -2, -1, 5, -4} is 5.

3. Find the maximum sub-array sum for the given elements.

{-2, -1, -3, -4, -1, -2, -1, -5, -4}

a) -3

b) 5

c) 3

d) -1

Answer: d

All the elements are negative. So, the maximum sub-array sum will be equal to the largest element. The largest element is -1 and therefore, the maximum sub-array sum is -1.

5. What is the time complexity of the following naive method used to find the maximum sub-array sum in an array containing n elements?

#include int main() { int arr[1000]={2, -1, 3, -4, 1, -2, -1, 5, -4}, len=9; int cur_max, tmp_max, strt_idx, sub_arr_idx; cur_max = arr[0]; for(strt_idx = 0; strt_idx < len; strt_idx++) { tmp_max=0; for(sub_arr_idx = strt_idx; sub_arr_idx < len; sub_arr_idx++) { tmp_max +=arr[sub_arr_idx]; if(tmp_max > cur_max) _____________; } } printf("%d",cur_max); return 0; }

a) O(n^{2})

b) O(n)

c) O(n3)

d) O(1)

Answer: a

The naive method uses two for loops. The outer loop runs from 0 to n,

i.e. i = 0 : n.

The inner loop runs from i to n, i.e. j = i: n.

Therefore, the inner loop runs:

n times when the outer loop runs the first time.

(n-1) times when the outer loop runs the second time.

:

:

:

2 times when the outer loop runs (n-1)th time.

1 time when the outer loop runs nth time.

Therefore, time complexity = n + (n-1) + (n-2) + …… + 2 + 1 = n * (n + 1) /2 = O(n^{2})

8. What is the time complexity of the divide and conquer algorithm used to find the maximum sub-array sum?

a) O(n)

b) O(logn)

c) O(nlogn)

d) O(n2)

Answer: c

The time complexity of the divide and conquer algorithm used to find the maximum sub-array sum is O(nlogn).

9. What is the space complexity of the divide and conquer algorithm used to find the maximum sub-array sum?

a) O(n)

b) O(1)

c) O(n!)

d) O(n2)

Answer: b

The divide and conquer algorithm uses constant space. So, the space complexity is O(1).

1. Which line should be inserted in the blank to complete the following dynamic programming implementation of the maximum sub-array sum problem?

#include int max_num(int a,int b) { if(a> b) return a; return b; } int maximum_subarray_sum(int *arr, int len) { int sum[len], idx; sum[0] = arr[0]; for(idx = 1; idx < len; idx++) sum[idx] = _______________________; int mx = sum[0]; for(idx = 0; idx < len; idx++) if(sum[idx] > mx) mx =sum[idx]; return mx; } int main() { int arr[] = {-2, -5, 6, -2, 3, -1, 0,-5, 6}, len = 9; int ans = maximum_subarray_sum(arr, len); printf("%d",ans); return 0; }

a) max_num(sum[idx – 1] + arr[idx], arr[idx])

b) sum[idx – 1] + arr[idx].

c) min_num(sum[idx – 1] + arr[idx], arr[idx])

d) arr[idx].

Answer: a

The array “sum” is used to store the maximum sub-array sum. The appropriate way to do this is by using:

sum[idx] = max_num(sum[idx – 1] + arr[idx], arr[idx]).

6. Find the maximum sub-array sum for the following array:

{3, 6, 7, 9, 3, 8}

a) 33

b) 36

c) 23

d) 26

Answer: b

All the elements of the array are positive. So, the maximum sub-array sum is equal to the sum of all the elements, which is 36.

1. Kadane’s algorithm is used to find ____________

a) Longest increasing subsequence

b) Longest palindrome subsequence

c) Maximum sub-array sum

d) Longest decreasing subsequence

Answer: c

- Kadane’s Algorithm is an iterative dynamic programming algorithm.
- It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position.
- Kadane’s algorithm is used to find the maximum sub-array sum for a given array.

2. Kadane’s algorithm uses which of the following techniques?

a) Divide and conquer

b) Dynamic programming

c) Recursion

d) Greedy algorithm

Answer: b

- Kadane’s Algorithm is an iterative dynamic programming algorithm.
- It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position.
- Kadane’s algorithm uses dynamic programming.

3. For which of the following inputs would Kadane’s algorithm produce the INCORRECT output?

a) {0,1,2,3}

b) {-1,0,1}

c) {-1,-2,-3,0}

d) {-4,-3,-2,-1}

Answer: d

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.

4. For which of the following inputs would Kadane’s algorithm produce a WRONG output?

a) {1,0,-1}

b) {-1,-2,-3}

c) {1,2,3}

d) {0,0,0}

Answer: b

Kadane’s algorithm doesn’t work for all negative numbers. So, the answer is {-1,-2,-3}.

6. What is the time complexity of Kadane’s algorithm?

a) O(1)

b) O(n)

c) O(n2)

d) O(5)

Answer: b

The time complexity of Kadane’s algorithm is O(n) because there is only one for loop which scans the entire array exactly once.

7. What is the space complexity of Kadane’s algorithm?

a) O(1)

b) O(n)

c) O(n2)

d) None of the mentioned

Answer: a

- Kadane’s Algorithm is an iterative dynamic programming algorithm.
- It calculates the maximum sum subarray ending at a particular position by using the maximum sum subarray ending at the previous position.
- Kadane’s algorithm uses a constant space. So, the space complexity is O(1).

1. The longest increasing subsequence problem is a problem finding the length of a subsequence from a sequence of array elements such that the subsequence is sorted in increasing order and its length is maximum. This problem can be solved using __________

a) Recursion

b) Dynamic programming

c) Brute force

d) Recursion, Dynamic programming, Brute force

Answer: d

The longest increasing subsequence problem can be solved using Recursion, Dynamic programming, and Brute force methods.

2. Find the longest increasing subsequence for the given sequence:

{10, -10, 12, 9, 10, 15, 13, 14}

a) {10, 12, 15}

b) {10, 12, 13, 14}

c) {-10, 12, 13, 14}

d) {-10, 9, 10, 13, 14}

Answer: d

The longest increasing subsequence for the given sequence is {-10, 9, 10, 13, 14}.

3. Find the length of the longest increasing subsequence for the given sequence:

{-10, 24, -9, 35, -21, 55, -41, 76, 84}

a) 5

b) 4

c) 3

d) 6

Answer: d

The longest increasing subsequence is {-10, 24, 35, 55, 76, 84} and it’s length is 6.

4. For any given sequence, there will ALWAYS be more than one subsequence with the longest length.

a) True

b) False

Answer: b

For a given sequence, it is possible that there is more than one subsequence with the longest length.

Consider, the following sequence: {10,11,12,1,2,3}:

There are two longest increasing subsequences: {1,2,3} and {10,11,12}.

5. The number of increasing subsequences with the longest length for the given sequence are:

{10, 9, 8, 7, 6, 5}

a) 3

b) 4

c) 5

d) 6

Answer: d

Each array element individually forms the longest increasing subsequence and so, the length of the longest increasing subsequence is 1. So, the number of increasing subsequences with the longest length is 6.

6. In the brute force implementation to find the longest increasing subsequence, all the subsequences of a given sequence are found. All the increasing subsequences are then selected and the length of the longest subsequence is found. What is the time complexity of this brute force implementation?

a) O(n)

b) O(n^{2})

c) O(n!)

d) O(2^{n})

Answer: d

The time required to find all the subsequences of a given sequence is 2n, where ‘n’ is the number of elements in the sequence. So, the time complexity is O(2^{n}).

1. 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?

a) Brute force

b) Dynamic programming

c) Recursion

d) Brute force, Dynamic Programming, and Recursion

Answer: d

Brute force, Dynamic Programming, and Recursion can be used to solve the rod cutting problem.

2. You are given a rod of length 5 and the prices of each length are as follows:

length price 1 2 2 5 3 6 4 9 5 9

What is the maximum value that you can get after cutting the rod and selling the pieces?

a) 10

b) 11

c) 12

d) 13

Answer: c

The pieces {1,2 2} give the maximum value of 12.

3. 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?

a) O(n2)

b) O(n3)

c) O(nlogn)

d) O(2n)

Answer: d

The brute force implementation finds all the possible cuts. This takes O(2n) time.

4. You are given a rod of length 10 and the following prices.

length price 1 2 2 5 3 6 4 9 5 9 6 17 7 17 8 18 9 20 10 22

Which of these pieces give the maximum price?

a) {1,2,7}

b) {10}

c) {2,2,6}

d) {1,4,5}

Answer: c

The pieces {2,2,6} give the maximum value of 27.

9. For every rod cutting problem there will be a unique set of pieces that give the maximum price.

a) True

b) False

Answer: b

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.

1. You are given an array of elements where each array element represents the MAXIMUM number of jumps that can be made in the forward direction from that element. You have to find the minimum number of jumps that are required to reach the end of the array. Which of these methods can be used to solve the problem?

a) Dynamic Programming

b) Greedy Algorithm

c) Recursion

d) Recursion and Dynamic Programming

Answer: d

Both recursion and dynamic programming can be used to solve a minimum number of jump problems.

2. Consider the following array:

{1, 3, 5, 8, 9, 2, 6, 7, 6}

What is the minimum number of jumps required to reach the end of the array?

a) 1

b) 2

c) 3

d) 4

Answer: c

The jumps made will be:{1 -> 2 -> 4 -> 9}. So, the number of jumps is three.

4. For a given array, there can be multiple ways to reach the end of the array using a minimum number of jumps.

a) True

b) False

Answer: a

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 cases, the number of jumps is 3, which is the minimum. Hence, it is possible to reach the end of the array in multiple ways using a minimum number of jumps.

6. For an array, given that at most one element is zero, it is ALWAYS possible to reach the end of the array using minimum jumps.

a) True

b) False

Answer: b

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.

1. The Knapsack problem is an example of ____________

a) Greedy algorithm

b) 2D dynamic programming

c) 1D dynamic programming

d) Divide and conquer

Answer: b

The knapsack problem is a problem in combinatorial optimization. The knapsack problem is an example of 2D dynamic programming.

2. Which of the following methods can be used to solve the Knapsack problem?

a) Brute force algorithm

b) Recursion

c) Dynamic programming

d) Brute force, Recursion, and Dynamic Programming

Answer: d

Brute force, Recursion, and Dynamic Programming can be used to solve the knapsack problem.

3. You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

a) 160

b) 200

c) 170

d) 90

Answer: a

The maximum value you can get is 160. This can be achieved by choosing items 1 and 3 that have a total weight of 60.

4. Which of the following problems is equivalent to the 0-1 Knapsack problem?

a) You are given a bag that can carry a maximum weight of W. You are given N items which have a weight of {w1, w2, w3,…., wn} and a value of {v1, v2, v3,…., vn}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value

b) You are studying for an exam and you have to study N questions. The questions take {t1, t2, t3,…., tn} time(in hours) and carry {m1, m2, m3,…., mn} marks. You can study for a maximum of T hours. You can either study a question or leave it. Choose the questions in such a way that your score is maximized

c) You are given infinite coins of denominations {v1, v2, v3,….., vn} and a sum S. You have to find the minimum number of coins required to get the sum S

d) You are given a suitcase that can carry a maximum weight of 15kg. You are given 4 items which have a weight of {10, 20, 15,40} and a value of {1, 2, 3,4}. You can break the items into smaller pieces. Choose the items in such a way that you get the maximum value

Answer: b

In this case, questions are used instead of items. Each question has a score that is the same as each item having a value. Also, each question takes a time t which is the same as each item having a weight w. You have to maximize the score in time T which is the same as maximizing the value using a bag of weight W.

5. What is the time complexity of the brute force algorithm used to solve the Knapsack problem?

a) O(n)

b) O(n!)

c) O(2n)

d) O(n3)

Answer: c

In the brute force algorithm, all the subsets of the items are found and the value of each subset is calculated.

The subset of items with the maximum value and a weight less than equal to the maximum allowed weight answers. The time taken to calculate all the subsets is O(2n).

6. The 0-1 Knapsack problem can be solved using the Greedy algorithm.

a) True

b) False

Answer: b

The Knapsack problem cannot be solved using the greedy algorithm.

1. Which of the following methods can be used to solve the matrix chain multiplication problem?

a) Dynamic programming

b) Brute force

c) Recursion

d) Dynamic Programming, Brute force, Recursion

Answer: d

Dynamic Programming, Brute force, and Recursion methods can be used to solve the matrix chain multiplication problem.

2. Which of the following is the recurrence relation for the matrix chain multiplication problem where mat[i-1] * mat[i] gives the dimension of the ith matrix?

a) dp[i,j] = 1 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]}

b) dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]}

c) dp[i,j] = 1 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

d) dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

Answer: d

The recurrence relation is given by:

dp[i,j] = 0 if i=j

dp[i,j] = min{dp[i,k] + dp[k+1,j]} + mat[i-1]*mat[k]*mat[j].

3. Consider the two matrices P and Q which are 10 × 20 and 20 × 30 matrices respectively. What is the number of multiplications required to multiply the two matrices?

a) 10*20

b) 20*30

c) 10*30

d) 10*20*30

Answer: d

The number of multiplications required is 10*20*30.

4. Consider the matrices P, Q, and R which are 10 x 20, 20 x 30, and 30 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the three matrices?

a) 18000

b) 12000

c) 24000

d) 32000

Answer: a

The minimum number of multiplications is 18000. This is the case when the matrices are parenthesized as (P*Q)*R.

5. Consider the matrices P, Q, R, and S which are 20 x 15, 15 x 30, 30 x 5, and 5 x 40 matrices respectively. What is the minimum number of multiplications required to multiply the four matrices?

a) 6050

b) 7500

c) 7750

d) 12000

Answer: c

The minimum number of multiplications required is 7750.

6. Consider the brute force implementation in which we find all the possible ways of multiplying the given set of n matrices. What is the time complexity of this implementation?

a) O(n!)

b) O(n^{3})

c) O(n^{2})

d) Exponential

Answer: d

The time complexity of finding all the possible ways of multiplying a set of n matrices is given by (n-1)th Catalan number which is exponential.

1. Which of the following methods can be used to solve the longest common subsequence problem?

a) Recursion

b) Dynamic programming

c) Both recursion and dynamic programming

d) Greedy algorithm

Answer: c

Both recursion and dynamic programming can be used to solve the longest subsequence problem.

2. Consider the strings “PQRSTPQRS” and “PRATPBRQRPS”. What is the length of the longest common subsequence?

a) 9

b) 8

c) 7

d) 6

Answer: c

The longest common subsequence is “PRTPQRS” and its length is 7.

3. Which of the following problems can be solved using the longest subsequence problem?

a) Longest increasing subsequence

b) Longest palindromic subsequence

c) Longest bitonic subsequence

d) Longest decreasing subsequence

Answer: b

To find the longest palindromic subsequence in a given string, reverse the given string and then find the longest common subsequence in the given string and the reversed string.

4. Longest common subsequence is an example of ____________

a) Greedy algorithm

b) 2D dynamic programming

c) 1D dynamic programming

d) Divide and conquer

Answer: b

The longest common subsequence is an example of 2D dynamic programming.

5. What is the time complexity of the brute force algorithm used to find the longest common subsequence?

a) O(n)

b) O(n^{2})

c) O(n^{3})

d) O(2n)

Answer: d

The time complexity of the brute force algorithm used to find the longest common subsequence is O(2n).

10. Which of the following is the longest common subsequence between the strings “hbcfgmnapq” and “cbhgrsfnmq”?

a) hgmq

b) cfnq

c) bfmq

d) fgmna

Answer: d

The length of the longest common subsequence is 4. But ‘fgmna’ is not the longest common subsequence as its length is 5.

1. Which of the following methods can be used to solve the longest palindromic subsequence problem?

a) Dynamic programming

b) Recursion

c) Brute force

d) Dynamic programming, Recursion, Brute force

Answer: d

Dynamic programming, Recursion, and Brute force can be used to solve the longest palindromic subsequence problem.

2. Which of the following is not a palindromic subsequence of the string “ababcdabba”?

a) abcba

b) abba

c) abbbba

d) adba

Answer: d

‘adba’ is not a palindromic sequence of the string “ababcdabba”.

3. For which of the following, the length of the string is not equal to the length of the longest palindromic subsequence?

a) A string that is a palindrome

b) A string of length one

c) A string that has all the same letters(e.g. aaaaaa)

d) Some strings of length two

Answer: d

A string of length 2 of the string is not equal to the length of the longest palindromic subsequence.

4. What is the length of the longest palindromic subsequence for the string “ababcdabba”?

a) 6

b) 7

c) 8

d) 9

Answer: b

The longest palindromic subsequence is “abbabba” and its length is 7.

5. What is the time complexity of the brute force algorithm used to find the length of the longest palindromic subsequence?

a) O(1)

b) O(2n)

c) O(n)

d) O(n2)

Answer: b

In the brute force algorithm, all the subsequences are found and the length of the longest palindromic subsequence is calculated. This takes exponential time.

6. For every non-empty string, the length of the longest palindromic subsequence is at least one.

a) True

b) False

Answer: a

A single character of any string can always be considered a palindrome and its length are one.

7. Longest palindromic subsequence is an example of ______________

a) Greedy algorithm

b) 2D dynamic programming

c) 1D dynamic programming

d) Divide and conquer

Answer: b

The longest palindromic subsequence is an example of 2D dynamic programming.

1. Which of the following methods can be used to solve the edit distance problem?

a) Recursion

b) Dynamic programming

c) Both dynamic programming and recursion

d) Greedy Algorithm

Answer: c

Both dynamic programming and recursion can be used to solve the edit distance problem.

2. The edit distance satisfies the axioms of a metric when the costs are non-negative.

a) True

b) False

Answer: a

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.

3. Which of the following is an application of the edit distance problem?

a) Approximate string matching

b) Spelling correction

c) Similarity of DNA

d) Approximate string matching, Spelling Correction, and Similarity of DNA

Answer: d

Approximate string matching, Spelling Correction, and Similarity of DNA are the applications of the edit distance problem.

4. In which of the following cases will the edit distance between two strings be zero?

a) When one string is a substring of another

b) When the lengths of the two strings are equal

c) When the two strings are equal

d) The edit distance can never be zero

Answer: c

The edit distance will be zero only when the two strings are equal.

5. 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.

a) True

b) False

Answer: a

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.

6. Consider the strings “Monday” and “Tuesday”. What is the edit distance between the two strings?

a) 3

b) 4

c) 5

d) 6

Answer: b

“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.

7. Consider the two strings “(empty string) and “abcd”. What is the edit distance between the two strings?

a) 0

b) 4

c) 2

d) 3

Answer: b

The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.

1. Wagner–Fischer is a ____________ algorithm.

a) Brute force

b) Greedy

c) Dynamic programming

d) Recursive

Answer: c

Wagner–Fischer belongs to the dynamic programming type of algorithms.

2. Wagner–Fischer algorithm is used to find ____________

a) Longest common subsequence

b) Longest increasing subsequence

c) Edit the distance between two strings

d) Longest decreasing subsequence

Answer: c

The Wagner-Fischer Algorithm is a dynamic programming algorithm that measures the Levenshtein distance or the edit distance between two strings of characters.

Wagner–Fischer algorithm is used to find the edit distance between two strings.

3. What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion, and substitution?

a) 1

b) 2

c) 3

d) 4

Answer: b

The string “abcd” can be changed to “acbd” by substituting “b” with “c” and “c” with “b”. Thus, the edit distance is 2.

4. For which of the following pairs of strings is the edit distance maximum?

a) Sunday & Monday

b) Monday & Tuesday

c) Tuesday & Wednesday

d) Wednesday & Thursday

Answer: d

The edit distances are 2, 4, 4, and 5 respectively. Hence, the maximum edit distance is between the strings Wednesday and Thursday.

6. What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?

a) O(1)

b) O(n+m)

c) O(mn)

d) O(nlogm)

Answer: c

The time complexity of the Wagner–Fischer algorithm is O(mn).

where “m” and “n” are the lengths of the two strings.

7. What is the space complexity of the above implementation of Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?

a) O(1)

b) O(n+m)

c) O(mn)

d) O(nlogm)

Answer: c

The space complexity of the above Wagner–Fischer algorithm is O(mn).

1. Which of the following is NOT a Catalan number?

a) 1

b) 5

c) 14

d) 43

Answer: d

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

Answer: d

Catalan numbers are given by: (2n!)/((n+1)!n!).

The 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

Answer: d

Counting the number of Dyck words, Counting the number of expressions containing n pairs of parenthesis, and 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 whereas the 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

Answer: d

Recursion, Binomial Coefficients, Dynamic programming 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:

#include 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("%dn",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];

Answer: c

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

Answer: b

The time complexities are as follows:

Dynamic programming: O(n^{2})

Recursion: Exponential

Binomial coefficients: O(n).

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

Answer: a

The space complexities are as follows:

Dynamic programming: O(n)

Recursion: O(1)

Binomial coefficients: O(1).

1. Which of the following methods can be used to solve the assembly line scheduling problem?

a) Recursion

b) Brute force

c) Dynamic programming

d) All of the mentioned

Answer: d

The methods that can be used to solve the assembly line scheduling problem are

a) Recursion

b) Brute force

c) Dynamic programming

All of the above-mentioned methods can be used to solve the assembly line scheduling problem.

2. What is the time complexity of the brute force algorithm used to solve the assembly line scheduling problem?

a) O(1)

b) O(n)

c) O(n2)

d) O(2n)

Answer: d

In the brute force algorithm, all the possible ways are calculated which are of the order of 2n.

3. In the dynamic programming implementation of the assembly line scheduling problem, how many lookup tables are required?

a) 0

b) 1

c) 2

d) 3

Answer: c

In the dynamic programming implementation of the assembly line scheduling problem, 2 lookup tables are required one for storing the minimum time and the other for storing the assembly line number.

4. Consider the following assembly line problem:

time_to_reach[2][3] = {{17, 2, 7}, {19, 4, 9}} time_spent[2][4] = {{6, 5, 15, 7}, {5, 10, 11, 4}} entry_time[2] = {8, 10} exit_time[2] = {10, 7} num_of_stations = 4

For the optimal solution which should be the starting assembly line?

a) Line 1

b) Line 2

c) All of the mentioned

d) None of the mentioned

Answer: b

For the optimal solution, the starting assembly line is line 2.

8. What is the time complexity of the above dynamic programming implementation of the assembly line scheduling problem?

a) O(1)

b) O(n)

c) O(n2)

d) O(n3)

Answer: b

The time complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

9. What is the space complexity of the above dynamic programming implementation of the assembly line scheduling problem?

a) O(1)

b) O(n)

c) O(n^{2})

d) O(n3)

Answer: b

The space complexity of the above dynamic programming implementation of the assembly line scheduling problem is O(n).

1. 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?

a) Greedy algorithm

b) Recursion

c) Dynamic programming

d) Both recursion and dynamic programming

Answer: d

Dynamic programming and recursion can be used to solve the problem to find the minimum number of characters to be inserted in the string so that the string becomes a palindrome.

2. In which of the following cases is the minimum no of insertions to form palindrome is maximum?

a) String of length one

b) String with all same characters

c) Palindromic string

d) Non palindromic string

Answer: d

In a string of length one, a 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.

3. 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.

a) True

b) False

Answer: b

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

4. Consider the string “efge”. What is the minimum number of insertions required to make the string a palindrome?

a) 0

b) 1

c) 2

d) 3

Answer: b

The string can be converted to “efgfe” by inserting “f” or to “egfge” by inserting “g”. Thus, only one insertion is required.

5. Consider the string “abbccbba”. What is the minimum number of insertions required to make the string a palindrome?

a) 0

b) 1

c) 2

d) 3

Answer: a

The given string “abbccbba” is already a palindrome. So, no insertions are required.

6. Which of the following problems can be used to solve the minimum number of insertions to form a palindrome problem?

a) Minimum number of jumps problem

b) Longest common subsequence problem

c) Coin change problem

d) Knapsack problems

Answer: b

A variation of the longest common subsequence can be used to solve the minimum number of insertions to form a palindrome problem.

1. Given a 2D matrix, find a submatrix that has the maximum sum. Which of the following methods can be used to solve this problem?

a) Brute force

b) Recursion

c) Dynamic programming

d) Brute force, Recursion, Dynamic programming

Answer: d

Brute force, Recursion, and Dynamic programming can be used to find the submatrix that has the maximum sum.

2. In which of the following cases, the maximum sum rectangle is the 2D matrix itself?

a) When all the elements are negative

b) When all the elements are positive

c) When some elements are positive and some negative

d) When diagonal elements are positive and the rest are negative

Answer: a

When all the elements of a matrix are positive, the maximum sum rectangle is the 2D matrix itself.

3. Consider the following statements and select which of the following statement are true.

Statement 1: The maximum sum rectangle can be a 1X1 matrix containing the largest element If the matrix size is 1X1

Statement 2: The maximum sum rectangle can be a 1X1 matrix containing the largest element If all the elements are zero

Statement 3: The maximum sum rectangle can be a 1X1 matrix containing the largest element If all the elements are negative

a) Only statement 1 is correct

b) Only statement 1 and Statement 2 are correct

c) Only statement 1 and Statement 3 are correct

d) Statement 1, Statement 2, and Statement 3 are correct

Answer: d

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.

4. 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.

a) True

b) False

Answer: a

If a matrix contains all non-zero elements with at least one positive and at least one negative element, then the sum of elements of the maximum sum rectangle cannot be zero.

5. Consider the 2×3 matrix {{1,2,3},{1,2,3}}. What is the sum of elements of the maximum sum rectangle?

a) 3

b) 6

c) 12

d) 18

Answer: c

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.

6. Consider the 2×2 matrix {{-1,-2},{-3,-4}}. What is the sum of elements of the maximum sum rectangle?

a) 0

b) -1

c) -7

d) -12

Answer: b

Since all the elements of the 2×2 matrix are negative, the maximum sum rectangle is {-1}, a 1×1 matrix containing the largest element. The sum of elements of the maximum sum rectangle is -1.

7. Consider the 3×3 matrix {{2,1,-3},{6,3,4},{-2,3,0}}. What is the sum of the elements of the maximum sum rectangle?

a) 13

b) 16

c) 14

d) 19

Answer: c

The complete matrix represents the maximum sum rectangle and its sum is 14.

8. What is the time complexity of the brute force implementation of the maximum sum rectangle problem?

a) O(n)

b) O(n2)

c) O(n3)

d) O(n^{4})

Answer: d

The time complexity of the brute force implementation of the maximum sum rectangle problem is O(n^{4}).

9. The dynamic programming implementation of the maximum sum rectangle problem uses which of the following algorithm?

a) Hirschberg’s algorithm

b) Needleman-Wunsch algorithm

c) Kadane’s algorithm

d) Wagner Fischer algorithm

Answer: c

The dynamic programming implementation of the maximum sum rectangle problem uses Kadane’s algorithm.

1. Given an array, check if the array can be divided into two subsets such that the sum of elements of the two subsets is equal. This is the balanced partition problem. Which of the following methods can be used to solve the balanced partition problem?

a) Dynamic programming

b) Recursion

c) Brute force

d) Dynamic programming, Recursion, Brute force

Answer: d

Dynamic programming, Recursion, Brute force methods can be used to solve the balanced partition problem.

2. In which of the following cases, it is not possible to have two subsets with an equal sum?

a) When the number of elements is odd

b) When the number of elements is even

c) When the sum of elements is odd

d) When the sum of elements is even

Answer: c

When the sum of all the elements is odd, it is not possible to have two subsets with equal sum.

3. What is the time complexity of the brute force algorithm used to solve the balanced partition problem?

a) O(1)

b) O(n)

c) O(n2)

d) O(2n)

Answer: d

O(2n) is the time complexity of the brute force algorithm used to solve the balanced partition problem.

In the brute force implementation, all the possible subsets will be formed. This takes exponential time.

4. Consider a variation of the balanced partition problem in which we find two subsets such that |S1 – S2| is minimum. Consider the array {1, 2, 3, 4, 5}. Which of the following pairs of subsets is an optimal solution for the above problem?

a) {5, 4} & {3, 2, 1}

b) {5} & {4, 3, 2, 1}

c) {4, 2} & {5, 3, 1}

d) {5, 3} & {4, 2, 1}

Answer: d

For S1 = {5, 3} and S2 = {4, 2, 1}, sum(S1) – sum(S2) = 1, which is the optimal solution.

10. What is the sum of each of the balanced partitions for the array {5, 6, 7, 10, 3, 1}?

a) 16

b) 32

c) 0

d) 64

Answer: a

The sum of all the elements of the array is 32. So, the sum of all the elements of each partition should be 16.

1. You are given n dice each having f faces. You have to find the number of ways in which a sum of S can be achieved. This is the dice-throw problem. Which of the following methods can be used to solve the dice throw problem?

a) Brute force

b) Recursion

c) Dynamic programming

d) Brute force, Recursion, and Dynamic Programming

Answer: d

Brute force, Recursion, and Dynamic Programming can be used to solve the dice throw problem.

2. You have n dice each having f faces. What is the number of permutations that can be obtained when you roll the n dice together?

a) n*n*n…f times

b) f*f*f…n times

c) n*n*n…n times

d) f*f*f…f times

Answer: b

Each die can take f values and there are n dice. So, the total number of permutations is f*f*f…n times.

3. You have 3 dice each having 6 faces. What is the number of permutations that can be obtained when you roll the 3 dice together?

a) 27

b) 36

c) 216

d) 81

Answer: c

The total number of permutations that can be obtained is 6 * 6 * 6 = 216.

4. You have 2 dice each of them having 6 faces numbered from 1 to 6. What is the number of ways in which a sum of 11 can be achieved?

a) 0

b) 1

c) 2

d) 3

Answer: c

The sum of 11 can be achieved when the dice show {6, 5} or {5, 6}.

5. There are n dice with f faces. The faces are numbered from 1 to f. What is the minimum possible sum that can be obtained when the n dice are rolled together?

a) 1

b) f

c) n

d) n*f

Answer: c

The sum will be minimum when all the faces show a value of 1. The sum in this case will be n.

6. There are n dice with f faces. The faces are numbered from 1 to f. What is the maximum possible sum that can be obtained when the n dice are rolled together?

a) 1

b) f*f

c) n*n

d) n*f

Answer: d

The sum will be maximum when all the faces show a value of f. The sum, in this case, will be n*f.

7. 10 dice are having 5 faces. The faces are numbered from 1 to 5. What is the number of ways in which a sum of 4 can be achieved?

a) 0

b) 2

c) 4

d) 8

Answer: a

Since there are 10 dice and the minimum value each die can take is 1, the minimum possible sum is 10. Hence, a sum of 4 cannot be achieved.

1. You are given a boolean expression which consists of operators &, | and ∧ (AND, OR and XOR) and symbols T or F (true or false). You have to find the number of ways in which the symbols can be parenthesized so that the expression evaluates to true. This is the boolean parenthesization problem. Which of the following methods can be used to solve the problem?

a) Dynamic programming

b) Recursion

c) Brute force

d) Dynamic programming, Recursion, and Brute force

Answer: d

Dynamic programming, Recursion, and Brute force can be used to solve the Boolean parenthesization problem.

2. Consider the expression T & F | T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

a) 0

b) 1

c) 2

d) 3

Answer: c

The expression can be parenthesized as T & (F | T) and (T & F) | T so that the output is T.

3. Consider the expression T & F ∧ T. What is the number of ways in which the expression can be parenthesized so that the output is T (true)?

a) 0

b) 1

c) 2

d) 3

Answer: c

The expression can be parenthesized as (T & F) ∧ T or T & (F ∧ T) so that the output is T.

4. Consider the expression T | F ∧ T. In how many ways can the expression be parenthesized so that the output is F (false)?

a) 0

b) 1

c) 2

d) 3

Answer: b

The expression can be parenthesized as (T | F) ∧ T so that the output is F (false).

5. Which of the following gives the total number of ways of parenthesizing an expression with n + 1 terms?

a) n factorial

b) n square

c) n cube

d) nth Catalan number

Answer: d

The nth Catalan number gives the total number of ways of parenthesizing an expression with n + 1 terms.

6. What is the maximum number of ways in which a boolean expression with n + 1 terms can be parenthesized, such that the output is true?

a) nth Catalan number

b) n factorial

c) n cube

d) n square

Answer: a

The number of ways will be maximum when all the possible parenthesizations result in a true value. The number of possible parenthesizations is given by the nth Catalan number.