Given below are some algorithms, and some algorithm design paradigms.

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.

Question

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

Examsnet · Accepted Answer

Correct Answer is : 1 – iii, 2 – ii, 3 – i, 4 – iv.

GATE Computer Science (CS) 2015 Shift 2 Solved Paper