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:

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.

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?

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

(a) Use the patterns given to prove that

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

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.

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.

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; 

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

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?

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