Q. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r. Let d(r,u) and d(r,v) be the lengths of the shortest paths from r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

View solution

Q. How many undirected graphs (not necessarily connected) can be constructed out of a given set V = {v1, v2, ... vn} of n vertices?

View solution

Q. The trapezoidal rule for integration give exact result when the integrand is a polynomial of degree:

View solution

Q. The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have the same colour is

View solution

Q. If X, then Y unless Z" is represented by which of the following formulae in propositional logic? ("¬" is negation "^" is conjunction, and "→" is implication)

View solution

Q. The decimal value 0.25

View solution

Q. Maximum number of edges in a n - node undirected graph without self loops is

View solution

Q. The Newton-Raphson iteration Xn + 1 = (Xn/2) + 3/(2Xn) can be used to solve the equation

View solution

Q. Four fair coins are tossed simultaneously. The probability that at least one head and one tail turn up is :

View solution

Q. A B+ -tree index is to be built on the Name attribute of the relation STUDENT. Assume that all student names are of length 8 bytes, disk block are size 512 bytes, and index pointers are of size 4 bytes. Given this scenario, what would be the best choice of the degree (i.e. the number of pointers per node) of the B+ -tree?

View solution

Q. Let P(E) denote the probability of the event E. Given P(A) = 1, P(B) = 1/2, the values of P(A | B) and P(B | A) respectively are

View solution

Q. Let A be a sequence of 8 distinct integers sorted in ascending order. How many distinct pairs of sequences, B and C are there such that (i) each is sorted in ascending order, (ii) B has 5 and C has 3 elements, and (iii) the result of merging B and C gives A?

View solution

Q. Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number of components in the resultant graph must necessarily lie between

View solution

Q. Let f : A → B be an injective (one-to-one) function.

Define g : 2^A → 2^B as :
g(C) = {f(x) | x ∈ C}, for all subsets C of A.
Define h : 2^B → 2^A as :
h(D) = {x | x ∈ A, f(x) ∈ D}, for all subsets D of B.

Which of the following statements is always true ?

View solution

Q. Consider the set {a, b, c} with binary operators + and × defined as follows :

+ a b c × a b c
a b a c a a b c
b a b c b b c a
c a c b c c c b

For example, a + c = c, c + a = a, c × b = c and b × c = a. Given the following set of equations :

(a × x) + (a × y) = c
(b × x) + (c × y) = c

The number of solution(s) (i.e., pair(s) (x, y)) that satisfy the equations is :

View solution

Q. 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?

View solution

Q. 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 ?

View solution

Q. 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?

View solution

Q. 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:

View solution

Q. 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?

View solution