Test: Dynamic Programming & Divide-And-Conquer - Computer Science Engineering (CSE) MCQ

# Test: Dynamic Programming & Divide-And-Conquer - Computer Science Engineering (CSE) MCQ

Test Description

## 20 Questions MCQ Test GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Test: Dynamic Programming & Divide-And-Conquer

Test: Dynamic Programming & Divide-And-Conquer for Computer Science Engineering (CSE) 2024 is part of GATE Computer Science Engineering(CSE) 2025 Mock Test Series preparation. The Test: Dynamic Programming & Divide-And-Conquer questions and answers have been prepared according to the Computer Science Engineering (CSE) exam syllabus.The Test: Dynamic Programming & Divide-And-Conquer 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 Programming & Divide-And-Conquer below.
Solutions of Test: Dynamic Programming & Divide-And-Conquer questions in English are available as part of our GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) & Test: Dynamic Programming & Divide-And-Conquer solutions in Hindi for GATE Computer Science Engineering(CSE) 2025 Mock Test Series 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 Programming & Divide-And-Conquer | 20 questions in 60 minutes | Mock test for Computer Science Engineering (CSE) preparation | Free important questions MCQ to study GATE Computer Science Engineering(CSE) 2025 Mock Test Series for Computer Science Engineering (CSE) Exam | Download free PDF with solutions
Test: Dynamic Programming & Divide-And-Conquer - Question 1

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

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 1

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

Test: Dynamic Programming & Divide-And-Conquer - Question 2

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

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 2

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 global optimal solution. For example, mergesort uses divide and conquer strategy.

 1 Crore+ students have signed up on EduRev. Have you?
Test: Dynamic Programming & Divide-And-Conquer - Question 3

### 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.   Initialize Ln−1=1 For all i such that  0 ≤ i  ≤ n-2   Finally, the length of the longest monotonically increasing sequence is max(L0,L1,…,Ln−1). Q. Which of the following statements is TRUE?

Test: Dynamic Programming & Divide-And-Conquer - Question 4

Kadane algorithm is used to find:

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 4

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

Test: Dynamic Programming & Divide-And-Conquer - Question 5

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 Programming & Divide-And-Conquer - Question 5

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 Programming & Divide-And-Conquer - Question 6

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 Programming & Divide-And-Conquer - Question 6

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 Programming & Divide-And-Conquer - Question 7

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 Programming & Divide-And-Conquer - Question 7

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 Programming & Divide-And-Conquer - Question 8

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 Programming & Divide-And-Conquer - Question 8

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 Programming & Divide-And-Conquer - Question 9

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 Programming & Divide-And-Conquer - Question 9

//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 Programming & Divide-And-Conquer - 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 Programming & Divide-And-Conquer - 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 Programming & Divide-And-Conquer - Question 11

Which of the following algorithms is NOT a divide & conquer algorithm by nature?

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 11

See Divide and Conquer

Test: Dynamic Programming & Divide-And-Conquer - Question 12

Consider the following C program

Q. What does the program compute?

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 12

This is an implementation of Euclid’s algorithm to find GCD

Test: Dynamic Programming & Divide-And-Conquer - Question 13

Consider the polynomial p(x) = a0 + a1x + a2x2 +a3x3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is:

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 13

Multiplications can be minimized using following order for evaluation of the given expression. p(x) = a0 + x(a1 + x(a2 + a3x))

Test: Dynamic Programming & Divide-And-Conquer - Question 14

Maximum Subarray Sum problem is to find the subarray with maximum sum. For example, given an array {12, -13, -5, 25, -20, 30, 10}, the maximum subarray sum is 45. The naive solution for this problem is to calculate sum of all subarrays starting with every element and return the maximum of all. We can solve this using Divide and Conquer, what will be the worst case time complexity using Divide and Conquer.

Test: Dynamic Programming & Divide-And-Conquer - Question 15

Consider a situation where you don't have function to calculate power (pow() function in C) and you need to calculate x^n where x can be any number and n is a positive integer. What can be the best possible time complexity of your power function?

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 15

We can calculate power using divide and conquer in O(Logn) time.

Test: Dynamic Programming & Divide-And-Conquer - Question 16

Consider the problem of searching an element x in an array 'arr[]' of size n. The problem can be solved in O(Logn) time if. 1) Array is sorted 2) Array is sorted and rotated by k. k is given to you and k <= n 3) Array is sorted and rotated by k. k is NOT given to you and k <= n 4) Array is not sorted

Test: Dynamic Programming & Divide-And-Conquer - Question 17

The secant method is used to find the root of an equation f(x) = 0. It is started from two distinct estimates xa and xb for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(xb) is very small and then xb is the solution. The procedure is given below. Observe that there is an expression which is missing and is marked by? Which is the suitable expression that is to be put in place of? So that it follows all steps of the secant method?

Initialize: xa, xb, ε, N // ε = convergence indicator
fb = f(xb) i = 0
while (i < N and |fb| > ε) do
i = i + 1             // update counter
xt = ?                // missing expression for
// intermediate value
xa = xb             // reset xa
xb = xt              // reset xb
fb = f(xb)           // function value at new xb

end while
if |fb| > ε
then            // loop is terminated with i = N
write “Non-convergence”
else
write “return xb
end if

Test: Dynamic Programming & Divide-And-Conquer - Question 18

Suppose you are provided with the following function declaration in the C programming language.

int partition (int a[ ], int n);

The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n

int kth_smallest (int a[], int n, int k)

int left_end = partition (a, n);
if (left_end+1==k)

return a [left_end];

if (left_end+1 > k)

return kth_smallest (____________________);

else

return kth_smallest (____________________);
}

Q.
The missing argument lists are respectively

Test: Dynamic Programming & Divide-And-Conquer - Question 19

Consider the problem of computing min-max in an unsorted array where min and max are minimum and maximum elements of array. Algorithm A1 can compute min-max in a1 comparisons without divide and conquer. Algorithm A2 can compute min-max in a2 comparisons by scanning the array linearly. What could be the relation between a1 and a2 considering the worst case scenarios?

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 19

When Divide and Conquer is used to find the minimum-maximum element in an array, Recurrence relation for the number of comparisons is
T(n) = 2T(n/2) + 2 where 2 is for comparing the minimums as well the maximums of the left and right subarrays
On solving, T(n) = 1.5n - 2.
While doing linear scan, it would take 2*(n-1) comparisons in the worst case to find both minimum as well maximum in one pass.

Test: Dynamic Programming & Divide-And-Conquer - Question 20

Consider the C program below.
#include <stdio.h>
int *A, stkTop;
int stkFunc (int opcode, int val)

static int size=0, stkTop=0;
switch (opcode)
{
case -1:
size = val;
break;
case 0:
if (stkTop < size ) A[stkTop++]=val;
break;
default:
if (stkTop) return A[--stkTop];
}
return -1;

int main()

int B[20];
A=B;
stkTop = -1;
stkFunc (-1, 10);
stkFunc (0, 5);
stkFunc (0, 10);
printf ("%d\n", stkFunc(1, 0)+ stkFunc(1, 0));

The value printed by the above program is ___________

Detailed Solution for Test: Dynamic Programming & Divide-And-Conquer - Question 20

The code in main, basically initializes a stack of size 10, then pushes 5, then pushes 10.

Finally the printf statement prints sum of two pop operations which is 10 + 5 = 15.

stkFunc (-1, 10); // Initialize size as 10 stkFunc (0, 5); // push 5
stkFunc (0, 10); // push 10
// print sum of two pop
printf ("%d\n", stkFunc(1, 0) + stkFunc(1, 0));

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests
Information about Test: Dynamic Programming & Divide-And-Conquer Page
In this test you can find the Exam questions for Test: Dynamic Programming & Divide-And-Conquer solved & explained in the simplest way possible. Besides giving Questions and answers for Test: Dynamic Programming & Divide-And-Conquer, EduRev gives you an ample number of Online tests for practice

## GATE Computer Science Engineering(CSE) 2025 Mock Test Series

55 docs|215 tests