Test: Dynamic Programing - Computer Science Engineering (CSE) MCQ

# Test: Dynamic Programing - Computer Science Engineering (CSE) MCQ

Test Description

## 15 Questions MCQ Test - Test: Dynamic Programing

Test: Dynamic Programing for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) preparation. The Test: Dynamic Programing questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Dynamic Programing MCQs are made for Computer Science Engineering (CSE) 2024 Exam. Find important definitions, questions, notes, meanings, examples, exercises, MCQs and online tests for Test: Dynamic Programing below.
Solutions of Test: Dynamic Programing questions in English are available as part of our course for Computer Science Engineering (CSE) & Test: Dynamic Programing solutions in Hindi for Computer Science Engineering (CSE) course. Download more important topics, notes, lectures and mock test series for Computer Science Engineering (CSE) Exam by signing up for free. Attempt Test: Dynamic Programing | 15 questions in 35 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
 1 Crore+ students have signed up on EduRev. Have you?
Test: Dynamic Programing - Question 1

### Which of the following standard algorithms is not Dynamic Programming based.

Detailed Solution for Test: Dynamic Programing - Question 1

Prim's Minimum Spanning Tree is a Greedy Algorithm. All other are dynamic programming based.

Test: Dynamic Programing - Question 2

### An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array A[0 :n-1] is given below. Let Li denote the length of the longest monotonically increasing sequence starting at index i in the array. Which of the following statements is TRUE?

Detailed Solution for Test: Dynamic Programing - Question 2

The time complexity of the above Dynamic Programming (DP) solution is O(n^2) and there is a O(N log N) solution for the LIS problem. We have not discussed the O(N log N) solution here as the purpose of this post is to explain Dynamic Programming with a simple example. See below post for O(N log N) solution.

Test: Dynamic Programing - Question 3

### We use dynamic programming approach when

Detailed Solution for Test: Dynamic Programing - Question 3

Option (D) is incorrect because Greedy algorithms are generally faster than Dynamic programming.

Test: Dynamic Programing - Question 4

Four matrices M1, M2, M3 and M4 of dimensions pxq, qxr, rxs and sxt respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 X M2) X (M3 X M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 X M2) X M3) X M4), the total number of scalar multiplications is pqr + prs + pst. If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is

Detailed Solution for Test: Dynamic Programing - Question 4

It is basically matrix chain multiplication problem. We get minimum number of multiplications using ((M1 X (M2 X M3)) X M4). Total number of multiplications = 100x20x5 (for M2 x M3) + 10x100x5 + 10x5x80 = 19000.

Test: Dynamic Programing - Question 5

Kadane algorithm is used to find:

Detailed Solution for Test: Dynamic Programing - Question 5

Kadane algorithm is used to find the maximum sum subarray in an array. It runs in O(n) time complexity.

Test: Dynamic Programing - Question 6

In the above question, which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

Detailed Solution for Test: Dynamic Programing - Question 6

If we get the entry X[n, W] as true then there is a subset of {a1, a2, .. an} that has sum as W.

Test: Dynamic Programing - Question 7

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j],1 <= i <= n, 0 <= j <= W, is TRUE if and only if there is a subset of {a1 ,a2 ,...,ai} whose elements sum to j. Which of the following is valid for 2 <= i <= n and ai <= j <= W?

Detailed Solution for Test: Dynamic Programing - Question 7

X[I, j] (2 <= i <= n and ai <= j <= W), is true if any of the following is true 1) Sum of weights excluding ai is equal to j, i.e., if X[i-1, j] is true. 2) Sum of weights including ai is equal to j, i.e., if X[i-1, j-ai] is true so that we get (j – ai) + ai as j

Test: Dynamic Programing - Question 8

Consider two strings A = "qpqrr" and B = "pqprqrp". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ___.

Detailed Solution for Test: Dynamic Programing - Question 8

The LCS is of length 4. There are 3 LCS of length 4 "qprr", "pqrr" and qpqr   A subsequence is a sequence that can be derived from another sequence by selecting zero or more elements from it, without changing the order of the remaining elements. Subsequence need not be contiguous. Since the length of given strings A = “qpqrr” and B = “pqprqrp” are very small, we don’t need to build a 5x7 matrix and solve it using dynamic programming. Rather we can solve it manually just by brute force. We will first check whether there exist a subsequence  of length 5 since min_length(A,B) = 5. Since there is no subsequence , we will now check for length 4. “qprr”, “pqrr” and “qpqr” are common in both strings. X = 4 and Y = 3 X + 10Y = 34

Test: Dynamic Programing - Question 9

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:
l(i,j) = 0, if either i=0 or j=0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] != Y[j-1]

Detailed Solution for Test: Dynamic Programing - Question 9

In Longest common subsequence problem, there are two cases for X[0..i] and Y[0..j]
1) The last characters of two strings match.
The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]
2) The last characters don't match.
The length of lcs is max of following two lcs values
a) LCS of X[0..i-1] and Y[0..j]
b) LCS of X[0..i] and Y[0..j-1]

Test: Dynamic Programing - Question 10

Let A1, A2, A3, and A4 be four matrices of dimensions 10 x 5, 5 x 20, 20 x 10, and 10 x 5, respectively. The minimum number of scalar multiplications required to find the product A1A2A3A4 using the basic matrix multiplication method is

Detailed Solution for Test: Dynamic Programing - Question 10

We have many ways to do matrix chain multiplication because matrix multiplication is associative. In other words, no matter how we parenthesize the product, the result of the matrix chain multiplication obtained will remain the same. Here we have four matrices A1, A2, A3, and A4, we would have: ((A1A2)A3)A4 = ((A1(A2A3))A4) = (A1A2)(A3A4) = A1((A2A3)A4) = A1(A2(A3A4)). However, the order in which we parenthesize the product affects the number of simple arithmetic operations needed to compute the product, or the efficiency. Here, A1 is a 10 × 5 matrix, A2 is a 5 x 20 matrix, and A3 is a 20 x 10 matrix, and A4 is 10 x 5. If we multiply two matrices A and B of order l x m and m x n respectively,then the number of scalar multiplications in the multiplication of A and B will be lxmxn. Then, The number of scalar multiplications required in the following sequence of matrices will be : A1((A2A3)A4) = (5 x 20 x 10) + (5 x 10 x 5) + (10 x 5 x 5) = 1000 + 250 + 250 = 1500. All other parenthesized options will require number of multiplications more than 1500.

Test: Dynamic Programing - Question 11

Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. The value of Vopt − Vgreedy is ______ .
Note -This was Numerical Type question.

Detailed Solution for Test: Dynamic Programing - Question 11

First we will pick item_4 (Value weight ratio is highest). Second highest is item_1, but cannot be picked because of its weight. Now item_3 shall be picked. item_2 cannot be included because of its weight. Therefore, overall profit by Vgreedy = 20+24 = 44 Hence, Vopt - Vgreedy = 60-44 = 16 So, answer is 16.

Test: Dynamic Programing - Question 12

Consider a sequence F00 defined as : F00(0) = 1, F00(1) = 1 F00(n) = 10 ∗ F00(n – 1) + 100 F00(n – 2) for n ≥ 2 Then what shall be the set of values of the sequence F00 ?

Detailed Solution for Test: Dynamic Programing - Question 12

F00(0) = 1, F00(1) = 1 F00(n) = 10 ∗ F00(n – 1) + 100 F00(2) = 10 * F00(1) + 100 = 10 * 1 + 100 = 10 + 100 = 110 Similarly: F00(3) = 10 * F00(2) + 100 = 10 * 110 + 100 = 1100 + 100 = 1200 The sequence will be (1, 110, 1200).

So, (A) will be the answer.

Test: Dynamic Programing - Question 13

Consider the following two sequences :
X = < B, C, D, C, A, B, C >, and
Y = < C, A, D, B, C, B >
The length of longest common subsequence of X and Y is :

Detailed Solution for Test: Dynamic Programing - Question 13

Initially, We check for length 5 sub-sequence between both given sequences but couldn't find. Then checked for length 4 sub-sequences and CDBC and CDCB two sub-sequences found.

Test: Dynamic Programing - Question 14

What happens when a top-down approach of dynamic programming is applied to any problem?

Detailed Solution for Test: Dynamic Programing - Question 14

As the mentioned approach uses the memoization technique it always stores the previously calculated values. Due to this, the time complexity is decreased but the space complexity is increased.

Test: Dynamic Programing - Question 15

The following paradigm can be used to find the solution of the problem in minimum time: Given a set of non-negative integer, and a value K, determine if there is a subset of the given set with sum equal to K:

Detailed Solution for Test: Dynamic Programing - Question 15

Given problem is Subset-sum problem in which a set of non-negative integers, and a value sum is given, to determine if there is a subset of the given set with sum equal to given sum. With recursion technique, time complexity of the above problem is exponential. We can solve the problem in Pseudo-polynomial time using Dynamic programming. Refer: Subset Sum Problem Option (B) is correct

Information about Test: Dynamic Programing Page
In this test you can find the Exam questions for Test: Dynamic Programing solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Dynamic Programing, EduRev gives you an ample number of Online tests for practice