Q. Match List-I with List-II and choose the correct answer from the code given below:

List I (Graph Algorithm) List II (Time Complexity)
(a) Dijkstra’s algorithm (i) O(E lg E)
(b) Kruskal’s algorithm (ii) Θ(V3)
(c) Floyd-Warshall algorithm (iii) O(V2)
(d) Topological sorting (iv) Θ(V+E)

where V and E are the number of vertices and edges in graph respectively.

View solution

Q. In K-coloring of an undirected graph G=(V,E) is a function. c:V→{0,1,…,K−1} such that c(u)≠c(v) for every edge (u,v)∈E.

Which of the following is not correct?

View solution

Q. Consider a singly linked list. What is the worst case time complexity of the best-known algorithm to delete the node a, pointer to this node is q, from the list?

View solution

Q. The second smallest of n elements can be found with ............... comparisons in the worst case.

View solution

Q. Consider the following statements related to AND-OR Search algorithm.

S1: A solution is a subtree that has a goal node at every leaf.
S2: OR nodes are analogous to the branching in a deterministic environment.
S3: AND nodes are analogous to the branching in a non-deterministic environment.

Which of the following is true referencing the above statements?

View solution

Q. The solution of the recurrence relation
T(m) = T(3m/4) + 1 is:

View solution

Q. Consider the array A=<4, 1, 3, 2, 16, 9, 10, 14, 8, 7>. After building heap from the array A, the depth of the heap and the right child of max-heap are .............. and .................. respectively. (Root is at level 0).

View solution

Q. A hash function h defined h(key)=key mod 7, with linear probing, is used to insert the keys 44, 45, 79, 55, 91, 18, 63 into a table indexed from 0 to 6. What will be the location of key 18?

View solution

Q. Which of the following algorithms solves the single-source shortest paths?

View solution

Q. A text is made up of the characters A, B, C, D, E each occurring with the probability 0.08, 0.40, 0.25, 0.15 and 0.12 respectively. The optimal coding technique will have the average length of:

View solution

Q. A binary search tree in which every non-leaf node has non-empty left and right subtrees is called a strictly binary tree. Such a tree with 19 leaves:

View solution

Q. Match the following with respect to algorithm paradigms :

List - I
(a) The 8-Queen’s problem
(b) Single-Source shortest paths
(c) STRASSEN’s Matrix multiplication
(d) Optimal binary search trees

List - II
(i) Dynamic programming
(ii) Divide and conquer
(iii) Greedy approach
(iv) Backtracking

Code:
(a) (b) (c) (d)

View solution

Q. The maximum number of comparisons needed to sort 9 items using radix sort is (assume each item is 5 digit octal number):

View solution

Q. A 5-ary tree is tree in which every internal node has exactly 5 children. The number of left nodes in such a tree with 8 internal nodes will be:

View solution

Q. Consider a Boolean function of ‘n’ variables. The order of an algorithm that determines whether the Boolean function produces a output 1 is:

View solution

Q. Consider an array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array (i< = n), the index of the parent is:

View solution

Q. The following numbers are inserted into an empty binary search tree in the given order:

10, 1, 3, 5, 15, 12, 16.

What is the height of the binary search tree?

View solution

Q. Let G be an undirected connected graph with distinct edge weight. Let Emax be the edge with maximum weight and Emin the edge with minimum weight. Which of the following statements is false?

View solution

Q. A list of n strings, each of length n, is sorted into lexicographic order using merge - sort algorithm. The worst case running time of this computation is:

View solution

Q. Postorder traversal of a given binary search tree T produces following sequence of keys:

3, 5, 7, 9, 4, 17, 16, 20, 18, 15, 14

Which one of the following sequences of keys can be the result of an in-order traversal of the tree T?

View solution