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.
- GATE 2008 CS Q80 – 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…
- GATE 2008 CS Q81 – 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…
- GATE 2009 CS Q53 – 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…
- GATE 2009 CS Q54 – 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…
- GATE 2010 CS Q44 – 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…
- GATE 2011 CS Q35 – 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…
- GATE 2011 CS Q48 – 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.
- GATE 2016 CS (CS2) Q24 – Which paradigm underlies Floyd–Warshall all-pairs shortest paths?
- GATE 2016 CS (CS2) Q48 – 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…
- GATE 2014 CS (CS3) Q47 – 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…
- GATE 2014 CS (CS2) Q47 – A = “qpqrr”, B = “pqprqrp”. Let x be their longest common subsequence length (not necessarily contiguous), and y the number of such longest common…
- GATE 2018 CS Q41 – 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…
- GATE 2026 CS (CS2) Q39 – 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…
- GATE 2024 CS (CS2) Q35 – 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…
- GATE 2024 CS (CS2) Q42 – 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…
- GATE 2021 CS (CS1) Q50 – 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,…