1

GATE CSE 2022

Numerical

+1

-0.33

Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.

$$A[i][j] = \left\{ {\matrix{ {1,} & {1 \le j \le i \le 5} \cr {0,} & {otherwise} \cr } } \right.$$

A[i][j] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r $$\in$$ V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is _____________.

Your input ____

2

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

3

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

4

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?

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