1
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. GATE CSE 2011 Algorithms - Greedy Method Question 16 English What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
A
$${1 \over {12}}(11{n^2} - 5n)$$
B
$${n^2}{\rm{ - }}\,n + 1$$
C
6n – 11
D
2n + 1
2
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
An undirected graph G(V, E) contains n ( n > 2 ) nodes named v1 , v2 ,….vn. Two nodes vi , vj are connected if and only if 0 < |i – j| <= 2. Each edge (vi, vj ) is assigned a weight i + j. A sample graph with n = 4 is shown below. GATE CSE 2011 Algorithms - Greedy Method Question 15 English The length of the path from v5 to v6 in the MST of previous question with n = 10 is
A
11
B
25
C
31
D
41
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 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?
A
The algorithm uses dynamic programming paradigm
B
The algorithm has a linear complexity and uses branch and bound paradigm
C
The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
D
The algorithm uses divide and conquer paradigm
4
GATE CSE 2011
MCQ (Single Correct Answer)
+2
-0.6
Four matrices M1, M2, M3 and M4 of dimensions p $$\times$$ q, q $$\times$$ r, r $$\times$$ s and s $$\times$$ t respectively can be multiplied is several ways with different number of total scalar multiplications. For example, when multiplied as ((M1 $$\times$$ M2) $$\times$$ (M3 $$\times$$ M4)), the total number of multiplications is pqr + rst + prt. When multiplied as (((M1 $$\times$$ M2) $$\times$$ M3) $$\times$$ M4), the total number of scalar multiplications is pqr + prs + pst.

If p = 10, q = 100, r = 20, s = 5 and t = 80, then the number of scalar multiplications needed is:
A
248000
B
44000
C
19000
D
25000
EXAM MAP
Medical
NEET
Graduate Aptitude Test in Engineering
GATE CSEGATE ECEGATE EEGATE MEGATE CEGATE PIGATE IN
CBSE
Class 12