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

Test Description

Test: Dynamic Programming & Divide-And-Conquer for Computer Science Engineering (CSE) 2024 is part of Computer Science Engineering (CSE) 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 course for Computer Science Engineering (CSE) & Test: Dynamic Programming & Divide-And-Conquer 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 Programming & Divide-And-Conquer | 20 questions in 60 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

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

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

1 Crore+ students have signed up on EduRev. Have you? Download the App |

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 L_{n−1}=1

For all i such that 0 ≤ i ≤ n-2

Finally, the length of the longest monotonically increasing sequence is max(L_{0},L_{1},…,L_{n−1}).

Q.

Which of the following statements is TRUE?

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

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

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

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

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

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

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

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

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

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

Consider the polynomial p(x) = a0 + a1x + a2x^{2} +a3x^{3}, 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

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

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 x_{a} and x_{b} for the root. It is an iterative procedure involving linear interpolation to a root. The iteration stops if f(x_{b}) is very small and then x_{b} 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: x_{a}, x_{b}, ε, N // ε = convergence indicator

f_{b} = f(x_{b}) i = 0

while (i < N and |f_{b}| > ε) do

i = i + 1 // update counter

x_{t} = ? // missing expression for

// intermediate value

x_{a} = x_{b} // reset x_{a}

x_{b} = x_{t} // reset x_{b}

f_{b} = f(x_{b}) // function value at new x_{b}

end while

if |f_{b}| > ε

then // loop is terminated with i = N

write “Non-convergence”

else

write “return x_{b}”

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

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

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

Download as PDF