41.  Consider an experiment of tossing two fair dice, one black and one red. What is the probability that the number on the black die divides the number on red die ? 
a.  22 / 36 
b.  12 / 36 
c.  14 / 36 
d.  6 / 36 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).14 / 36

42.  In how many ways can 15 indistinguishable fishes be placed into 5 different ponds, so that each pond contains atleast one fish ? 
a.  1001 
b.  3876 
c.  775 
d.  200 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (a).1001

43.  Consider a Hamiltonian Graph (G) with no loops and parallel edges. Which of the following is true with respect to this Graph (G) ?
(a) deg (v) >= n / 2 for each vertex of G (b)  E(G)  >= 1 / 2 (n1) (n2) + 2 edges (c) deg (v) + deg (w) >= n for every v and w not connected by an edge 
a.  (a) and (b) 
b.  (b) and (c) 
c.  (a) and (c) 
d.  (a), (b) and (c) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).(a), (b) and (c)

44.  An allpairs shortestpaths problem is efficiently solved using : 
a.  Dijkstra' algorithm 
b.  BellmanFord algorithm 
c.  Kruskal algorithm 
d.  FloydWarshall algorithm 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).FloydWarshall algorithm

45.  The travelling salesman problem can be solved in : 
a.  Polynomial time using dynamic programming algorithm 
b.  Polynomial time using branchandbound algorithm 
c.  Exponential time using dynamic programming algorithm or branchandbound algorithm 
d.  Polynomial time using backtracking algorithm 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Exponential time using dynamic programming algorithm or branchandbound algorithm

46.  Let f (n) and g(n) be asymptotically nonnegative functions. Which of the following is correct? 
a.  0(f(n)*g(n)) = min(f(n), g(n)) 
b.  0(f(n)*g(n)) = max(f(n), g(n)) 
c.  0(f(n)+g(n)) = min(f(n), g(n)) 
d.  0(f(n)+g(n)) = max(f(n), g(n)) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).0(f(n)+g(n)) = max(f(n), g(n))

47.  Given the following equalities :
E1 : nK+∈ + nK lg n = Ф(nK+∈) for all fixed K and ∈, K ≥ 0 and ∈ > 0. E2 : n32n + 6n23n = O(n32n) Which of the following is true ? 
a.  E1 is correct and E2 is correct 
b.  E1 is correct and E2 is not correct 
c.  E1 is not correct and E2 is correct 
d.  E1 is not correct and E2 is not correct 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).E1 is correct and E2 is not correct

48.  How many different equivalence relations with exactly three different equivalence classes are there on a set with five elements 
a.  10 
b.  15 
c.  25 
d.  30 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).15

49.  Suppose that R1 and R2 are reflexive relations on a set A.
Which of the following statements is correct ? 
a.  R1 ∩R2 is Reflexive and R1 ∪R2 is irreflexive 
b.  R1 ∩R2 is irReflexive and R1 ∪R2 is reflexive 
c.  Both R1 ∩R2 and R1 ∪R2 are reflexive 
d.  Both R1 ∩R2 and R1 ∪R2 are irreflexive 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).Both R1 ∩R2 and R1 ∪R2 are reflexive

50.  There are three cards in a box. Both sides of one card are black, both sides of one card are red, and the third card has one black side and one red side. we pick a card at random and observe only one side. What is the probability that the opposite side is the same colour as the one side we observed ? 
a.  3/4 
b.  2/3 
c.  1/2 
d.  1/3 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).2/3
