Suppose the letters a, b, c, d, e, f have probabilities $ \dfrac{1}{2},\dfrac{1}{4},\dfrac{1}{8},\dfrac{1}{16},\dfrac{1}{32},\dfrac{1}{32}$ respectively.

What is the average length of the correct answer to Q.?

The most efficient algorithm for finding the number of connected components in an undirected graph on n vertices and m edges has time complexity

The minimum number of comparisons required to determine if an integer appears more than $\frac{n}{2}$ times in a sorted array of $n$ integers is

A B-tree of order 4 is built from scratch by 10 successive insertions. What is the maximum number of node splitting operations that may take place?

G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?

Dijkstra's single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

Consider the following functions: f(n) = 2ⁿ g(n) = n! h(n) = n^logn Which of the following statements about the asymptotic behaviour of f(n), g(n), and h(n) is true?

The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer W, determine whether there is a subset of S Whose elements sum to W. An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T(n) be the number of comparisons required to sort n elements. Then

You are given the postorder traversal, P, of a binary search tree on the n elements 1, 2,….,n. You have to determine the unique binary search tree that has P as its postorder traversal. What is the time complexity of the most efficient algorithm for doing this?

We have a binary heap on n elements and wish to insert n more elements (not necessarily one after another) into this heap. The total time required for this is

Consider the following C functions:

int f1(int n) {
  If(n == 0 | | n == 1)
  return n;
  else
    return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n) {
  int i;
  int X[N], Y[N], Z[N];
  X[0] = Y[0] = Z[0] = 0;
  X[1] = 1;
  Y[1] = 2;
  Z[1] = 3;
  for (i = 2; i <= n; i++) {
    X[i] = Y[i - 1] + Z[i - 2];
    Y[i] = 2 * X[i];
    Z[i] = 3 * X[i];
  }
  Return X[n];
}

f₁ (8) and f₂ (8) return the values

Consider the following C functions:

int f1(int n) {
  If(n == 0 | | n == 1)
  return n;
  else
    return (2 * f1(n - 1) + 3 * f1(n - 2));
}
int f2(int n) {
  int i;
  int X[N], Y[N], Z[N];
  X[0] = Y[0] = Z[0] = 0;
  X[1] = 1;
  Y[1] = 2;
  Z[1] = 3;
  for (i = 2; i <= n; i++) {
    X[i] = Y[i - 1] + Z[i - 2];
    Y[i] = 2 * X[i];
    Z[i] = 3 * X[i];
  }
  Return X[n];
}

The running time of f1 (n) and f2 (n) are

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁, a₂, a₃, …, a_n}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\le$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a₁, a₂, …, a} whose elements sum to j.

Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W?

Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.

1.         f(int Y[10], int x) {          
2.            int u, j, k;
3.            i = 0; j = 9;
4.           do {
5.               k = (i + j)/2;
6.               if (Y[k] ! = x) && (i < j);
7.            } while ((Y[k] ! = x) && (i 

Consider the following C program that attempts to locate an element x in an array Y[ ] using binary search. The program is erroneous.

1.         f(int Y[10], int x) {          
2.            int u, j, k;
3.            i = 0; j = 9;
4.           do {
5.               k = (i + j)/2;
6.               if (Y[k] ! = x) && (i < j);
7.            } while ((Y[k] ! = x) && (i 

The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a₁, a₂, a₃, …, a_n}, and positive integer W, is there a subset of S whose elements sum to W? A dynamic program for solving this problem uses a 2-dimensional Boolean array, X, with n rows and W+1 columns. X [i, j], 1$\le$i $\ge$ n,0 $\le$j $\le$ W, is TRUE if and only if there is a subset of {a₁, a₂, …, a} whose elements sum to j.

Which of the following is valid for 2 $\le$ i $\le$ n and ai $\le$ j $\le$ W?

What is the number of swaps required to sort n elements using selection sort, in the worst case?

Which of the following statement(s) is / are correct regarding Bellman-Ford shortest path algorithm? P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.

Let $\pi_A$ be a problem that belongs to the class NP. Then which one of the following is TRUE?

In quick-sort, for sorting n elements, the $\left(n/4\right)^{th}$ smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?

The running time of an algorithm is represented by the following recurrence relation:

$T(n) = \begin{cases} n & n \leq 3 \\ T(\frac{n}{3})+cn & \text{ otherwise } \end{cases}$

Which one of the following represents the time complexity of the algorithm?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i, j] = l(i,j). Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(I, j)?

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.

We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y[n] as l(m, n), where an incomplete recursive definition for the function l(i, j) to compute the length of the LCS of X[m] and Y[n] is given below: l (i, j) = 0, if either i=0 or j=0 = expr1, if i,j>0 and X [i-1] = Y [j 1] = expr2, if i,j>0 and X [i-1] = Y [j 1]

Which one of the following options is correct?

Consider the following graph:

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?

The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash table?