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

2

GATE CSE 2015 Set 1

MCQ (Single Correct Answer)

+1

-0.3

Match the following:

(Q) Floyd-Warshall algorithm for all pairs shortest paths

(R) Mergesort

(S) Hamiltonian circuit

(ii) Greedy method

(iii) Dynamic programming

(iv) Divide and conquer

**List 1**

(Q) Floyd-Warshall algorithm for all pairs shortest paths

(R) Mergesort

(S) Hamiltonian circuit

**List 2**

(ii) Greedy method

(iii) Dynamic programming

(iv) Divide and conquer

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 L

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

Which of the following statements is TRUE?

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

_{0}, L_{1},…,L_{n−1})Which of the following statements is TRUE?

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

Questions Asked from Dynamic Programming (Marks 1)

Number in Brackets after Paper Indicates No. of Questions

GATE CSE Subjects

Theory of Computation

Operating Systems

Algorithms

Database Management System

Data Structures

Computer Networks

Software Engineering

Compiler Design

Web Technologies

General Aptitude

Discrete Mathematics

Programming Languages