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 G = (V, E) be any connected undirected edge-weighted graph. The weights of the edges in E are positive and distinct. Consider the following statements:

• (I) Minimum Spanning Tree of

• is always unique.

• (II) Shortest path between any two vertices of

is always unique.

Which of the above statements is/are necessarily true?

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

G = (V,E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular edge of G. Which of the following statements about the minimum spanning trees (MSTs) of G is/are TRUE?

• I. If

• is the lightest edge of

• cycle in

• , then every MST of

• II. If

• is the heaviest edge of

•  cycle in

• , then every MST of

Assume that the algorithms considered here sort the input sequences in ascending order. If the input is already in ascending order, which of the following are TRUE?

• I. Quicksort runs in Θ(n

• ) time

• II. Bubblesort runs in Θ(n

• ) time

• III. Mergesort runs in Θ(n) time

IV. Insertion sort runs in Θ(n) time

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.

The line graph L(G) of a simple graph G is defined as follows: · There is exactly one vertex v(e) in L(G) for each edge e in G. · For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e'are incident with the same vertex in G. Which of the following statements is/are TRUE?

(P) The line graph of a cycle is a cycle.
(Q) The line graph of a clique is a clique.
(R) The line graph of a planar graph is planar.
(S) The line graph of a tree is a tree.

The number of elements that can be sorted in Θ(log n) time using heap sort is

What is the return value of f(p,p), if the value of p is initialized to 5 before the call? Note that the first parameter is passed by reference, whereas the second parameter is passed by value.

int f(int &x, int c) {
   c = c - 1;
   if (c==0) return 1;
   x = x + 1;
   return f(x,c) * x;
}

The preorder traversal sequence of a binary search tree is 30, 20, 10, 15, 25, 23, 39, 35, 42. Which one of the following is the postorder traversal sequence of the same tree?

Consider the following operation along with Enqueue and Dequeue operations on queues, where k is a global parameter.

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}

What is the worst case time complexity of a sequence of n MultiDequeue() operations on an initially empty queue?

Assuming P ≠ NP, which of the following is TRUE?

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?

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

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

An algorithm Q solves this problem in O(nW) time. Which of the following statements is false?

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

Merge sort uses

The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:

Which of the following statements is true?

I. As the number of entries in a hash table increases, the number of collisions increases.
II. Recursive programs are efficient
III. The worst case complexity for Quicksort is O(n²)

FORTRAN implementation do not permit recursion because

The recurrence relation that arises in relation with the complexity of binary search is:

Which of the following algorithm design techniques is used in the quicksort algorithm?

In which one of the following cases is it possible to obtain different results for call-by reference and call-by-name parameter passing methods?

Which one of the following statements is false?

Consider the following two functions:

Which of the following is true?

For parameters a and b, both of which are ω(1), T(n) = T(n^1/a)+1, and T(b)=1.

Then T(n) is

Let G = (V,E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G maintained using adjacency lists. Suppose a new weighted edge (u,v) ∈ V×V is added to G. The worst case time complexity of determining if T is still an MST of the resultant graph is

Consider a graph G = (V, E), where V = {v₁, v₂, …, v₁₀₀}, E = {(v_i, v_j) | 1 ≤ i < j ≤ 100}, and weight of the edge (v_i, v_j) is |i - j|. The weight of the minimum spanning tree of G is ______.

The root directory of a disk should be placed

Consider a simple connected graph G with n vertices and n-edges (n>2). Then, which of the following statements are true?

where O(n) stands for order n is:

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are sorted is __________

Following algorithm(s) can be used to sort n integers in the range [1...n³] in O(n) time

Assume that the last element of the set is used as partition element in Quicksort. If n distinct elements from the set [1…..n] are to be sorted, give an input for which Quicksort takes maximum time.

The minimum number of comparisons required to sort 5 elements is _____

The weighted external path length of the binary tree in figure is _____

If the binary tree in figure is traversed in inorder, then the order in which the nodes will be visited is ______

Match the pairs in the following questions by writing the corresponding letters only.

(A) The number distinct binary trees with n nodes       (P) n!/2        
(B) The number of binary strings of length of 2n        (Q) (3n/n)
    with an equal number of 0’s and 1’s                                     
(C) The number of even permutations of n objects        (R) (2n/n) 
(D) The number of binary strings of length 6m which     (S) 1/n+1(2n/n) 
    are palindromes with 2n 0’s.

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with vertices and m edges has the time complexity of:

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: The following sequence of operations is performed on a stack:

 PUSH (10), PUSH (20), POP, PUSH (10), PUSH (20), POP, POP, POP, PUSH (20), POP

Match the pairs in the following questions:

(a) Strassen's matrix multiplication algorithm     (p) Greedy method
(b) Kruskal's minimum spanning tree algorithm      (q) Dynamic programming
(c) Biconnected components algorithm               (r) Divide and Conquer
(d) Floyd's shortest path algorithm                (s) Depth first search

The numbers 1, 2, .... n are inserted in a binary search tree in some order. In the resulting tree, the right subtree of the root contains p nodes. The first number to be inserted in the tree must be

In a depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is

In the following table, the left column contains the names of standard graph algorithms and the right column contains the time complexities of the algorithms. Match each algorithm with its time complexity.

1. Bellman-Ford algorithm       A: O ( m log n)   
2. Kruskal’s algorithm          B: O (n3) 
3. Floyd-Warshall algorithm     C: O (nm)
4. Topological sorting	        D: O (n + m) 

A hash table contains 10 buckets and uses linear probing to resolve collisions. The key values are integers and the hash function used is key % 10. If the values 43, 165, 62, 123, 142 are inserted in the table, in what location would the key value 142 be inserted?

In a binary tree, for every node the difference between the number of nodes in the left and right subtrees is at most 2. If the height of the tree is h > 0, then the minimum number of nodes in the tree is:

Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + √n for n ≥ 2 and T(1) = 1 Which of the following statements is TRUE?

Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there is a minimum weight spanning tree in G containing the edge e. Which of the following statements is always TRUE?

A binary search tree contains the numbers 1, 2, 3, 4, 5, 6, 7, 8. When the tree is traversed in pre-order and the values in each node printed out, the sequence of values obtained is 5, 3, 1, 2, 4, 6, 8, 7. If the tree is traversed in post-order, the sequence obtained would be

Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is

To carry out white box testing of a program, its flow chart representation is obtained as shown in the figure below:

For basis path based testing of this program, its cyclomatic complexity is

An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal node of the complete binary tree starting at the node ⌊(n - 1) /2⌋, and doing this adjustment up to the root node (root node is at index 0) in the order ⌊(n - 1)/2⌋, ⌊(n - 3)/2⌋, ....., 0. The time required to construct a heap in this manner is

Which one of the following binary trees has its inorder and preorder traversals as BCAD  and ABCD, respectively?

Let f(n), g(n) and h(n) be functions defined for positive inter such that f(n) = O(g(n)), g(n) ≠ O(f(n)), g(n) = O(h(n)), and h(n) = O(g(n)). Which one of the following statements is FALSE?

Consider the undirected graph below:

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

RECURSIVE ALGORITHM		  RECURRENCE RELATION
 P. Binary search	      I. T(n) = T(n-k) + T(k) + cn
 Q. Merge sort	             II. T(n) = 2T(n-1) + 1
 R. Quick sort	            III. T(n) = 2T(n/2) + cn
 S. Tower of Hanoi	     IV. T(n) = T(n/2) + 1 

1. Quicksort
2. Heapsort
3. Mergesort

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

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

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 :

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 :

Match the following with respect to algorithm paradigms :

          List-I                        List-II 
(a) The 8-Queens problem               (i) Dynamic programming 
(b) Single-Source shortest paths      (ii) Divide and conquer
(c) STRASSEN’s Matrix multiplication (iii) Greedy approach 
(d) Optimal binary search trees       (iv) Backtracking

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 :

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

E is the number of edges in the graph and f is maximum flow in the graph. When the capacities are integers, the runtime of Ford-Fulkerson algorithm is bounded by :