The GATE Grind

GATE Algorithms: Dynamic Programming – Previous Year Questions

16 GATE previous year questions on Dynamic Programming (Algorithms, Computer Science) with answers and explanations, from every paper.

16 questions worth 29 marks in all (3 1-mark, 13 2-mark). Asked between 2008 and 2026, so you can see how the topic has been tested over time.

  1. GATE 2008 CS Q80 (2 marks, Multiple choice) – Given positive integers S=\a 1,,a n\ and positive W, subset sum asks whether some subset sums to W. Boolean X[i, j], with n rows and W+1 columns…
  2. GATE 2008 CS Q81 (2 marks, Multiple choice) – Given positive integers S=\a 1,,a n\ and positive W, subset sum asks whether some subset sums to W. Boolean X[i, j], with n rows and W+1 columns…
  3. GATE 2009 CS Q53 (2 marks, Multiple choice) – A subsequence deletes any number of elements while preserving order. X[m], Y[n] are sequences of lengths m, n, indexed from0. Let l(i, j) be their…
  4. GATE 2009 CS Q54 (2 marks, Multiple choice) – A subsequence deletes any number of elements while preserving order. X[m], Y[n] are sequences of lengths m, n, indexed from0. Let l(i, j) be their…
  5. GATE 2010 CS Q44 (2 marks, Multiple choice) – The weight of a sequence a 0,,a n-1 is a 0+a 1/2++a n-1/2n-1. Subsequences preserve order and may delete elements. Let X be the maximum subsequence…
  6. GATE 2011 CS Q35 (1 mark, Multiple choice) – For A[0…n−1], define Lᵢ as the longest monotonically increasing run beginning at i. Set Lₙ₋₁=1 and for earlier i, Lᵢ=1+Lᵢ₊₁ if A[i]<A[i+1], otherwise…
  7. GATE 2011 CS Q48 (2 marks, Multiple choice) – Matrices M₁,M₂,M₃,M₄ have dimensions p×q,q×r,r×s,s×t. With p=10,q=100,r=20,s=5,t=80, find minimum scalar multiplications.
  8. GATE 2016 CS (CS2) Q24 (1 mark, Multiple choice) – Which paradigm underlies Floyd–Warshall all-pairs shortest paths?
  9. GATE 2016 CS (CS2) Q48 (2 marks, Numerical answer) – Matrices A₁,A₂,A₃,A₄ have dimensions 10×5, 5×20, 20×10 and 10×5. Find the minimum scalar-multiplication count for A₁A₂A₃A₄ using ordinary matrix…
  10. GATE 2014 CS (CS3) Q47 (2 marks, Numerical answer) – To move from 0 to 100 on the number line, each step moves right one unit or uses a prespecified shortcut (i,j), i < j, directly from i to j. At most…
  11. GATE 2014 CS (CS2) Q47 (2 marks, Numerical answer) – A = “qpqrr”, B = “pqprqrp”. Let x be their longest common subsequence length (not necessarily contiguous), and y the number of such longest common…
  12. GATE 2018 CS Q41 (2 marks, Multiple choice) – Assume that multiplying a matrix G 1 of dimension p q with another matrix G 2 of dimension q r requires pqr scalar multiplications. Computing the…
  13. GATE 2026 CS (CS2) Q39 (2 marks, Multiple choice) – Consider a table T where the entries T[i][j], 0 i,j n, represent costs of subproblems in a dynamic programming algorithm. The recursive formulation is…
  14. GATE 2024 CS (CS2) Q35 (1 mark, Numerical answer) – 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…
  15. GATE 2024 CS (CS2) Q42 (2 marks, Multiple choice) – Consider an array X of n positive integers. The C code below computes the length of the longest subarray of X containing at most two distinct…
  16. GATE 2021 CS (CS1) Q50 (2 marks, Multiple select) – Define R n 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,…