GATE CSE 2008 Q ||Algorithms || GATE Insights Version: CSE

Planning to take coaching on https://unacademy.com/ here is a code for 10% off PLUS1BPK1 Telegram Notification Group link:- https://t.me/joinchat/X5egW_cvdt9kMGY1 Telegram discussion Group link:- https://t.me/joinchat/VCyGUmVq8RNkMzhl Downloads resources from here https://education4fun.com/gate-cse/ MCQ (Single Correct Answer) GATE CSE 2008 The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 ,a2 ,a3 ,…,an} and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array X, with n rows and W+1 columns. X[i, j], 1 LESS THAN OR EQUAL TO i LESS THAN OR EQUAL TO n, 0 LESS THAN OR EQUAL j LESS THAN OR EQUAL W, is TRUE if and only if there is a subset of {a1 ,a2 ,…,ai} whose elements sum to j.Which of the following is valid for 2 LESS THAN OR EQUAL i LESS THAN OR EQUAL n and ai LESS THAN OR EQUAL j LESS THAN OR EQUAL W? A) X[i, j] = X[i – 1, j] V X[i, j -ai] B) X[i, j] = X[i – 1, j] V X[i – 1, j – ai] C) X[i, j] = X[i – 1, j] V X[i, j – ai] D) X[i, j] = X[i – 1, j] V X[i -1, j – ai]