Advance data-structures

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

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

• Optimal substructure
• Overlapping subproblems
• Greedy approach
• Both optimal substructure and overlapping subproblems

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