29-10-2013, 04:47 PM
CS-GATE-2013 PAPER|.pdf (Size: 289.86 KB / Downloads: 24)
Q. No. 1 – 25 Carry One Mark Each
1.
Consider an undirected random graph of eight vertices. The probability that there
is an edge between a pair of vertices is 1⁄2. What is the expected number of
unordered cycles of length three?
(A) 1/8
(B) 1
Ans. P(edge) =
(D) 8
©
Exp:
© 7
1
2
Number of ways we can choose the vertices out of 8 is 8 c 3
(Three edges in each cycle)
3
1
Expected number of unordered cycles of length 3 = 8C 3 × = 7
2
2.
Which of the following statements is/are TRUE for undirected graphs?
P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.
(A) P only (B) Q only
© Both P and Q (D) Neither P nor Q
Ans: ©
Exp: Q: Sum of degrees of all vertices = 2 × (number of edges )
3. Function f is known at the following points:
x 0 0.3 0.6 0.9 1.2 1.5 1.8 2.1 2.4 2.7 3.0
f(x) 0 0.09 0.36 0.81 1.44 2.25 3.24 4.41 5.76 7.29 9.00
The value of
∫
3
0
f ( x ) dx computed using the trapezoidal rule is
(A) 8.983
Ans:
(B) 9.003
© 9.017
(D) 9.045
(D)
3
Exp:
h
f x + f ( x ) + 2 ( f ( x ) + f ( x ) + ... + f ( x ) )
∫ f ( x ) dx = 2
( )
0
10
1
2
9
0
=
0.3
9.00 + 2 (25.65)
= 9.045
2
Which one of the following functions is continuous at x = 3 ?
A)
Exp:
(B ) 4, if x = 3
f (x) =
8 − x if x ≠ 3
(C )
Ans:
x + 3, (D ) f (x) =
2, if x = 3 f (x) =
x − 4
f ( x ) = x − 1, if x > 3
x + 3
, if x < 3
3
if x≤3
if x>3
1
3
x − 27
,
if
x≠3
(A)
lim f ( x ) = lim ( x − 1) = 2 = f (3)
x →3 +
x →3 +
x + 3
lim f ( x ) = lim
= 2 = f (3)
x →3 −
3
∴ f ( x ) is continuous at x = 3
x →3 −
5. Which one of the following expressions does NOT represent exclusive NOR of x
and y?
(A) xy + x ' y '
(B) x ⊕ y '
© x '⊕ y
(D) x '⊕ y '
Ans: (D)
Exp: (A) x
y = xy + x y
(B ) x ⊕ y = xy + x y = xy + x y = x
(C ) x ⊕ y = x y + x y = x y + xy = x
(D )
6.
()
x ⊕ y = (x) y + x y = x ⊕ y
y
y
In a k-way set associative cache, the cache is divided into v sets, each
consists of k lines. The lines of a set are placed in sequence one after
The lines in set s are sequenced before the lines in set (s+1). The main
blocks are numbered 0 onwards. The main memory block numbered j
mapped to any one of the cache lines from
of which
another.
memory
must be
(A) ( j mod v ) * k to ( j mod v ) *k + (k − 1)
(B) ( j mod v ) to ( j mod v ) + (k − 1)
© ( j mod k ) to ( j mod k ) + ( v − 1)
(D) ( j mod k ) * v to ( j mod k ) * v + ( v − 1)
Ans:
Exp:
(B)
Set number in the cache = (main memory block number) MOD number of sets in
the cache.
As the lines in the set are placed in sequence, we can have the lines from 0 to K
– 1 in the set.
Number of sets = v
Main memory block number = j
First line = (j mod v); last line = (j Mod v) + (k – 1)
What is the time complexity of Bellman-Ford single-source shortest path
algorithm on a complete graph of n vertices?
( )
(A) Θ n2
(
(B) Θ n2 logn
)
( )
(
© Θ n3
Ans:
)
©
Exp:
(D) Θ n3 logn
Bellman-ford time complexity: Θ( V × E )
For complete graph:
E =
n(n − 1)
2
V =n
n(n − 1)
∴ Θ n ×
= Θ(n3 )
2
8.
Which of the following statements are TRUE?
(1) The problem of determining whether there exists a cycle in an undirected
graph is in P.
(2) The problem of determining whether there exists a cycle in an undirected
graph is in NP.
(3) If a problem A is NP-Complete, there exists a non-deterministic polynomial
time algorithm to solve A.
(A) 1,2 and 3
Ans:
(B) 1 and 2 only
© 2 and 3 only
(D) 1 and 3 only
(A)
Exp: 1. Cycle detection using DFS: O(V + E) = O(V 2 ) and it is polynomial problem
2. Every P-problem is NP ( sin ce P ⊂ NP )
3. NP − complete ∈ NP
Hence, NP-complete can be solved in non-deterministic polynomial time
9.
Which of the following statements is/are FALSE?
(1) For every non-deterministic Turing machine, there exists an equivalent
deterministic Turing machine.
(2) Turing recognizable languages are closed under union and complementation.
(3) Turing
decidable
complementation
languages
are
closed
under
intersection
and
(4) Turing recognizable languages are closed under union and intersection.
(A) 1 and 4 only
Ans:
© 2 only
(D) 3 only
©
Exp:
(B) 1 and 3 only
(1) NTM ≅ DTM
(2) RELs are closed under union & but not complementation
(3) Turing decidable languages are recursive and recursive languages are closed
under intersection and complementation
(4) RELs are closed under union & intersection but not under complementation