Q. If S(n,e) represents the maximum additional space taken by DFS for an n-vertex, e-edge graph,  then what is the value of S(n,e), if adjacency lists are used.

View solution

Q. Breaking down a problem into several sub problems is known as…….

View solution

Q. Alpha cutoff and Beta cutoff are combined to get………

View solution

Q. A graph G is bi-connected if and only if ………..

View solution

Q. The common vertex of two bi connected components is called …………

View solution

Q. If two queens are placed at position (i, j) and (k,l). Then they are on the same Diagonal if and only if………

View solution

Q. A node which has been generated and all of whose children have not yet been generated is…….

View solution

Q. In the sum of subsets problem, if n=4, (w1, w2 w3, w4) = (11, 13, 24, 7) and m=31 then solutions are .........
(where 1 represents weight chosen and 0 represents weight is not choosen.)

View solution

Q. Painting all the verticies of a graph with colors such that no two adjacent vertices have the same color is called………of the graph.

View solution

Q. A sufficient condition for a simple graph G with n vertices have a Hamiltonian cycle is that the degree of every vertex in G is atleast……..

View solution

Q. Choose the properties of the asymptotic notation given below:

1) Reflexivity & transpose symmetry
2) Asymmetry& reflexivity
3) Symmetry& transitivity
4) Symmetry& equity

View solution

Q. The searching technique that takes O(1) time to find a data is

View solution

Q. Which of the following sorting algorithms does not have a worst case running time of O(nlog n)?

View solution

Q. An undirected graph G with n vertices and e edges is represented by adjacency list. What is  the time required to generate all the connected components?

View solution

Q. The quick sort algorithm exploits……..design technique.

View solution

Q. The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

View solution

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

View solution

Q. The best case time complexity for a successful binary search is O(1). Similarly the best case time complexity for an unsuccessful binary search is…….

View solution

Q. State the worst case time complexity for quick sort.

View solution

Q. A search technique where we keep expanding nodes with least accumulated cost so far is called

View solution