Dynamic Programming: GATE CS previous year questions (Algorithms)

GATE CS 2026 Set 2MCQ2 marksMedium (estimate)
GATE CS 2026 Set 2, Q.39
Consider a table $T$ , where the elements $T [i] [j]$ , $0 \leq i, j \leq n$ , represent the cost of the optimal solutions of different subproblems of a problem that is being solved us...
Dynamic Programming
GATE CS 2024 Set 2NAT1 markMedium (estimate)
GATE CS 2024 Set 2, Q.35
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 res...
Dynamic Programming
GATE CS 2024 Set 2MCQ2 marksMedium (estimate)
GATE CS 2024 Set 2, Q.42
Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code snippet given be...
Dynamic Programming · Data Types, Operators and Control Flow
GATE CS 2021 Set 1MSQ2 marksMedium (estimate)
GATE CS 2021 Set 1, Q.50 (CS Q.40)
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$ , let $p [i]$ denote the...
Dynamic Programming
GATE CS 2021 Set 2NAT2 marksMedium (estimate)
GATE CS 2021 Set 2, Q.65 (CS Q.55)
In a directed acyclic graph with a source vertex $s$ , the quality-score of a directed path is defined to be the product of the weights of the edges on the path. Further, for a v...
Dynamic Programming
GATE CS 2018MCQ2 marksMedium (estimate)
GATE CS 2018, Q.41 (CS Q.31)
Assume that multiplying a matrix $G_{1}$ of dimension $p \times q$ with another matrix $G_{2}$ of dimension $q \times r$ requires $pq r$ scalar multiplications. Computing the product...
Dynamic Programming
GATE CS 2018NAT2 marksMedium (estimate)
GATE CS 2018, Q.58 (CS Q.48)
Consider the weights and values of items listed below. Note that there is only one unit of each item. Item number Weight (in Kgs) Value (in Rupees) 1 10 60 2 7 28 3 4 20 4 2 24...
Dynamic Programming
GATE CS 2017 Set 1MCQ1 markEasy (estimate)
GATE CS 2017 Set 1, Q.5 (CS Q.5)
Consider the following table: Algorithm Design Paradigm (P) Kruskal (i) Divide and Conquer (Q) Quicksort (ii) Greedy (R) Floyd-Warshall (iii) Dynamic Programming Match the algor...
Greedy Algorithms · Dynamic Programming · Divide and Conquer
GATE CS 2016 Set 2MCQ1 markEasy (estimate)
GATE CS 2016 Set 2, Q.24 (CS Q.14)
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
Dynamic Programming
GATE CS 2016 Set 2NAT2 marksMedium (estimate)
GATE CS 2016 Set 2, Q.48 (CS Q.38)
Let $A_{1}, A_{2}, A_{3},$ and $A_{4}$ be four matrices of dimensions $10 \times 5$ , $5 \times 20$ , $20 \times 10$ , and $10 \times 5$ , respectively. The minimum number of scalar multipl...
Dynamic Programming
GATE CS 2015 Set 2MCQ2 marksEasy (estimate)
GATE CS 2015 Set 2, Q.46 (CS Q.36)
Given below are some algorithms, and some algorithm design paradigms. List-I 1. Dijkstra's Shortest Path 2. Floyd-Warshall algorithm to compute all pairs shortest path 3. Bi...
Dynamic Programming
GATE CS 2014 Set 2NAT2 marksMedium (estimate)
GATE CS 2014 Set 2, Q.47 (CS Q.37)
Consider two strings $A = "qpqrr"$ and $B = "pqprqrp"$ . Let $x$ be the length of the longest common subsequence (not necessarily contiguous) between $A$ and $B$ an...
Dynamic Programming
GATE CS 2014 Set 3NAT2 marksEasy (estimate)
GATE CS 2014 Set 3, Q.47 (CS Q.37)
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified...
Dynamic Programming
GATE CS 2011MCQ1 markEasy (estimate)
GATE CS 2011, Q.25 (CS Q.25)
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array $A [0 : n - 1]$ is given below. Let $L_{i}$ denote the length of the longest mon...
Dynamic Programming
GATE CS 2011MCQ2 marksMedium (estimate)
GATE CS 2011, Q.38 (CS Q.38)
Four matrices $M_{1}, M_{2}, M_{3}$ and $M_{4}$ of dimensions $p \times q$ , $q \times r$ , $r \times s$ and $s \times t$ respectively can be multiplied in several ways with different num...
Dynamic Programming

Questions

Other topics of Algorithms