Advanced dynamic programming questions rarely ask you to write a recurrence. They ask you to place an algorithm in its paradigm, attach a complexity to a name, and judge statements about what dynamic programming does and does not guarantee. GATE and UGC NET lean on all three habits, ISRO recycles the same complexity facts, and the same handful of names keeps returning: Dijkstra, Kruskal, Prim, Floyd-Warshall, Bellman-Ford, Huffman, topological sort and matrix chain. Attempt each question before reading its answer. If the paradigm names themselves feel loose, work through Dynamic Programming Explained with a Worked 0/1 Knapsack first.
1. Spotting the design paradigm
Memorise these anchors: Dijkstra, Prim, Kruskal and Huffman are greedy; Floyd-Warshall, matrix chain, LCS and optimal triangulation use DP; binary search and merge sort use divide and conquer; subset-sum search and graph backtracking use DFS.
Q1. GATE 2015
Given below are some algorithms, and some algorithm design paradigms.
Algorithm | Design paradigm |
|---|---|
1. Dijkstra's Shortest Path | i. Divide and Conquer |
2. Floyd-Warshall algorithm to compute all pairs shortest path | ii. Dynamic Programming |
3. Binary search on a sorted array | iii. Greedy design |
4. Backtracking search on a graph | iv. Depth-first search |
v. Breadth-first search |
Match the above algorithms on the left to the corresponding design paradigm they follow.
Options: (a) 1-i, 2-iii, 3-i, 4-v (b) 1-iii, 2-iii, 3-i, 4-v (c) 1-iii, 2-ii, 3-i, 4-iv (d) 1-iii, 2-ii, 3-i, 4-v
Answer: (c). Dijkstra picks the closest unsettled vertex greedily. Floyd-Warshall uses intermediate-vertex subproblems. Binary search halves the instance. Backtracking explores depth-first, so BFS is the distractor.
Q2. UGC NET 2017
Match the following with respect to algorithm paradigms :
a. Merge sort :: i. Dynamic programming
b. Huffman coding :: ii. Greedy approach
c. Optimal polygon triangulation :: iii. Divide and conquer
d. Subset sum problem :: iv. Back tracking
Options: (a) a-iii, b-i, c-ii, d-iv (b) a-ii, b-i, c-iv, d-iii (c) a-ii, b-i, c-iii, d-iv (d) a-iii, b-ii, c-i, d-iv
Answer: (d). Merge sort splits and merges. Huffman greedily combines the two lowest frequencies. Optimal polygon triangulation is interval DP. Subset sum here uses backtracking. NET repeats this matching, so learn the mapping.
2. What DP actually guarantees: statements and memoization
Top-down memoization and bottom-up tabulation solve the same set of subproblems, so they normally carry the same asymptotic bound. Memoization reaches only the states your instance needs and pays recursion overhead; tabulation fills every state in a fixed order. Neither is automatically faster, and statement questions punish that assumption.
Q3. UGC NET 2019
Consider the following statements:
(a) The running time of dynamic programming algorithm is always θ(ρ) where ρ is number of subproblems
(b) When a recurrence relation has a cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program.
(c) For a dynamic programming algorithm, computing all values in a bottom-up fashion is asymptotically faster than using recursion and memorization
(d) If a problem X can be reduced to a known NP-hard problem, then X must be NP-hard
Which of the statement(s) is (are) true?
Options: (a) Only (b) and (a) (b) Only (b) (c) Only (b) and (c) (d) Only (b) and (d)
Answer: (b). Statement (a) fails: LCS uses mn constant-work states, while matrix chain uses O(n²) states with O(n) splits each. Statement (b) is true because a cycle prevents an evaluation order. Statement (c) fails because bottom-up and memoized top-down can be asymptotically equal. Statement (d) reverses the reduction: reduce a known NP-hard problem to X.
Q4. GATE 2011
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 monotonically increasing sequence starting at index i in the array. Initialize L[n-1] = 1. For all i such that 0 <= i <= n-2:
L[i] = 1 + L[i+1] if A[i] < A[i+1], and 1 otherwise.
Finally, the length of the longest monotonically increasing sequence is max(L[0], L[1], ..., L[n-1]). Which of the following statements is TRUE?
Options: (a) The algorithm uses dynamic programming paradigm (b) The algorithm has a linear complexity and uses branch and bound paradigm (c) The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm (d) The algorithm uses divide and conquer paradigm
Answer: (a). Each L[i] is built from the already-solved L[i+1] and stored for reuse, which is optimal substructure plus tabulation, so the paradigm is DP. The scan is linear, but not branch-and-bound search; nothing is split and recombined for divide and conquer.
For A = [5, 7, 2, 4, 9, 1]: L[5]=1; L[4]=1 because 9 > 1; L[3]=1+L[4]=2 because 4 < 9; L[2]=1+L[3]=3 because 2 < 4; L[1]=1 because 7 > 2; and L[0]=1+L[1]=2 because 5 < 7. So max(L[0], ..., L[5])=3, from the run 2, 4, 9.
3. Knapsack: its problem class, and the order of the DP steps
Q5. Infosys 2024
To which of the following domain problem does the knapsack problem belong?
Options: (a) NP-complete (b) Sorting (c) Optimization (d) Linear Solution
Answer: (c). Knapsack maximises value under a weight constraint, so its domain is optimization. Its 0/1 decision version is NP-complete, but this question asks for the domain.
Q6. UGC NET 2024
Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.
(A) Define the base case when the capacity is zero (0) or no items are left to consider
(B) Compute the maximum value that can be obtained using items up to the i-th item and a knapsack capacity of 0
(C) Identify subproblems and their dependencies based on items weights and values
(D) Initialize a table to store results of subproblems
(E) Iterate through each item and each possible Capacity to fill the table
Choose the correct answer from the options given below:
Options: (a) (C), (D), (A), (E), (B) (b) (D), (C), (A), (E), (B) (c) (A), (C), (D), (E), (B) (d) (D), (A), (C), (E), (B)
Answer: (c). The base case (A) comes first because zero capacity and no items left are the boundary values the table's first row and column must already hold. Then identify the subproblems and their dependencies (C) so the table's dimensions follow from the item and capacity ranges, initialize it (D), and fill it item by item and capacity by capacity (E). Step (B) is the read-out, and the value you want sits in the cell for all items at the target capacity.
4. Matching algorithms to time complexities, part 1
Anchor the complexities you are sure of, then eliminate. If those anchors are shaky, the pairings get drilled harder in Time Complexity MCQs: 12 Solved on Big-O (GATE).
Q7. UGC NET 2014
Match the following :
a. Bucket sort :: i. O(n^3 lg n)
b. Matrix chain multiplication :: ii. O(n^3)
c. Huffman codes :: iii. O(n lg n)
d. All pairs shortest paths :: iv. O(n)
Codes :
Options: (a) a-iv, b-ii, c-i, d-iii (b) a-ii, b-iv, c-i, d-iii (c) a-iv, b-ii, c-iii, d-i (d) a-iii, b-ii, c-iv, d-i
Answer: (c). Bucket sort averages O(n), matrix chain takes O(n³), and heap-based Huffman O(n lg n). The remaining O(n³ lg n) is repeated-squaring all-pairs, not Floyd-Warshall, whose O(n³) slot is used.
Q8. UGC NET 2018
Match List I with List II and choose the correct answer from the code given below.
(a) Dijkstra's algorithm :: (i) O(E lg E)
(b) Kruskal's algorithm :: (ii) Θ(V^3)
(c) Floyd-Warshall algorithm :: (iii) O(V^2)
(d) Topological sorting :: (iv) Θ(V+E)
where V and E are the number of vertices and edges in graph respectively.
Options: (a) (a)-(i), (b)-(iii), (c)-(ii), (d)-(iv) (b) (a)-(iii), (b)-(i), (c)-(ii), (d)-(iv) (c) (a)-(i), (b)-(iii), (c)-(iv), (d)-(ii) (d) (a)-(iii), (b)-(i), (c)-(iv), (d)-(ii)
Answer: (b). Matrix-based Dijkstra is O(V²), Kruskal's edge sort is O(E lg E), Floyd-Warshall's triple loop is Θ(V³), and one DFS or BFS topological pass is Θ(V+E).
5. Matching algorithms to time complexities, part 2
The same anchors work with n and m, even when one forced pairing is non-standard.
Q9. GATE 2005
In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.
Bellman-Ford algorithm :: A : O(m log n)
Kruskal's algorithm :: B : O(n^3)
Floyd-Warshall algorithm :: C : O(nm)
Topological sorting :: D : O(n + m)
Options: (a) 1→C, 2→A, 3→B, 4→D (b) 1→B, 2→D, 3→C, 4→A (c) 1→C, 2→D, 3→A, 4→B (d) 1→B, 2→A, 3→C, 4→D
Answer: (a). Bellman-Ford relaxes m edges n-1 times, O(nm). Kruskal is O(m log n), Floyd-Warshall O(n³), and topological sorting O(n+m). Three of these four pairings are Q8's, written in n and m instead of V and E; only Bellman-Ford is new.
Q10. UGC NET 2020
Match list I with II
(A) Topological sort of DAG :: (I) O(V+E)
(B) Kruskal's MST algorithm :: (II) O(VE)
(C) Bellman-Ford's single-source shortest path algorithm :: (III) θ(V+E)
(D) Floyd-Warshall's all pair shortest path algorithm :: (IV) θ(V^3)
Choose the correct answer from the options given below:
Options: (a) A-I, B-III, C-IV, D-II (b) A-III, B-I, C-IV, D-II (c) A-III, B-I, C-II, D-IV (d) A-I, B-III, C-II, D-IV
Answer: (c). Anchor topological sort at θ(V+E), Bellman-Ford at O(VE), and Floyd-Warshall at θ(V³). Elimination gives Kruskal the remaining O(V+E), despite its textbook O(E log E). Three sure pairs decide the non-standard fourth.
6. DP on graphs and relations
Q11. ISRO 2017
The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be
Options: (a) O(n*log(n)) (b) O(n^(3/2)) (c) O(n^3) (d) O(n)
Answer: (c). Treat the relation as a directed graph. Warshall, the Boolean cousin of Floyd-Warshall, computes reachability using three loops over n, so it takes O(n³).
Q12. UGC NET 2022
Match List I with List II
A. Dijkstra's Algorithm :: I. Calculates path matrix
B. Prim's Algorithm :: II. Stores minimum cost edge
C. Warshall's Algorithm :: III. Stores the total cost from a source node to the current node
D. Kruskal's algorithm :: IV. Finds Minimum Spanning Tree
Choose the correct answer from the options given below:
Options: (a) A-I, B-II, C-III, D-IV (b) A-III, B-II, C-I, D-IV (c) A-II, B-I, C-IV, D-III (d) A-III, B-IV, C-II, D-I
Answer: (b). Dijkstra stores source cost (III). Prim stores the minimum cost edge (II). Warshall calculates the path matrix (I), Q11's transitive closure. Kruskal builds an MST (IV).
7. How GATE and UGC NET keep testing dynamic programming, and what to revise next
Seven of the twelve are match-the-list questions: two pair algorithms with paradigms, four with time complexities, one with what each algorithm computes. The other five judge statements about dynamic programming, name the paradigm behind a recurrence, place knapsack in a problem class, order the knapsack DP steps, and recall one complexity outright. Those papers run from GATE 2005 to UGC NET 2024, so the format is stable.
Redo all twelve cold after a week. A pairing you answer from memory beats one you reconstruct under exam pressure. For the full theory sequence, work through GATE Guidance by Sanchit Sir and the GATE CS exam preparation courses and test series. If the graph names are the part that slipped, trace them again in Graph Algorithms: BFS, DFS and Dijkstra Traced Step by Step.
One drill beats rereading. Cover the right-hand column of the complexity table above, recite each figure from memory, then revise only the rows you missed.
