NEW
Font size
S
M
L
XL
WorksheetsISCP 04 Tuesday slot 1 (09:00 - 11:00) CSE A&C
Total questions: 20
Worksheet time: 20mins
Name
Class
Date
1.
In dynamic programming, the technique of storing the previously calculated values is called ___________
a)
Saving value property
b)
Storing value property
c)
Memoization
d)
Mapping
2.
The following sequence is a fibonacci sequence:
0, 1, 1, 2, 3, 5, 8, 13, 21,…..
Which technique can be used to get the nth fibonacci term?
a)
Recursion
b)
Dynamic programming
c)
single for loop
d)
Recursion, Dynamic Programming, For loops
3.
Find the length of the longest increasing subsequence for the given sequence:
{-10, 24, -9, 35, -21, 55, -41, 76, 84}
a)
5
b)
4
c)
3
d)
6
4.
What is the worst case for linear search?
a)
O(nlogn)
b)
O(logn)
c)
O(n)
d)
O(1)
5.
Longest increasing subsequence problem can be optimally solved by
a)
Greedy method
b)
Divide & conquer
c)
Dynamic programming
d)
None of these
6.
Given items as {value, weight} pairs {{60,20},{50,25},{20,5}}. The capacity of the knapsack=40.
Find the maximum value output assuming items to be divisible and non-divisible respectively.
a)
100, 80
b)
110, 80
c)
130, 110
d)
110, 70
7.
Consider the below table for Jobs given with profit and deadline.
Job J1 J2 J3 J4 J5 J6 J7 J8 J9
Profit 20 25 35 23 23 15 28 21 30
Deadline 7 2 5 3 4 5 2 7 3
Find the maximum profit earned?
a)
185
b)
182
c)
170
d)
None
8.
The time and space compexitites of longest common subsequence problem of two strings with lengths m, n respectively using dynamic programming?
a)
O(m! * n!), O(1)
b)
O(m**2), O(n**2)
c)
O(m * n), O(m * n)
d)
O(2**m), O(1)
9.
You are given a rod of length 5 and the prices of each length are as follows:
length price
1 2
2 5
3 6
4 9
5 9
What is the maximum value that you can get after cutting the rod and selling the pieces?
a)
10
b)
11
c)
12
d)
13
10.
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)
160
b)
200
c)
170
d)
90
11.
You are given infinite coins of N denominations v1, v2, v3,…..,vn and a sum S. The coin change problem is to find the minimum number of coins required to get the sum S. What is the time complexity of a dynamic programming implementation used to solve the coin change problem?
a)
O(N)
b)
O(S)
c)
O(N2)
d)
O(S*N)
12.
Which of the following is an example of greedy approach?
a)
priority queue
b)
0/1 knapsack
c)
n-queens problem
d)
longest common substring
13.
You are given a knapsack that can carry a maximum weight of 20. There are 5 items with values
{21, 24, 12, 40, 30} and weights {7, 4, 6, 5, 6}. What is the maximum value of the items you can carry using the fractional knapsack?
a)
90
b)
109
c)
91
d)
100
14.
Which of the following problem must not be solved using dynamic programming?
a)
0/1 knapsack problem
b)
Matrix chain multiplication problem
c)
Edit distance problem
d)
Fractional knapsack problem
15.
The property in which optimal solution is found by constructing optimal solution for the subproblems.
a)
Overlapping subproblems
b)
Memoization
c)
Optimal substructure
d)
Greedy
16.
Time complexity of coin change problem solved using greedy technique is
a)
O(nlogn)
b)
O(n)
c)
O(n^2)
d)
none
17.
Which of the following statement is correct about 0/1 knapsack?
a)
Items are divisible
b)
It is same as fractional knapsack
c)
It can be solved using greedy technique
d)
Items are indivisible
18.
In Dynamic programming which of the following method does not consist recursion?
a)
memoization
b)
merging
c)
tabulation
d)
none
19.
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
20.
In dynamic programming top-down approach is also known as____
a)
tabulation
b)
memoization
c)
optimization
d)
generalization
Reset
