GATE CSE 2016 Set 2 | Dynamic Programming Question 5 | Algorithms

GATE CSE 2016 Set 2

MCQ (Single Correct Answer)

-0.3

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Greedy paradigm.

Divide-and-Conquer paradigm.

Dynamic Programming paradigm.

neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

GATE CSE 2015 Set 1

MCQ (Single Correct Answer)

-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

P - iii, Q - ii, R - iv, S - i

P - i, Q - ii, R - iv, S - iii

P - ii, Q - iii, R - iv, S - i

P - ii, Q - i, R - iii, S - iv

GATE CSE 2011

MCQ (Single Correct Answer)

-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 L_i, denote the length of the longest monotonically increasing sequence starting at index i in the array. Initialize L_n−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(L₀, L₁,…,L_n−1)
Which of the following statements is TRUE?

The algorithm uses dynamic programming paradigm

The algorithm has a linear complexity and uses branch and bound paradigm

The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm

The algorithm uses divide and conquer paradigm

GATE CSE 2004

MCQ (Single Correct Answer)

-0.3

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is of the order of

n²

n log n

$$n \log^2n$$