Font size
WorksheetsAdvance data-structures
Total questions: 20
Worksheet time: 11mins
Dynamic Programming is often used for (choose all that apply):
Optimization problems that involve making a choice that leave one or more subproblems to be solved.
Problems previously solved using divide and conquer that have over lapping subproblems
Non polynomial solution problems
Subproblems where resources are shared
.................technique doesn't give guarantee that our solution is optimal
greedy method
dynamic programming approach
backtracking
branch and bound
Which of the following problems is equivalent to the 0-1 Knapsack problem?
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
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
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
None of the mentioned
If b is the source vertex, what is the minimum cost to reach f vertex?
8
9
6
4
...........................technique is used by solving optimization problems
divide and conquer
greedy method
dynamic programming
both b and c
Which of the following is/are property/properties of a dynamic programming problem?
Optimal substructure
Overlapping subproblems
Greedy approach
d) Both optimal substructure and overlapping subproblems
In dynamic programming, the technique of storing the previously calculated values is called ___________
Saving value property
Storing value property
Memorization
Mapping
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?
170
200
160
90
Time complexity of fractional knapsack problem is (a)
1
2
3
all
Fractional knapsack problem is solved most efficiently by which of the following algorithm?
(a)
The algorithms like merge sort, quick sort and binary search are based on
Greedy algorithm
Divide and Conquer algorithm
Hash table
Parsing
In dynamic programming, the technique of storing the previously calculated values is called ___________
Saving value property
Storing value property
Memorization
Mapping
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”?
O(n)
O(m)
O (m + n)
O(mn)
_________ approach is best to solve 0/1 Knapsack problem
Greedy
Divide and Conquer
Dynamic Programming
Iterative
Consider a job scheduling problem with 4 jobs J1, J2, J3, J4 and with corresponding deadlines: ( d1, d2, d3, d4) = (4, 2, 4, 2). Which of the following is not a feasible schedule without violating any job schedule?
J2, J4, J1, J3
J4, J1, J2, J3
J4, J2, J1, J3
J4, J2, J3, J1
Consider the following two sequences :
The length of longest common subsequence of X and Y is :Consider the following two sequences :
X = < B, C, D, C, A, B, C >, and Y = < C, A, D, B, C, B >
The length of longest common subsequence of X and Y is :
5
3
4
2
