1
GATE CSE 2021 Set 1
+2
-0.67

Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as:

diam(G) = $$\displaystyle\max_{u, x\in V}$$ {the length of shortest path between u and v}

Let M be the adjacency matrix of G.

Define graph G2 on the same set of vertices with adjacency matrix N, where

$$N_{ij} =\left\{ {\begin{array}{*{20}{c}} {1 \ \ \text{if} \ \ {M_{ij}} > 0 \ \ \text{or} \ \ P_{ij} > 0, \ \text{where} \ \ P = {M^2}}\\ {0, \ \ \ \ \ \text{otherwise}} \end{array}} \right.$$

Which one of the following statements is true?

A
diam(G) < diam(G2) ≤ diam(G)
B
$$\left\lceil {diam(G)/2} \right\rceil$$ < diam(G2) < diam(G)
C
diam(G2) ≤ $$\left\lceil {diam(G)/2} \right\rceil$$
D
diam(G2) = diam(G)
2
GATE CSE 2018
+2
-0.6
Assume that multiplying a matrix $${G_1}$$ of dimension $$p \times q$$ with another matrix $${G_2}$$ of dimension $$q \times r$$ requires $$pqr$$ scalar multiplications. Computing the product of $$n$$ matrices $${G_1}{G_2}{G_{3...}}{G_n}$$ can be done by parenthesizing in different ways. Define $${G_i}\,\,{G_{i + 1}}$$ as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain $${G_1}{G_2}{G_3}{G_4}{G_5}{G_6}$$ using parenthesization $$\left( {{G_1}\left( {{G_2}{G_3}} \right)} \right)\left( {{G_4}\left( {{G_5}{G_6}} \right)} \right),\,\,{G_2}{G_3}$$ and $${G_5}{G_6}$$ are the only explicitly computed pairs.

Consider a matrix multiplication chain $${F_1}{F_2}{F_3}{F_4}{F_5},$$ where matrices $${F_1},{F_2},{F_3},{F_4}$$ and $${F_5}$$ are of dimensions $$2 \times 25,\,\,25 \times 3,\,\,3 \times 16,\,\,16 \times 1$$ and $$1 \times 1000,$$ respectively. In the parenthesization of $${F_1}{F_2}{F_3}{F_4}{F_5}$$ that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

A
$${F_1}{F_2}$$ and $${F_3}{F_4}$$ only
B
$${F_2}{F_3}$$ only
C
$${F_3}{F_4}$$ only
D
$${F_1}{F_2}$$ and $${F_4}{F_5}$$ only
3
GATE CSE 2016 Set 2
Numerical
+2
-0
Let $${A_1},{A_2},{A_3},$$ and $${A_4}$$ be four matrices of dimensions $$10 \times 5,\,\,5 \times 20,\,\,20 \times 10,$$ and $$10 \times 5,\,$$ respectively. The minimum number of scalar multiplications required to find the product $${A_1}{A_2}{A_3}{A_4}$$ using the basic matrix multiplication method is ______________.
4
GATE CSE 2015 Set 2
+2
-0.6
Given below are some algorithms, and some algorithm design paradigms.

GROUP 1 GROUP 2
1. Dijkstra's Shortest Path i. Divide and Conquer
2. Floyd-Warshall algorithm to compute
all pairs shortest path
ii. Dynamic Programming
3. Binary search on a sorted array iii. Greedy design
4. Backtracking search on a graph iv. Depth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow.

A
$$1 - i,\,\,2 - iii,\,\,3 - i,\,\,4 - v.$$
B
$$1 - iii,\,\,2 - iii,\,\,3 - i,\,\,4 - v.$$
C
$$1 - iii,\,\,2 - ii,\,\,3 - i,\,\,4 - iv.$$
D
$$1 - iii,\,\,2 - ii,\,\,3 - i,\,\,4 - v.$$
GATE CSE Subjects
EXAM MAP
Medical
NEET