1
GATE CSE 2016 Set 2
MCQ (Single Correct Answer)
+1
-0.3
The Floyd-Warshall algorithm for all-pair shortest paths computation is based on
A
Greedy paradigm.
B
Divide-and-Conquer paradigm.
C
Dynamic Programming paradigm.
D
neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
2
GATE CSE 2015 Set 1
MCQ (Single Correct Answer)
+1
-0.3
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
3
GATE CSE 2011
MCQ (Single Correct Answer)
+1
-0.3
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
4
GATE CSE 2004
MCQ (Single Correct Answer)
+1
-0.3
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 Subjects
Software Engineering
Web Technologies
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
Civil Services
UPSC Civil Service
Defence
NDA
CBSE
Class 12