Ratings are approximate, based on recurring patterns in past GATE CSE papers.
Previous year questions
7 real questions from the official GATE CSE papers (2014 to 2024), newest first, each with the official answer key and a worked solution. Questions are the property of the GATE organising institutes; this copy is for your personal study.
7 questions · 0 correct of 0 attempted · marks 0 / 12
Year:
GATE 2024 CS2 · Q35NAT1 mark
Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array [2, 5, 3, 1, 4, 2, 6] is ______.
GATE 2024 CS2 · Q42MCQ2 marks
Consider an array X that contains n positive integers. A subarray of X is a sequence of array locations with consecutive indices. The C code snippet below computes the length of the longest subarray of X that contains at most two distinct integers, with two missing expressions (P) and (Q):
int first = 0, second = 0, len1 = 0, len2 = 0, maxlen = 0;
for (i = 0; i < n; i++) {
if (X[i] == first) {
len2++;
len1++;
} else if (X[i] == second) {
len2++;
len1 = (P);
second = first;
} else {
len2 = (Q);
len1 = 1;
second = first;
}
if (len2 > maxlen) maxlen = len2;
first = X[i];
}
(Hint: at the end of the i-th iteration, len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)
GATE 2021 Set 1 · Q40MSQ2 marks
Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices: p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18. Which of the following statements is/are correct about R7?
One or more options may be correct. Select all that apply, then submit.
GATE 2019 Set 2 · Q25NAT1 mark
Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0]. The subsequence sum S(i, j) = Σk=i..j A[k]. Determine the maximum of S(i, j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used.) Answer: ______.
GATE 2018 · Q31MCQ2 marks
Assume that multiplying a matrix G1 of dimension p × q with another matrix G2 of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G1G2…Gn can be done by parenthesizing in different ways. Define GiGi+1 as an explicitly computed pair for a given parenthesization if they are directly multiplied. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2 × 25, 25 × 3, 3 × 16, 16 × 1 and 1 × 1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pair(s) is/are
GATE 2018 · Q48NAT2 marks
Consider the weights and values of items listed below. Note that there is only one unit of each item. Items (weight in Kg, value in rupees): 1 (10, 60), 2 (7, 28), 3 (4, 20), 4 (2, 24). The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy. The value of Vopt − Vgreedy is ______.
GATE 2014 Set 1 · Q49NAT2 marks
A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1, 1, 2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1, 1)} and the set of all 3-pennants is {(2, 1), (1, 1, 1), (1, 2)}. Note that the pennant (1, 2) is not the same as the pennant (2, 1). The number of 10-pennants is ______.
Common traps
Greedy for 0/1 knapsack is wrong; greedy for fractional knapsack is right.
LCS needs O(mn) space for the full table, but only two rows if you need only the length.
Matrix chain minimises the number of scalar multiplications, and the dimension array has n + 1 entries for n matrices.
O(nW) is pseudo-polynomial: W can be exponential in its bit length.