1
GATE CSE 2003
+2
-0.6
Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is sequence of vertices (vi, vi+1, ……., vj) such that (vk, vk+1) ∈ E for all k in i through j – 1. A simple path is a path in which no vertex appears more than once. Let A be an n x n array initialized as follow
$$A[j,k] = \left\{ {\matrix{ {1\,if\,(j,\,k)} \cr {1\,otherwise} \cr } } \right.$$\$ Consider the following algorithm.
for i = 1 to n
for j = 1 to n
for k = 1 to n
A [j , k] = max (A[j, k] (A[j, i] + A [i, k]); 
Which of the following statements is necessarily true for all j and k after terminal of the above algorithm ?
A
$$A\left[ {j,{\rm{ }}k} \right]{\rm{ }} \le {\rm{ }}n$$
B
If $${\rm{A[j, k] = n }} - 1$$, then G has a Hamiltonian cycle
C
If there exists a path from j to k, A[j, k] contains the longest path lens from j to k
D
If there exists a path from j to k, every simple path from j to k contain most A[j, k] edges
2
GATE CSE 2003
+1
-0.3
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time reduction from Π to 3-SAT. Which of the following can be inferred from these reductions ?
A
Π is NP-hard but not NP-complete
B
Π is in NP, but is not NP-complete
C
Π is NP-complete
D
Π is neither NP-hard, nor in NP
3
GATE CSE 2003
+2
-0.6
What is the weight of a minimum spanning tree of the following graph?
A
29
B
31
C
38
D
41
4
GATE CSE 2003
+1
-0.3
Which of the following suffices to convert an arbitrary CFG to an LL(1) grammar?
A
Removing left recursion alone
B
Factoring the grammar alone
C
Removing left recursion and factoring the grammar
D
None of the above
GATE CSE Papers
2023
2022
2021
2020
2019
2018
2017
2016
2015
2014
2013
2012
2011
2010
2009
2008
2007
2006
2005
2004
2003
2002
2001
2000
1999
1998
1997
1996
1995
1994
1993
1992
1991
1990
1989
1988
1987
EXAM MAP
Joint Entrance Examination