A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below:

If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum . Determine the maximum of S(i,j), where 0 ≤ i ≤ j < 14. (Divide and conquer approach may be used)

An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _____.

There are n unsorted arrays: A₁, A₂, …, A_n. Assume that n is odd. Each of A₁, A₂, …, A_n contains n distinct elements. There are no common elements between any two arrays. The worst-case time complexity of computing the median of the medians of A₁, A₂, …, A_n is

Consider the following undirected graph G:

Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value of x is _________.

Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by V_opt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by V_greedy.

The value of V_opt − V_greedy is ______ .

Consider the following functions from positives integers to real numbers

The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

Consider the following table

Match the algorithm to design paradigms they are based on:

Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The problem is to find the smallest index i such that A[i] is 1 by probing the minimum number of locations in A. The worst case number of probes performed by an optimal algorithm is _________.

Match the algorithms with their time complexities:

      Algorithm                                     Time complexity
(P) Towers of Hanoi with n disks                       (i) Θ(n2)
(Q) Binary search given n stored numbers              (ii) Θ(n log⁡ n)
(R) Heap sort given n numbers at the worst case      (iii) Θ(2n)
(S) Addition of two n×n matrices                      (iv) Θ(log⁡ n)

Consider the recurrence function

Then T(n) in terms of Θ notation is

Consider the following C function.

int fun (int n)   {
         int i, j;
         for (i = 1; i <= n; i++)   {
                for (j = 1; j < n; j += i)   {
                        printf("%d %d",i,j);
                }
          }
}

Time complexity of fun in terms of Θ notation is

The worst case running times of Insertion sort, Merge sort and Quick sort, respectively, are:

Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. The maximum possible weight that a minimum weight spanning tree of G can have is __________.

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Let A₁, A₂, A₃ and A₄ be four matrices of dimensions 10 × 5, 5 × 20, 20 × 10, and 10 × 5, respectively. The minimum number of scalar multiplications required to find the product A₁A₂A₃A₄ using the basic matrix multiplication method is _________.

The given diagram shows the flowchart for a recursive function A(n). Assume that all statements, except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this function is O(n^α), then the least possible value (accurate upto two decimal  positions) of α is _________.

Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(≥ 2) numbers? In the recurrence equations given in the options below, c is a constant.

Match the following:

(P) Prim's algorithm for minimum spanning tree               (i) Backtracking
(Q) Floyd-Warshall algorithm for all pairs shortest paths   (ii) Greedy method
(R) Mergesort                                              (iii) Dynamic programming
(S) Hamiltonian circuit                                     (iv) Divide and conquer

An algorithm performs (log N)^1/2 find operations, N insert operations, (log N)^1/2 delete operations, and (log N)^1/2 decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________.

Given below are some algorithms, and some algorithm design paradigms

A. Dijkstra’s Shortest Path                     1. Divide and Conquer
B. Floyd-Warshall algorithm to                  2. Dynamic Programming                 
   compute all pairs shortest path
C. Binary search on a sorted array              3. Greedy design
D. Backtracking search on a graph               4. Depth-first search
                                                5. Breadth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow Codes:

Suppose you are provided with the following function declaration in the C programming language.

       int partition (int a[], int n); 

The function treats the first element of a[] as a pivot, and rearranges the array so that all elements less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left part. The return value is the number of elements in the left part. The following partially given function in the C programming language is used to find the kth smallest element in an array a[ ] of size n using the partition function. We assume k ≤ n

int kth_smallest (int a[], int n, int k)
{
   int left_end = partition (a, n);
   if (left_end+1==k)
   {
       return a [left_end];
   }
   if (left_end+1 > k)
   {
      return kth_smallest (____________________);
   }
   else
   {
      return kth_smallest (____________________);
    }
}

The missing argument lists are respectively

Consider a typical disk that rotates at 15000 rotations per minute (RPM) and has a transfer rate of 50×106 bytes/sec. If the average seek time of the disk is twice the average rotational delay and the controller’s transfer time is 10 times the disk transfer time, the average time (in milliseconds) to read or write a 512-byte sector of the disk is _____________.  

Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?  

Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a minimum spanning tree becomes __________.

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______.

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is __________.

Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1?

     T(n) = 2T(n/2) + Logn  

Consider two strings A = “qpqrr” and B = “pqprqrp”. Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x+10y = _________.

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time.  The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ______.

The number of distinct minimum spanning trees for the weighted graph below is _______.

Consider the following rooted tree with the vertex labeled P as t he root:

The order in which the nodes are visited during in-order traversal is

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

Suppose we have a balanced binary search tree T holding n numbers.  We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n^alog^bn + m^clog^dn), the value of a + 10b + 100c + 1000d is ____.

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

Consider the pseudocode given below. The function DoSomething() takes as argument a pointer to the root of an arbitrary tree represented by the leftMostChild-rightSibling representation. Each node of the tree is of type treeNode.

typedef struct treeNode* treeptr;
struct treeNode
{
    treeptr leftMostChild, rightSibling;
};
int DoSomething (treeptr tree)
{
    int value=0;
    if (tree != NULL)
    {
        if (tree->leftMostChild == NULL)
            value = 1;
        else
            value = DoSomething(tree->leftMostChild);
        value = value + DoSomething(tree->rightSibling);
    }
    return(value);
}

When the pointer to the root of a tree is passed as the argument to DoSomething, the value returned by the function corresponds to the

Consider the C function given below. Assume that the array listA contains n (> 0) elements, sorted in ascending order.

int ProcessArray(int *listA, int x, int n)
{
    int i, j, k;
    i = 0;
    j = n-1;
    do
    {
        k = (i+j)/2;
        if (x <= listA[k])
            j = k-1;
        if (listA[k] <= x)
            i = k+1;
    }
    while (i <= j);
    if (listA[k] == x)
        return(k);
    else
        return -1;
}

Which one of the following statements about the function ProcessArray is CORRECT?

Which one of the following is the tightest upper bound that represents the number of swaps required to sort n numbers using selection sort?

Which one of the following is the tightest upper bound that represents the time complexity of inserting an object into a binary search tree of n nodes?

Consider the languages L₁ = ϕ and L₂ = {a}. Which one of the following represents L₁L₂* ∪ L₁*?

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n vertices?

Consider an undirected random graph of eight vertices. The probability that there is an edge between a pair of vertices is 1/2. What is the expected number of unordered cycles of length three?

Which of the following statements is/are TRUE for undirected graphs?

P: Number of odd degree vertices is even.
Q: Sum of degrees of all vertices is even.