91.  A graph G = (V, E) satisfies E ≤ 3 V  6. The mindegree of G is defined as follows. Therefore, mindegree of G cannot be 
a.  3 
b.  4 
c.  5 
d.  6 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).6

92.  Consider the following system of linear equations Notice that the second and the third columns of the coefficient matrix are linearly dependent. For how many values of a, does this system of equations have infinitely many solutions? 
a.  0 
b.  1 
c.  2 
d.  infinitely many 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).1

93.  A piecewise linear function f(x) is plotted using thick solid lines in the figure below (the plot is drawn to scale). If we use the NewtonRaphson method to find the roots of f(x) = 0 using x0, x1 and x2 respectively as initial guesses, the roots obtained would be 
a.  1.3, 0.6, and 0.6 respectively 
b.  0.6, 0.6, and 1.3 respectively 
c.  1.3, 1.3, and 0.6 respectively 
d.  1.3, 0.6, and 1.3 respectively 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).1.3, 0.6, and 1.3 respectively

94.  Consider two languages L1 and L2 each on the alphabet ∑. Let f : ∑ → ∑ be a polynomial time computable bijection such that (∀ x) [x ∈ L1 iff f(x) ∈ L2]. Further, let f^1 be also polynomial time computable. Which of the following CANNOT be true? 
a.  L1 ∈ P and L2 is finite 
b.  L1 ∈ NP and L2 ∈ P 
c.  L1 is undecidable and L2 is decidable 
d.  L1 is recursively enumerable and L2 is recursive 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).L1 is undecidable and L2 is decidable

95.  In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1.....n ? 
a.  n(n  1)/2 
b.  n(n  1)/4 
c.  n(n + 1)/4 
d.  2n[log2 n] 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).n(n  1)/4

96.  In a permutation a1.....an of n distinct integers, an inversion is a pair (ai, aj) such that i < j and ai > aj. What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1.....n with at most n inversions? 
a.  Θ (n^2) 
b.  Θ (n log n) 
c.  Θ (n^1.5) 
d.  Θ (n) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (d).Θ (n)

97.  The cube root of a natural number n is defined as the largest natural number m such that m^3 ≤ n. The complexity of computing the cube root of n (n is represented in binary notation) is: 
a.  O(n) but not O(n^0.5) 
b.  O(n^0.5) but not O((log n)^k) for any constant k > 0 
c.  O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0 
d.  O((log log n)^m) for some constant k > 0.5, but not O((log log n)^0.5) 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).O((log n)^k) for some constant k > 0, but not O ((log log n)^m) for any constant m > 0

98.  Let G = (V, E) be an undirected graph with a subgraph G1 = (V1, El). Weights are assigned to edges of G as follows : A singlesource shortest path algorithm is executed on the weighted graph (V, E, w) with an arbitrary vertex ν1 of V1 as the source. Which of the following can always be inferred from the path costs computed? 
a.  The number of edges in the shortest paths from ν1 to all vertices of G 
b.  G1 is connected 
c.  V1 forms a clique in G 
d.  G1 is a tree 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).G1 is connected

99.  Consider the following logic program P A(x) < B(x, y), C(y) < B(x,x) Which of the following first order sentences is equivalent to P? 
a.  A 
b.  B 
c.  C 
d.  D 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (c).C

100.  The following resolution rule is used in logic programming: Derive clause (P v Q) from clauses (P v R), (Q v ¬ R) Which of the following statements related to this rule is FALSE? 
a.  ((P v R) ^ (Q v ¬ R)) (P v Q) is logically valid 
b.  (P v Q) ⇒ ((P v R) ^ (Q v ¬ R)) is logically valid 
c.  (P v Q) is satisfiable if and only if (P v R) ^ (Q v ¬ R) is satisfiable 
d.  (P v Q) ⇒ FALSE if and only if both P and Q are unsatisfiable 
View Answer Report Discuss Too Difficult! Search Google 
Answer: (b).(P v Q) ⇒ ((P v R) ^ (Q v ¬ R)) is logically valid
