Q. The recurrence relation T(n) = m T(n/2) tan2 is satisfied by

View solution

Q. A ___________ complete subgraph and a __________ subset of vertices of a graph G = (V, E) are a clique and a vertex cover respectively.

View solution

Q. A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph?

View solution

Q. Consider a set A {1, 2, 3,……… 1000}. How many members of A shall be divisible by 3 or by 5 or by both 3 and 5?

View solution

Q. A computer program selects an integer in the set {k : 1 < k < 10,00,000} at random and prints out the result. This process is repeated 1 million times. What is the probability that the value k = 1 appears in the printout at least once?

View solution

Q. Which one of the following is used to compute cyclomatic complexity?

View solution

Q. If we define the functions f, g and h that map R into R by :

f(x) = x4, g(x) = √x2 + 1, h(x) = x2 + 72,  then the value of the composite functions ho(gof) and (hog)of are given as

View solution

Q. Dijkstra algorithm, which solves the single-source shortest-paths problem, is a_______________, and the Floyd-Warshall algorithm, which finds shortest paths between all pairs of vertices, is a _____________.

View solution

Q. Equivalent logical expression for the Well Formed Formula (WFF), ~(∀ x)F[x] is

View solution

Q. An A * algorithm is a heuristic search technique which

View solution

Q. The resolvent of the set of clauses (A v B, ~ A v D, C v ~B) is

View solution

Q. How many strings of 5 digits have the property that the sum of their digits is 7 ?

View solution

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

View solution

Q. In how many ways can 15 indistinguishable fishes be placed into 5 different ponds, so that each pond contains atleast one fish ?

View solution

Q. 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 (n-1) (n-2) + 2 edges
(c) deg (v) + deg (w) >= n for every v and w not connected by an edge

View solution

Q. An all-pairs shortest-paths problem is efficiently solved using :

View solution

Q. The travelling salesman problem can be solved in :

View solution

Q. Let f (n) and g(n) be asymptotically non-negative functions. Which of the following is correct?

View solution

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

View solution

Q. How many different equivalence relations with exactly three different equivalence classes are there on a set with five elements

View solution