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

Q. The three aspects of Quantization, programmers generally concerned with are:

View solution

Q. The logic of pumping lemma is an example of ....................

View solution

Q. Heap allocation is required for languages that :

View solution

Q. Consider a full binary tree with n internal nodes, internal path length i, and external path length e. The internal path length of a full binary tree is the sum, taken over all nodes of the tree, of the depth of each node. Similarly, the external path length is the sum, taken over all leaves of the tree, of the depth of each leaf.
Which of the following is correct for the full binary tree?

View solution

Q. You are given a sequence of n elements to sort. The input sequence consists of n/k subsequences, each containing k elements. The elements in a given subsequence are all smaller than the elements in the succeeding subsequence and larger than the elements in the preceding subsequence. Thus, all that is needed to sort the whole sequence of length n is to sort the k elements in each of the n/k subsequences.
The lower bound on the number of comparisons needed to solve this variant of the sorting problem is:

View solution

Q. Consider the recurrence relation:

T (n) = 8T(n/2) + Cn, if n > 1
= b, if n =1
Where b and c are constants.

The order of the algorithm corresponding to above recurrence relation is:

View solution