Cross-concept questions refuse to stay inside one chapter. A stem may mix a paradigm, graph algorithm, data-structure bound and complexity class.
Twelve such questions follow. Eleven come from previous-year papers, with the paper and year printed above each stem. Attempt each one before reading the answer below it. The wider cross-concept set, including the items here that have no solved page of their own, sits in the Algorithm learn module.
Name the paradigm behind the problem
Use canonical anchors: Strassen for divide and conquer, Dijkstra for greedy, optimal BSTs for dynamic programming, and 8-Queens for backtracking. This dynamic programming primer develops that anchor.
Q1. Match the design techniques
UGC NET 2018
Match the following with respect to algorithm paradigms (Design Techniques):
List-I
(a) The 8-Queen's Problem
(b) Single-source shortest path
(c) STRASSEN's Matrix
(d) Optimal binary search trees
List-II
(i) Dynamic Programming
(ii) Divide and Conquer
(iii) Greedy approach
(iv) Backtracking
Options:
(1) (a)-(iv), (b)-(i), (c)-(iii), (d)-(ii)
(2) (a)-(iv), (b)-(iii), (c)-(i), (d)-(ii)
(3) (a)-(iii), (b)-(iv), (c)-(ii), (d)-(i)
(4) (a)-(iv), (b)-(iii), (c)-(ii), (d)-(i)
Answer: (4). 8-Queens places a queen, tests it and undoes it, so (a)-(iv). Dijkstra takes the cheapest frontier edge each step, so (b)-(iii). Strassen splits the matrices and recombines the seven products, so (c)-(ii). Optimal BSTs fill an interval cost table, so (d)-(i). Only option (4) carries all four pairs.
Q2. Find the divide-and-conquer exception
UPPSC Polytechnic Lecturer 2022
Which of the following algorithm does NOT use divide-and-conquer strategy?
(a) Merge sort
(b) Quick sort
(c) Binary sort and Stressian Multiplication
(d) Travelling Salesperson Problem (TSP)
Answer: (d). Merge sort splits, quick sort partitions, binary search halves its range, and Strassen splits matrices. Option (c) is a garbled printing of binary search and Strassen multiplication, and both of those do split and combine. Exact TSP uses dynamic programming or branch and bound, with no clean combine step.
Match an algorithm to its real-world job
Match outputs: Dijkstra gives shortest paths, Huffman a compressed code, KMP substring positions, and Ford-Fulkerson maximum flow. See the wider graph toolkit in this BFS, DFS and shortest paths overview.
Q3. Match algorithms with applications
UGC NET December 2025
Match the LIST-I with LIST-II
LIST-I: A. Dijkstra's Algorithm; B. Huffman Coding; C. KMP string matching; D. Ford-Fulkerson
LIST-II: I. GPS route finding; II. Data compression; III. Text editor search function; IV. Network bandwidth optimization
Choose the correct answer from the options given below:
(a) A-II, B-IV, C-I, D-III
(b) A-I, B-II, C-III, D-IV
(c) A-IV, B-II, C-III, D-I
(d) A-IV, B-III, C-II, D-I
Answer: (b). Road-graph shortest paths give A-I, Huffman compression B-II, KMP text search C-III, and maximum flow D-IV. A-I appears in one option, so it settles the match.
Euclid's GCD in subtraction and remainder form
Both forms preserve the gcd, but remainders move faster. For X = 48 and Y = 18:
(48,18) -> (30,18) -> (12,18) -> (12,6) -> (6,6)
The loop stops at 6. Each move is valid because gcd(X - Y, Y) = gcd(X, Y).
Q4. Read the subtraction loop
Kendriya Vidyalaya Sangathan 2017
Assume X and Y are non-zero positive integers. Consider the following pseudo-code fragment:
while X <> Y do
if X > Y then
X ← X − Y
else
Y ← Y − X
endif
end while
print (X)What is the code doing?
(a) It computes the GCD of two numbers.
(b) It computes the LCM of two numbers.
(c) It finds the smallest of two numbers.
(d) It divides the largest number by the smaller.
Answer: (a). Subtraction preserves the gcd, and termination makes both variables equal to it. The trace prints 6, neither input, rejecting the smallest-number and division traps.
Q5. Count Euclid's recursive calls
Accenture 2023
In the following C function, let n >= m.
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}How many recursive calls are made by this function?
(a) Θ(log n)
(b) Ω(n)
(c) Θ(log log n)
(d) Θ(√n)
Answer: (a). The value at least halves every two calls. Consecutive Fibonacci numbers give the worst shape: gcd(55,34) -> gcd(34,21) -> gcd(21,13) -> gcd(13,8) -> gcd(8,5) -> gcd(5,3) -> gcd(3,2) -> gcd(2,1). That is seven recursive calls for n = 55. Option (b) belongs to the subtraction version of Euclid, which on (n, 1) needs n - 1 turns.
Find the second best with a tournament
A tournament finds the maximum in n - 1 comparisons. The second largest lost to the champion, whose path has ceil(log2 n) opponents. Searching them gives n + ceil(log2 n) - 2 total.
Q6. Worst-case second-smallest comparisons
UGC NET December 2018
The second smallest of n elements can be found with ____ comparisons in the worst case.
(a) n - 1
(b) lg n
(c) n + ceil(lg n) - 2
(d) 3n/2
Answer: (c). Mirror the tournament: n - 1 comparisons find the minimum, then ceil(lg n) - 1 find the smallest direct opponent. The sum is n + ceil(lg n) - 2. The 3n/2 expression is for finding minimum and maximum together.
Q7. Substitute n = 1024
You are given an array of 1024 elements, minimum number of comparisons required to find out second largest element among all will be _______.
(a) 1032
(b) 2045
(c) 1033
(d) 2046
Answer: (a). The bracket takes 1024 - 1 = 1023 comparisons. Since log2 1024 = 10, the champion has 10 direct opponents; their maximum takes 9. Thus 1023 + 9 = 1032. Option (b) is a two-pass count, and (c) is off by one.
Bound Ford-Fulkerson with integer capacities
Each Ford-Fulkerson augmentation raises integer flow by at least 1. There are at most f augmentations, each costing O(E).
Q8. Choose the max-flow runtime
UGC NET July 2018
E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford-Fulkerson algorithm is bounded by:
(a) O(E·f)
(b) O(E²·f)
(c) O(E·f²)
(d) O(E²·f²)
Answer: (a). At most f augmentations times O(E) gives O(E·f). With E = 8 and f = 6, the model gives 6 × 8 = 48 edge-processing units. The bound depends on flow value; Edmonds-Karp uses BFS for a V-and-E bound.
Understand NP-completeness without the fog
NP solutions are polynomial-time checkable. If one NP-complete problem enters P, then P = NP. Exact TSP and integer-programming methods remain exponential in the worst case.
Q9. Classify exact TSP runtime
UGC NET June 2015
The travelling salesman problem can be solved in:
(a) Polynomial time using dynamic programming algorithm
(b) Polynomial time using branch-and-bound algorithm
(c) Exponential time using dynamic programming algorithm or branch-and-bound algorithm
(d) Polynomial time using back tracking algorithm
Answer: (c). Held-Karp is O(n²·2ⁿ), still exponential. At n = 10, 10² × 2¹⁰ = 100 × 1024 = 102400, while 10! = 3628800, about 35.4 times larger. Branch and bound prunes but retains exponential worst-case behaviour. Polynomial exact TSP would imply P = NP.
Q10. Find the true complexity statements
UGC NET 2023
A. If some NP-complete problem P is in P then P = NP
B. TSP is in NP
C. SAT is in NP
D. Hamilton circuit problem is not NP-complete
Choose the correct answer from the options given below:
(a) A, B and C only
(b) B, C and D only
(c) C, D and A only
(d) D, A and B only
Answer: (a). A follows from NP-completeness. TSP tours and SAT assignments are polynomial-time verifiable, so B and C hold. D is false because Hamiltonian circuit is NP-complete. Choose the option omitting D.
Q11. Separate ILP from PERT
UGC NET December 2022
Consider the statements:
A. There does not exist a polynomial time algorithm to solve integer linear programming problem.
B. Main focus of PERT is 'minimizing time'.
Choose the correct option about the statements A and B.
(a) A is True; B is True
(b) A is True; B is False
(c) A is False; B is True
(d) A is False; B is False
Answer: (b). Integer linear programming is NP-hard and no polynomial-time exact algorithm is known for it, so A is true. Linear programming itself is polynomial. PERT models uncertain activity times rather than minimising time, so B is false.
Remember the red-black tree height bound
A red-black tree has a black root, no red-red edge, and equal black counts on root-to-leaf paths. The longest path can alternate colours while the shortest is all black, giving height at most 2·log2(n + 1).
Q12. Apply the red-black height bound
DSSSB 2021
What is the at most height of a red-black tree with n internal nodes?
(a) n
(b) log₂ n
(c) 2 log₂ (n + 1)
(d) log₂ (2n + 1)
Answer: (c). At n = 15, 2·log2(16) = 2 × 4 = 8. Perfect balance is about log2 16 = 4, so red-black height stays within a factor of two. Option (a) is a degenerate BST; (b) demands perfect balance.
The short version and your next step
Paradigm matches are won with canonical examples.
Application matches start from what each algorithm outputs.
Remainder-based Euclid takes Θ(log n) recursive calls.
Second best takes n + ceil(lg n) - 2 comparisons, which is 1032 at n = 1024.
Integer-capacity Ford-Fulkerson is O(E·f).
TSP, SAT and Hamiltonian circuit anchor NP questions, while red-black height is at most 2·log2(n + 1).
Practise the solved pages inside the Coding for Placements course, then browse more CS fundamentals for placements.
