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
(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
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 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?
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?
Questions Asked from Dynamic Programming (Marks 1)
Number in Brackets after Paper Indicates No. of Questions
GATE CSE Subjects
Discrete Mathematics
Programming Languages
Theory of Computation
Operating Systems
Computer Organization
Database Management System
Data Structures
Computer Networks
Algorithms
Compiler Design
Software Engineering
Web Technologies
General Aptitude