Free Printable Dynamic Programming

1.

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

a)

Optimal substructure

b)

Overlapping subproblems

c)

Greedy approach

d)

d) Both optimal substructure and overlapping subproblems

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

3.

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

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memoization

d)

Greedy

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

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

6.

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

a)

True

b)

False

7.

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

8.

Dynamic programming divides problems into a number of

a)

conflicting objective functions.

b)

decision stages.

c)

unrelated constraints.

d)

policies.

9.

The relationship between stages of a dynamic programming problem is called a(n)

a)

state.

b)

random variable.

c)

node.

d)

Transformation.

10.

In dynamic programming, the output to stage n become the input to

a)

stage n-1.

b)

stage n itself.

c)

stage n+1.

d)

stage n-2.

11.

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

a)

Saving value property

b)

Storing value property

c)

Memorization

d)

Mapping

12.

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

a)

0

b)

3

c)

4

d)

None of the above

13.

What are 2 things required in order to successfully use the dynamic programming technique?

a)

Optimal sub structure and overlapping sub problems

b)

A problem that can’t be sub divided and is complex

c)

Non overlapping sub problems and intervals

d)

Recursion and a problem that is complex

14.

Dynamic Programming is often used for (choose all that apply):

a)

Optimization problems that involve making a choice that leave one or more subproblems to be solved.

b)

Problems previously solved using divide and conquer that have over lapping subproblems

c)

Non polynomial solution problems

d)

Subproblems where resources are shared

15.

The difference between Divide and Conquer and Dynamic Programming is:

a)

The division of problems and combination of subproblems

b)

Whether the sub problems overlap or not

c)

The way we solve the base case

d)

The depth of recurrence

16.

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

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memorization

d)

Greedy

17.

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

18.

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}

19.

For any given sequence, there will ALWAYS be a unique increasing subsequence with the longest length.

a)

True

b)

False

20.

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)

170

b)

200

c)

160

d)

90

21.

Consider the two matrices P and Q which are 10 x 20 and 20 x 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

22.

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

a)

6

b)

7

c)

8

d)

9

23.

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

24.

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

25.

Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?

a)

3

b)

4

c)

5

d)

6

26.

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

27.

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)

None of the mentioned

28.

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

a)

True

b)

False

29.

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

30.

What is the time complexity of the dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

a)

O(n)

b)

O(m)

c)

O (m + n)

d)

O(mn)

31.

In Dynamic programming which of the following method does not consist recursion?

a)

memoization

b)

merging

c)

tabulation

d)

none

32.

0/1 knapsack is based on _________ method

a)

greedy method

b)

dynamic programming

c)

divide and conquer

d)

branch and bound

33.

Minimum number of platforms required for trains is

Lists of arrival time and departure time.

Arrival: {900, 940, 950, 1100, 1500, 1800}

Departure: {910, 1200, 1120, 1130, 1900, 2000}

a)

1

b)

2

c)

3

d)

4

34.

In dynamic programming top-down approach is also known as____

a)

tabulation

b)

memoization

c)

optimization

d)

generalization

35.

_______ guarantees to find the optimal solution of a problem if the solution exists

a)

Dynamic programming

b)

Backtracking

c)

Greedy

d)

None

36.

___________ is a method used to store the results of previous function calls to speed up future calculations.

a)

Optimization

b)

Tabulation

c)

Memoization

d)

None

37.

Identify applications of dynamic programming

a)

Fibonacci number series

b)

Knapsack problem

c)

Longest common subsequence

d)

All

38.

Time complexity of longest common sub string using DP is

a)

O(n*m)

b)

O(n+m)

c)

O(n/m)

d)

O(n-m)

39.

Time complexity of longest increasing sub sequences using DP is

a)

O(n^3)

b)

O(n^2)

c)

O(2^n)

d)

O(3^n)

40.

Formula for longest increasing sub sequence is

a)

LS(i) = 1+ max {LS(j)} ; where j<i and A[i] > A[j]

0 ; Otherwise

b)

LS(i) = 1+ min {LS(j)} ; where j<i and A[i] > A[j]

1 ; Otherwise

c)

LS(i) = 1+ max {LS(j)} ; where j<i and A[i] > A[j]

1 ; Otherwise

d)

LS(i) = 1+ max {LS(j)} ; where j>i and A[i] <A[j]

1 ; Otherwise

41.

Which of the following standard algorithms is not Dynamic Programming based

a)

Bellman–Ford Algorithm for single source shortest path

b)

Floyd Warshall Algorithm for all pairs shortest paths

c)

0-1 Knapsack problem

d)

Prim's Minimum Spanning Tree

42.

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

a)

Optimal substructure

b)

Overlapping subproblems

c)

Distinct Subproblems

d)

Combinatorial

43.

Which technique can be used to get the nth fibonacci term?

a)

Recursion

b)

Dynamic Programming

c)

Both

44.

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

a)

True

b)

False

45.

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

a)

Dynamic Programming

b)

Divide and Conquer

c)

Recursion

d)

Greedy Technique

46.

The 0/1 Knapsack problem belongs to which domain of problems?

a)

NP Complete

b)

Linear Solution

c)

Sorting

d)

Optimization

47.

What is the space complexity of the following dynamic programming implementation of the Knapsack problem?

a)

O(n)

b)

O(n+W)

c)

O(nW)

d)

O(n²)

48.

Which of the following greedy strategies may give the optimal solution for 0-1 knapsack problem?

a)

Largest profit first

b)

Lightest item first

c)

Heaviest item first

d)

Largest profit per unit weight first

49.

Given a Weighted graph G, Floyd's Algorithm finds

a)

Single source shortest path

b)

All pairs shortest path

c)

Minimum Spanning Tree

d)

Transitive closure

50.

Which of the following recurrence formula is correct for all n>k>0

a)

C(n,k) = C(n-1,k-1) + C(n-1, k) & C(n, 0) = C(n, n )= 1

b)

C(n,k)=C(n-1,k-1)+C(n,k-1) & C(0,n) = C(n,n) = 1

c)

C(n,k)=C(n-1,k-1)+C(n-1,k) & C(0,n) = C(n,n) = 1

d)

C(n,k)=C(n-1,k-1)+C(n-1,k) & C(n,0) = C(n,n) = 0

51.

A sequence of values in a column of DP table for an instance of the knapsack problem is always non-decreasing

a)

True

b)

False

52.

What according to you is a good online quiz app?

a)

Kahoot

b)

Mentimeter

c)

Quizizz

d)

Google Form

53.

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

54.

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

a)

True

b)

False

55.

Dynamic programming differs from the greedy method since the greedy method produces only one feasible solution, which may or may not be optimal, while dynamic programming produces all possible sub-problems at most once, one of which guaranteed to be optimal.

a)

True

b)

False

56.

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

a)

Saving value property

b)

Storing value property

c)

Memorization

d)

Mapping

57.

What are 2 things required in order to successfully use the dynamic programming technique?

a)

Optimal sub structure and overlapping sub problems

b)

A problem that can’t be sub divided and is complex

c)

Non overlapping sub problems and intervals

d)

Recursion and a problem that is complex

58.

Dynamic Programming is often used for (choose all that apply):

a)

Optimization problems that involve making a choice that leave one or more subproblems to be solved.

b)

Problems previously solved using divide and conquer that have over lapping subproblems

c)

Non polynomial solution problems

d)

Subproblems where resources are shared

59.

The difference between Divide and Conquer and Dynamic Programming is:

a)

The division of problems and combination of subproblems

b)

Whether the sub problems overlap or not

c)

The way we solve the base case

d)

The depth of recurrence

60.

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

a)

Overlapping subproblems

b)

Optimal substructure

c)

Memorization

d)

Greedy

61.

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)

170

b)

200

c)

160

d)

90

62.

Consider the two matrices P and Q which are 10 x 20 and 20 x 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

63.

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

a)

6

b)

7

c)

8

d)

9

64.

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

65.

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)

None of the mentioned

66.

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

a)

True

b)

False

67.

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

68.

What is the time complexity of the dynamic programming implementation of the longest common subsequence problem where length of one string is “m” and the length of the other string is “n”?

a)

O(n)

b)

O(m)

c)

O (m + n)

d)

O(mn)

69.

In Greedy method we get ________ Feasible solutions

a)

one

b)

more than one

c)

zero

d)

hundred

70.

Which of the following is true about Huffman Coding.

a)

Huffman coding may become lossy in some cases

b)

Huffman Codes may not be optimal lossless codes in some cases

c)

In Huffman coding, no code is prefix of any other code.

d)

All

71.

The output of Kruskal and Prims algorithm is ________________

a)

Maximum spanning tree

b)

Spanning tree

c)

Minimum spanning tree

d)

None

72.

How do you determine the cost of a spanning tree?

a)

By the sum of costs of the edges of the tree

b)

By the sum of the costs of the edges and vertices of the tree

c)

By the sum of the costs of the vertices of the tree

d)

By the sum of costs of the edges of the graph

73.

A minimum spanning tree has___edges.

a)

(K-1)

b)

(K-1)*1

c)

(V – 1)

d)

NONE OF THE ABOVE

74.

A graph can only have one(1) spanning tree.

a)

TRUE

b)

FALSE

75.

The correct encoding of the letter C in this tree is...

a)

11

b)

10

c)

01

d)

00

76.

How do you move through a Huffman tree?

a)

0 = right 1= left

b)

1 = left 2 = right

c)

0 = left 1 = right

d)

0 = middle 1 = back

77.

Knapsack problem is an example of ________ problem

a)

Maximize

b)

Minimize

c)

Neutralized

d)

Balanced

78.

Which is optimal value in the case of job sequence problem Item : 1 2 3 4 5..

Profit : 20 15 10 5 1

Deadline : 2 2 3 3 3

a)

1,3,4

b)

1,2,4

c)

4,2,3

d)

1,5,2

79.

The right child of Binary search tree always should be

a)

less than root node

b)

greater than root node

c)

should be equal to left child

d)

none

80.

When traversing a binary tree, which diagram is post-order?

a)

b)

c)

81.

When traversing a binary tree, which diagram is pre-order?

a)

b)

c)

82.

Given a binary search tree, insert 27, 15, 63, 99, 70 and 85 (in this order) into the binary search tree. What is the post-order traversal?

a)

5,15,27,34,47,54,63,70,72,75,83,85,88,94,99,101

b)

72,54,34,5,27,15,47,63,70,83,75,88,85,101,94,99

c)

15,27,5,47,34,70,63,54,75,85,99,94,101,88,83,72

d)

15,27,5,47,34,63,54,70,75,85,99,94,101,88,83,72

e)

none of the above

Dynamic Programming

Total questions: 82

Worksheet time: 1hrs 2mins

Similar Resources on Wayground