CS502 Quiz 3 by VU Topper RM

In chain matrix multiplication, the order of the matrices__________. A. is equal

B. is reverse

C. can not be changed D. can be changed

In Knapsack Problem, each item must be entirely accepted or rejected, is called _______ problem. A. Linear B. Fractional

C. 0-1

D. Optimal

In Dynamic Programming based solution of Knapsack Problem, if we decide to take an object 'i', then we gain _______. A. W(Total Weight of Knapsack) B. V (Total Value of all items)

C. vi (Value of object i) Page 93

D. None of the given option

In chain matrix multiplication, table is filled ______ to find the multiplication of matrix. A. row wise B. column wise C. diagonally

D. bottom-to-up Page 86

In chain matrix multiplication, if there are n items, there are ______ ways in which outer most pair of parentheses can placed. A. n^2 B. 2n C. n+1

D. n-1 Page 85

Catalan numbers are related the number of different ______ on 'n' nodes. A. Arrays B. linked lists

C. binary trees Page 85

D. functions

What is the value of k in the given equation?

m[1, 5] = m[1, 3] + m[4, 5] + p0 · p3 · p5

A. 3

B. 1 C. 4 D. 5

The running time of brute-force algorithm to solve Knapsack problem is

A. O(n!)

B. O(2^n)

C. O(n) D. O(n3)

What is the value of k in the given equation?

m[2, 5] = m[2, 3] + m[4, 5] + p1 · p3 · p5 A. 3 B. 5

C. 2

D. 4

We can't utilize a divide-and-conquer strategy for Chain Matrix Multiplication because ____________. A. Size of data is not given B. We can easily perform it in linear time C. We use divide and conquer for sorting only

D. We do not know the optimum k

Suppose we have 5 matrices A, B, C, D and E. What is the correct expansion of m[3,4] in chain matrix multiplication?

1. m[3, 4] = m[3, 4] + m[4, 4] + p2 · p3 · p4
2. m[3, 4] = m[3, 3] + m[3, 4] + p2 · p3 · p4
3. m[3, 4] = m[3, 3] + m[4, 4] + p0 · p3 · p4
4. m[3, 4] = m[3, 3] + m[4, 4] + p2 · p3 · p4

Correct answer: m[3, 4] = m[3, 3] + m[4, 4] + p2 · p3 · p4

Time complexity of activity selection algorithm is _________. A. O(logN2)

B. O(NlogN)

C. O(logN) D. O(N)

If we have 6 metrices in chain matrix multiplication problem then the number of table entries must be?

1. 12
2. 25
3. 30
4. 36 Google

Correct answer: 36 Google

Counting Money problem: A. Can be solved by simple recursive algorithm

B. Can be optimally solved by greedy algorithm

C. can not be optimally solved by greedy algorithm D. Can not be solved by brute force algorithm

Time complexity of Dynamic Programming based algorithm for computing the minimum cost of Chain MatrixMultiplication is

A. Log n B. n C. n^2 (n square)