Match the following :

(a)

Merge sort

(i)

Greedy approach

(b)

8 Queens problem

(ii)

Dynamic programming

(c)

Single source shortest path

(iii)

Divide and conquer

(d)

Optimal binary search tree

(iv)

Backtracking

Question

Question

This question was previously asked in

NIELIT Scientific Assistant IT 5 Dec 2021 Official Paper

Answer 1

The correct answer is Option 1.

Key Points

Merge Sort uses the Divide and Conquer strategy. It divides the array into halves, recursively sorts them, and then merges the sorted halves.
8 Queens Problem is solved using Backtracking, which explores possible positions and backtracks upon invalid placements.
Single Source Shortest Path (like Dijkstra’s algorithm) follows the Greedy Approach by selecting the shortest unvisited path at each step.
Optimal Binary Search Tree uses Dynamic Programming to compute minimum expected search costs by evaluating all combinations of subtrees.

Additional Information

Divide and Conquer: Breaks the problem into smaller sub-problems, solves them recursively, and combines their results. (Merge Sort)
Backtracking: Systematically tries all possibilities and abandons paths that fail. (8 Queens)
Greedy Approach: Makes optimal choices at each step to find global optimum. (Dijkstra’s algorithm)
Dynamic Programming: Solves overlapping subproblems and builds solutions bottom-up. (Optimal BST)