GATE CSE Dynamic Programming – Algorithms Practice Test

Question 1

MCQ · Single Correct 1 mark

In Dynamic Programming, what are the two essential properties a problem must possess to be efficiently solved using DP?

A Overlapping Subproblems and Optimal Substructure B Divide and Conquer and Independence C Polynomial Time Solvability and Determinism D Greedy Choice Property and Optimal Substructure

Question 2

MCQ · Single Correct 1 mark

What is the time complexity of the standard Dynamic Programming solution for the 0/1 Knapsack problem with n items and knapsack capacity W?

A O(n log W) B $O(W^2)$ C O(n * W) D $O(2^n)$

Question 3

MCQ · Single Correct 2 mark

Why is the O(n * W) Dynamic Programming algorithm for 0/1 Knapsack classified as PSEUDO-POLYNOMIAL time?

A Because W is represented in $\log(W) bits, making$ the running time exponential in the input size of W B Because it uses floating point arithmetic C Because it is an approximation algorithm D Because it only works when weights are real numbers

Question 4

MCQ · Single Correct 1 mark

In 0/1 Knapsack DP table K[i][w], what does cell K[i][w] represent?

A Minimum weight required to achieve at least value i using w items B Maximum value obtainable using a subset of the first i items with total weight at most w C Maximum weight that can be packed using i items D Total number of subsets of first i items with weight exactly w

Question 5

MCQ · Single Correct 2 mark

What is the standard recurrence relation for 0/1 Knapsack K[i][w] when considering item i with weight $w_{i}$ and value $v_{i}$ (for w >= $w_{i}$)?

A $K[i][w] = max(K[i-1][w], v_{i} + K[i-1][w - w_{i}])$ B $K[i][w] = max(K[i-1][w], v_{i} + K[i][w - w_{i}])$ C $K[i][w] = min(K[i-1][w], K[i-1][w - w_{i}])$ D $K[i][w] = K[i-1][w] + v_{i}$