NEW
Font size
S
M
L
XL
WorksheetsISCP 04 Monday slot 1 (10:30 - 12:00) CSE D&H
Total questions: 20
Worksheet time: 20mins
Name
Class
Date
1.
Longest increasing subsequence problem can be optimally solved by
a)
Greedy method
b)
Divide & conquer
c)
Dynamic programming
d)
None of these
2.
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, 70
c)
130, 110
d)
110, 80
3.
The time complexity of fractional knapsack problem is?
a)
O(nlogn)
b)
O(n)
c)
O(n2)
d)
O(nW)
4.
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
5.
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
6.
The property in which optimal solution is found by constructing optimal solution for the subproblems.
a)
Overlapping subproblems
b)
Optimal substructure
c)
Memoization
d)
Greedy
7.
Time complexity of coin change problem solved using greedy technique is
a)
O(logn)
b)
O(n)
c)
O(n^2)
d)
None of these
8.
What cannot be used to represent an algorithm?
a)
Flowchart
b)
Pseudocode
c)
Program
d)
Syntax
9.
Which property differentiates dynamic programming with divide and conquer technique?
a)
Optimal solution
b)
Optimal substructure
c)
Overlapping subproblems
d)
None
10.
Which of the following is not a property of dynamic programming problem?
a)
Always give the optimal solution
b)
Optimal substructure
c)
Overlapping subproblems
d)
Greedy approach
11.
What could be the correct definition of greedy algorithm?
a)
Solving a problem by breaking it down into smaller sub problems
b)
Generating all possible solutions and selecting the best one
c)
Repeating the same steps over and over until a solution is found
d)
Making the locally optimal choice at each stage to obtain a global optimal solution
12.
Which method may or may not give the optimal solution?
a)
Divide and conquer
b)
Dynamic programming
c)
Greedy method
d)
None of these
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)
109
b)
90
c)
91
d)
100
14.
Which algorithm can be used to solve knapsack problem?
a)
Brute force algorithm
b)
Recursion
c)
Dynamic programming
d)
All of the mentioned
15.
What is the objective of the knapsack problem?
a)
To get maximum profit
b)
To get minimum profit
c)
To get maximum weight
d)
To get minimum weight
16.
In dynamic programming, previously calculated values are stored, this technique is called as
a)
Saving value property
b)
Storing value property
c)
Memoization
d)
Mapping
17.
The time complexity to solve 0/1 knapsack using brute force algorithm?
a)
O(n**2)
b)
O(n!)
c)
O(2**n)
d)
O(n**3)
18.
The complexity of 0/1 knapsack, if number objects n and the capacity of knapsack m is given,
a)
O(m**2)
b)
O(m*n)
c)
O(2**n)
d)
O(n**2)
19.
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)
20.
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)
182
b)
185
c)
170
d)
None
Reset
