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²)

Consider the following sequence of numbers

  92, 37, 52, 12, 11, 25  

Use bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five passes.

How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).

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

Which of the following is false?

The recurrence relation

 T(1) = 2
 T(n) = 3T(n/4)+n 

has the solution, T(n) equals to

The average number of key comparisons done on a successful sequential search in list of length n is

Quicksort is run on two inputs shown below to sort in ascending order taking first element as pivot,

(i) 1,2,3,...,n
(ii) n,n-1,n-2,...,2,1 

Let C₁ and C₂ be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

A two dimensional array A[1...n][1...n] of integers is partially sorted if

    ∀i, j ∈ [1...n−1],   A[i][j] < A[i][j+1] and 
                           A[i][j] < A[i+1][j] 

Fill in the blanks:
(a) The smallest item in the array is at A[i][j] where i=............and j=..............
(b) The smallest item is deleted. Complete the following O(n) procedure to insert item x (which is guaranteed to be smaller than any item in the last row or column) still keeping A partially sorted.

procedure  insert (x: integer);
var        i,j: integer;
begin
(1) i:=1; j:=1, A[i][j]:=x;
(2) while (x > ...... or x > ......) do
(3) if A[i+1][j] < A[i][j] ......... then begin
(4) A[i][j]:=A[i+1][j]; i:=i+1;
(5) end
(6) else begin
(7) ............
(8) end
(9) A[i][j]:= .............
    end  

Insert the characters of the string K R P C S N Y T J M into a hash table of size 10.
Use the hash function

 h(x) = (ord(x) – ord("a") + 1) mod10 

and linear probing to resolve collisions.
(a) Which insertions cause collisions?
(b) Display the final hash table.

A complete, undirected, weighted graph G is given on the vertex {0, 1,...., n−1} for any fixed ‘n’. Draw the minimum spanning tree of G if
(a) the weight of the edge (u,v) is ∣u − v∣
(b) the weight of the edge (u,v) is u + v

Let G be the directed, weighted graph shown in below figure.

We are interested in the shortest paths from A.
(a) Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the algorithm is started at node A.
(b) Write down sequence of vertices in the shortest path from A to E.
(c) What is the cost of the shortest path from A to E?

Consider the following program that attempts to locate an element x in a sorted array a[] using binary search. Assume N>1. The program is erroneous. Under what conditions does the program fail?

      var          i,j,k: integer; x: integer;
                   a:= array; [1...N] of integer;
      begin	   i:= 1; j:= N;
      repeat	   k:(i+j) div 2;
                   if a[k] < x then i:= k 
                   else j:= k 
      until (a[k] = x) or (i >= j);
      if (a[k] = x) then
      writeln ('x is in the array')
      else
      writeln ('x is not in the array')
      end; 

The correct matching for the following pairs is

(A) All pairs shortest path          (1) Greedy
(B) Quick Sort                       (2) Depth-First search
(C) Minimum weight spanning tree     (3) Dynamic Programming
(D) Connected Components             (4) Divide and and Conquer 

Let T(n) be the function defined by T(1)= 1, T(n)= 2T(⌊n/2⌋) + √n for n≥2. Which of the following statement(s) is true?

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

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a graph?

Give the correct matching for the following pairs:

            A. O(log n)     1. Selection sort
            B. O(n)         2. Insertion sort
            C. O(nlog n)    3. Binary search
            D. O(n2)        4. Merge sort   

(a) Solve the following recurrence relation:

  xn = 2xn-1 - 1, n>1
  x1 = 2 

(b) Consider the grammar

  S →  Aa | b
  A → Ac | Sd | ε 

Construct an equivalent grammar with no left recursion and with minimum number of production rules.

A sorting technique is called stable if

Suppose  we  want  to  arrange  the  n  numbers  stored  in any  array  such  that  all negative  values  occur  before  all  positive  ones. Minimum  number  of  exchanges required in the worst case is

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:

   20, 47, 15, 8, 9, 4, 40, 30, 12, 17 

then the order of these elements after second pass of the algorithm is:

If n is a power of 2, then the minimum number of multiplications needed to compute a* is

The minimum number of record movements required to merge five files A (with 10 records), B (with 20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:

If T₁ = O(1), give the correct matching for the following pairs:

   (M) Tn = Tn−1 + n          (U) Tn = O(n)
   (N) Tn = Tn/2 + n          (V) Tn = O(nlogn)
   (O) Tn = Tn/2 + nlogn      (W) T = O(n2)
   (P) Tn = Tn−1 + logn       (X) Tn = O(log2n) 

Let A be an n×n matrix such that the elements in each row and each column are arranged in ascending order. Draw a decision tree which finds 1^st, 2^nd and 3^rd smallest elements in minimum number of comparisons.

(a) Consider the following algorithm. Assume procedure A and procedure B take O(1) and O(1/n) unit of time respectively. Derive the time complexity of the algorithm in O-notation.

         algorithm what (n)      
             begin 
                  if n = 1 then call A 
             else begin
                   what (n-1);
                   call B(n)
             end
         end. 

(b) Write a constant time algorithm to insert a node with data D just before the node with address p of a singly linked list.

Let s be a sorted array of n integers. Let t(n) denote the time taken for the most efficient algorithm to determined if there are two elements with sum less than 1000 in s. Which of the following statements is true?

Consider the following functions

Which of the following is true?

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

A recursive program to compute Fibonacci numbers is shown below. Assume you are also given an array f[0…..m] with all elements initialized to 0.

 fib(n) {
        if (n > M) error ();
        if (n == 0) return 1;
        if (n == 1) return 1;
        if (▭) _________________(1)
        return ▭ ____________(2)
        t = fib(n – 1) + fib (n – 2);
        ▭__________(3)
        return t;
 } 

(a) Fill in the boxes with expressions/statements to make fib() store and reuse computed Fibonacci values. Write the box number and the corresponding contents in your answer book.
(b) What is the time complexity of the resulting program when computing fib(n)?

An array contains four occurrences of 0, five occurrences of 1, and three occurrences of 2 in any order. The array is to be sorted using swap operations (elements that are swapped need to be adjacent).
(a) What is the minimum number of swaps needed to sort such an array in the worst case?
(b) Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the array is maximum.

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quicksort?

Let f(n) = n²logn and g(n) = n(logn)¹⁰ be two positive functions of n. Which of the following statements is correct?

Consider a weighted undirected graph with vertex set V = {n1,n2,n3,n4,n5,n6} and edge set

 E = {(n1,n2,2),(n1,n3,8),(n1,n6,3),(n2,n4,4),(n2,n5,12),(n3,n4,7),(n4,n5,9), 
     (n4,n6,4)}. The third value in each tuple represents the weight of the edge 
     specified in the tuple. 

(a) List the edges of a minimum spanning tree of the graph.
(b) How many distinct minimum spanning trees does this graph have?
(c) Is the minimum among the edge weights of a minimum spanning tree unique overall possible minimum spanning trees of a graph?
(d) Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum spanning trees of a graph?

The solution to the recurrence equation T(2^k) = 3 T(2^k-1) + 1, T(1)=1, is:

Consider the following algorithm for searching for a given number x in an unsorted array A[1...n] having n distinct values:

        1. Choose an i uniformly at random from 1...n;
        2. If A[i]=x then Stop else Goto 1; 

Assuming that x is present in A, what is the expected number of comparisons made by the algorithm before it terminates?

The running time of the following algorithm

  Procedure A(n)
  If n <= 2 return(1) else return (A(⌈√n⌉)); 

is best described by:

Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph G with n*n adjacency matrix A. A[i,j]equals if there is an edge in G from i to j, and 0 otherwise. Your aim in filling in the blanks is to ensure that the algorithm is correct.

 INITIALIZATION: For i = 1 … n
                      {For j = 1 … n
                          { if A[i,j]=0 then P[i,j] = _______ else P[i,j] =____;}
 ALGORITHM: For i = 1 …n
           { For j = 1 …n
                    {For k = 1 …n
                         {P[__,___]=min{_______,_______};}
                    }
           } 

(a) Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
(b) Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
(c) Fill in the blank: The running time of the Algorithm is O(____).

Consider the following C function.

float f(float x, int y)
{
  float p, s; int i;
  for (s=1, p=1, i=1; i < y; i ++)
  {
    p*= x/i;
    s+=p;
  }
  return s;
}  

For large values of y, the return value of the function f best approximates