Consider the recursive algorithm given below:

 procedure bubblersort (n);
 var i,j: index; temp : item;
 begin
    for i:=1 to n-1 do
    if A[i] > A [i+1] then
 begin
    temp : A[i];
    A[i]:=A[i+1]; 
    A[i+1]:=temp
    end;
   bubblesort (n-1)
 end 

Let a_n be the number of times the ‘if…then….’ Statement gets executed when the algorithm is run with value n. Set up the recurrence relation by defining a_n in terms of a_n-1. Solve for a_n.

where O(n) stands for order n is:

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

The root directory of a disk should be placed

An independent set in a graph is a subset of vertices such that no two vertices in the subset are connected by an edge. An incomplete scheme for a greedy algorithm to find a maximum independent set in a tree is given below:

                      V: Set of all vertices in the tree;        I:=φ;
    While             V ≠ φdo
    begin
                      select a vertex u; ∈ V such that
                      V:= V – {u};
                      if u is such that
                      then 1:= I ∪ {u}
                      end;
                      output(I); 

(a) Complete the algorithm by specifying the property of vertex u in each case
(b) What is the time complexity of the algorithm.

Consider the following recursive function:

 function fib (1:integer);integer;
 begin
 if (n=0) or (n=1) then fib:=1
 else fib:=fib(n-1) + fib(n-2)
 end; 

The above function is run on a computer with a stack of 64 bytes. Assuming that only return address and parameter and passed on the stack, and that an integer value and an address takes 2 bytes each, estimate the maximum value of n for which the stack will not overflow. Give reasons for your answer.

(a) Use the patterns given to prove that

(b) Use the result obtained in (a) to prove that

An array A contains n integers in locations A[0],A[1], …………… A[n-1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n-1. An incomplete algorithm for doing this in linear time, without using another is given below. Complete the algorithm by filling in the blanks. Assume all variables are suitably declared.

 min:=n;
 i=0;
 while _____do
 begin
     temp:=A[i];
     j:=i;
     while _____do
 begin
     A[j]:=_____;
     j:=(j+K) mod n;
 if j

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?

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

FORTRAN implementation do not permit recursion because

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

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.

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

Merge sort uses

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

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

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

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; 

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?

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  

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,

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

Which of the following is false?

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

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

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)

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?

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 

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

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   

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.

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)