ISCP 04 Monday slot 1 (10:30 - 12:00) CSE D&H

Longest increasing subsequence problem can be optimally solved by

• Greedy method
• Divide & conquer
• Dynamic programming
• None of these

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.

• 100, 80
• 110, 70
• 130, 110
• 110, 80

The time complexity of fractional knapsack problem is?

• O(nlogn)
• O(n)
• O(n2)
• O(nW)

Which of the following statement is correct about 0/1 knapsack?

• Items are divisible
• It is same as fractional knapsack
• It can be solved using greedy technique
• Items are indivisible

Which of the following problem must not be solved using dynamic programming?

• 0/1 knapsack problem
• Matrix chain multiplication problem
• Edit distance problem
• Fractional knapsack problem

The property in which optimal solution is found by constructing optimal solution for the subproblems.

• Overlapping subproblems
• Optimal substructure
• Memoization
• Greedy

Time complexity of coin change problem solved using greedy technique is

• O(logn)
• O(n)
• O(n^2)
• None of these

What cannot be used to represent an algorithm?

• Flowchart
• Pseudocode
• Program
• Syntax

Which property differentiates dynamic programming with divide and conquer technique?

• Optimal solution
• Optimal substructure
• Overlapping subproblems
• None

Which of the following is not a property of dynamic programming problem?

• Always give the optimal solution
• Optimal substructure
• Overlapping subproblems
• Greedy approach