ExamSIDE.Com

# GATE CSE 1998 Question

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?
A
Dynamic programming
B
Backtracking
C
Greedy
D
Divide and Conquer

# GATE CSE 2004 Question

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of
A
n
B
n2
C
n log n
D
$n \log^2n$

# GATE CSE 2011 Question

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 Li, denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize Ln−1=1.

For all i such that $0 \leq i \leq n-2$

$L_i = \begin{cases} 1+ L_{i+1} & \quad\text{if A[i] < A[i+1]} \\ 1 & \quad\text{Otherwise}\end{cases}$

Finally, the length of the longest monotonically increasing sequence is max(L0, L1,…,Ln−1)
Which of the following statements is TRUE?
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

# GATE CSE 2015 Set 1 Question

Match the following:

List 1

(P) Prim’s algorithm for minimum spanning tree
(Q) Floyd-Warshall algorithm for all pairs shortest paths
(R) Mergesort
(S) Hamiltonian circuit

List 2

(i) Backtracking
(ii) Greedy method
(iii) Dynamic programming
(iv) Divide and conquer
A
P - iii, Q - ii, R - iv, S - i
B
P - i, Q - ii, R - iv, S - iii
C
P - ii, Q - iii, R - iv, S - i
D
P - ii, Q - i, R - iii, S - iv