Algorithms
Question 1 
Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
A  f_{2}, f_{3}, f_{1} 
B  f_{3}, f_{2}, f_{1} 
C  f_{2}, f_{1}, f_{3} 
D  f_{1}, f_{2}, f_{3} 
The asymptotic notation order should be
Constant < logarithmic < linear < polynomial < exponential < factorial
F2 and F3 → Polynomial
F1 → Exponential
By the order of asymptotic notations F1 is definitely larger.
Method1:
Consider n=100
F1 : 100 ^100 ⇒ 1.e+200
F2 : N^log(100) base 2 ⇒ 100 ^ log(100) base 2 ⇒ 100^6.6438561897747 = 1,93,96,00,91,15,564.181300016469223466
F3 : N^Sqrt(n) ====> 100^Sqrt(100) ⇒ 100^10 ⇒ 10,00,00,00,00,00,00,00,00,000
Method2:
We can apply "log" on both sides.
log(F1)=nlog10 (base 2)
log(F2)=(logn)^2 = logn * logn (base 2)
log(F3)=sqrt(n)logn (base 2)
Answer: F2< F3< F1
Question 2 
p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18
Which of the following statements is/are correct about R_{7}?
A  R_{7is achieved by three different solutions.
} 
B  R_{7}=18 
C  R_{7}=19 
D  R_{7}cannot be achieved by a solution consisting of three pieces. 
There are 3 different possible ways to get the maximum amount.
P[6] + P[1] → 17+1 = 18
P[2] + P[2] + P[3] → 5+5+8 = 18
P[7] → 18 = 18
Question 3 
The number of minimumweight spanning trees of the graph is _______
A  3 
To find the number of spanning trees using 2 methods:
 If graph is complete, use n^n2 formula
 If graph is not complete, then use kirchhoff theorem.
Steps in Kirchoff’s Approach:
(i) Make an Adjacency matrix.
(ii) Replace all nondiagonal is by – 1.
(iii) Replace all diagonal zero’s by the degree of the corresponding vertex.
(iv) Cofactors of any element will give the number of spanning trees.
Using the Kirchhoff theorem will take lot of time because the number of vertices are 9.
So, we use brute force technique to solve the problem with the help of Kruskal's algorithm.
Question 4 
Which one of the following options is correct?
A  
B  
C  
D 
Question 5 
Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
A  Quicksort using the last element as pivot 
B  Insertion sort 
C  Selection sort 
D  Mergesort 
Quick sort(with last element as pivot) → will give the worst case time complexity as O(n^2).
Merge Sort → The merge sort will not depend upon the input order and will give O(nlogn) time complexity.
Insertion Sort → Insertion sort will perform best case time complexity when the input array is in sorted order. If the array is already sorted then the inversion count is 0 and If the array is sorted in reverse order that inversion count is the maximum.
Note: Inversion formal definition is two elements A[i] and A[j] form an inversion if A[i] > A[j] and i < j.
The number of comparisons will not take more than “n” for the given input array.
Selection Sort → Selection sort will not depend upon the input order and will give O(n^2) time complexity.
Question 6 
A  
B  
C  
D 
Let assume n=512
Method1:
Using standard recursive algorithm:
MaxMin is a recursive algorithm that finds the maximum and minimum of the set of elements {a(i), a(i+1), ..., a(j)}. The situation of set sizes one (i=j) and two (i=j1) are handled separately. For sets containing more than two elements, the midpoint is determined ( just as in binary search) and two new subproblems are generated. When the maxima and minima of these subproblems are determined, the two maxima are compared and the two minima are compared to achieve the solution for the entire set.
To find the number of element comparisons needed for Maxmin, T(n) represents this number, then the resulting recurrence relation is
When n is a power of two, n = 2^{k} for some positive integer k, then
T(n)=2T(n/2)+2
=2(2T(n/4)+2)+2
=4T(n/4)+4+2
፧
=2k1T(2)+1ik12i
=2k1+2k2
=3n/22
→ The given example n=512
Apply into 3n/2 2
= (3*512)/2 2
= 7682
= 766
Method2:
Find the minimum and maximum independently, using n1 comparisons for each, for a total of 2n2 comparisons. In fact, at most 3⌊n/2⌋ comparisons are sufficient to find both the minimum and the maximum. The strategy is to maintain the minimum and maximum elements seen thus far. Rather than processing each element of the input by comparing it against the current minimum and maximum, at a cost of 2 comparisons per element, we process elements in pairs. We compare pairs of elements from the input first with each other, and then we compare the smaller to the current minimum and the larger to the current maximum, at a cost of 3 comparisons for every 2 elements.
Setting up initial values for the current minimum and maximum depends on whether n is odd or even. If n is odd, we set both the minimum and maximum to the value of the first element,and then we process the rest of the elements in pairs. If n is even, we perform 1 comparison on the first 2 elements to determine the initial values of the minimum and maximum, and then process the rest of the elements in pairs as in the case for odd n.
Let us analyze the total number of comparisons. If n is odd, then we perform 3⌊n/2⌋ comparisons. If n is even, we perform 1 initial comparison followed by 3(n2)/2 comparisons, for a total of (3n/2)2. Thus, in either case, the total number of comparisons is at most 3⌊n/2⌋.
Given an even number of elements. So, 3n/2 2 comparisons.
= (3*512)/2 2
= 7682
= 766
Method3:
By using Tournament Method:
Step1: To find the minimum element in the array will take n1 comparisons.
We are given 512 elements. So, to find the minimum element in the array will take 5121= 511
Step2: To find the largest element in the array using the tournament method.
 After the first round of Tournament , there will be exactly n/2 numbers =256 that will lose the round.
 The biggest loser (the largest number) should be among these 256 loosers.To find the largest number will take (n/2)−1 comparisons =2561 = 255
Total 511+255= 766
Question 7 
Merge sort uses
A  Divide and conquer strategy 
B  Backtracking approach 
C  Heuristic search 
D  Greedy approach 
Question 8 
The postfix expression for the infix expression
A + B*(C + D)/F + D*E is:
A  AB + CD + *F/D + E* 
B  ABCD + *F/DE*++ 
C  A *B + CD/F *DE++ 
D  A + *BCD/F* DE++ 
E  None of the above 
A B C D + * F / + D E * +
Question 9 
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^{2})
A  I and II 
B  II and III 
C  I and IV 
D  I and III 
Recursive program requires stack for storing the function state. Any recursive program can be rewritten as an iterative one. Advantage of recursion is "less programming effort", while it always lags behind iterative one in terms of performance.
Question 10 
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.
A  Theory Explanation. 
Question 11 
How many minimum spanning trees does the following graph have? Draw them. (Weights are assigned to the edge).
A  Theory Explanation. 
Question 12 
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
A  θ(log_{a} log_{b} n) 
B  θ(log_{b} log_{a} n)

C  θ(log_{2} log_{2} n)

D  θ(log_{ab} n)

T(n) = [T(n^{1/a2})+1] + 1
= [T(n^{1/a3})+1] + 2
= [T(n^{1/a3})] + 3
= [T(n^{1/ak})] + b
= log_{b} n = a^{k}
= log log_{b} n = k log a
= k= log_{a} log_{b} n
T(n)=1+log_{a} log_{b} n
T(n)=O(log_{a} log_{b} n)
Question 13 
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
A  θ(E+V) 
B  θ(E logV) 
C  θ(EV) 
D  θ(V) 
• As T is a minimum spanning tree and we need to add a new edge to existing spanning tree.
• Later we need to check still T is a minimum spanning tree or not, So we need to check all vertices whether there is any cycle present after adding a new edge.
• All vertices need to traverse to confirm minimum spanning tree after adding new edge then time complexity is O(V).
Method2:
Time Complexity:
Total vertices: V, Total Edges : E
• O(logV) – to extract each vertex from the queue. So for V vertices – O(VlogV)
• O(logV) – each time a new pair object with a new key value of a vertex and will be done at most once for each edge. So for total E edge – O(ElogV)
• So overall complexity: O(VlogV) + O(ElogV) = O((E+V)logV) = O(ElogV)
Note: Method1 is the most appropriate answer for giving a question.
Question 14 
Consider a graph G = (V, E), where V = {v_{1}, v_{2}, …, v_{100}}, 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 ______.
A  99 
• N =100
• Edge weight is ij for Edge (vi,vj) {1<=i<=100}
• The weight of edge(v1,v2) is 1 , edge(v5,v6) is 1.
• So, 99 edges of weight is 99.
Question 15 
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
A  Theory Explanation. 
Question 16 
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  Theory Explanation. 
Question 17 
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
A  Theory Explanation. 
Question 18 
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  Theory Explanation. 
Question 19 
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;
A  Theory Explanation. 
Question 20 
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
A  (a)  (r), (b)  (p), (c)  (s), (d)  (q) 
Kruskal's minimum spanning tree algorithm  Greedy method
Biconnected components algorithm  Depth first search
Floyd's shortest path algorithm  Dynamic programming
Question 21 
(a) Solve the following recurrence relation:
x_{n} = 2x_{n1}  1, n>1 x_{1} = 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  Theory Explanation. 
Question 22 
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  Theory Explanation. 
Question 23 
(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 Onotation.
algorithm what (n) begin if n = 1 then call A else begin what (n1); 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.
A  Theory Explanation. 
Question 24 
FORTRAN implementation do not permit recursion because
A  they use static allocation for variables 
B  they use dynamic allocation for variables 
C  stacks are not available on all machines 
D  it is not possible to implement recursion on all machines 
→ Recursion requires dynamic allocation of data.
Question 25 
The recurrence relation that arises in relation with the complexity of binary search is:
A  T(n) = T(n/2) + k, k a constant 
B  T(n) = 2T(n/2) + k, k a constant 
C  T(n) = T(n/2) + log n 
D  T(n) = T(n/2) + n 
∴ T(n) = 2T(n/2) + k, k a constant
Question 26 
Which of the following algorithm design techniques is used in the quicksort algorithm?
A  Dynamic programming 
B  Backtracking 
C  Divide and conquer 
D  Greedy method 
Question 27 
In which one of the following cases is it possible to obtain different results for callby reference and callbyname parameter passing methods?
A  Passing a constant value as a parameter 
B  Passing the address of an array as a parameter 
C  Passing an array element as a parameter 
D  Passing an array following statements is true 
{ ........
a[ ] = {1, 2, 3, 4}
i = 0
fun(a[i]);
print a[0];
}
fun(int x)
{
int i = 1;
x = 8;
}
O/p:
Callbyreference = 8
Callbyvalue = 1
Question 28 
Which one of the following statements is false?
A  Optimal binary search tree construction can be performed efficiently using dynamic programming. 
B  Breadthfirst search cannot be used to find connected components of a graph. 
C  Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed. 
D  Depthfirst search can be used to find connected components of a graph. 
Question 29 
Consider the following two functions:
Which of the following is true?
A  g_{1}(n) is O(g_{2}(n)) 
B  g_{1} (n) is O(^{3}) 
C  g_{2} (n) is O(g_{1} (n)) 
D  g_{2} (n) is O(n) 
E  Both A and B 
Growth rate of g_{1} is less than that of g_{2} i.e., g_{1}(n) = O(g_{2}(n)) = O(n).
Question 30 
An array A contains n integers in locations A[0],A[1], …………… A[n1]. It is required to shift the elements of the array cyclically to the left by K places, where 1≤K≤n1. 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  Theory Explanation. 
Question 31 
(a) Use the patterns given to prove that
(You are not permitted to employ induction)
(b) Use the result obtained in (a) to prove that
A  Theory Explanation. 
Question 32 
Consider the following recursive function:
function fib (1:integer);integer; begin if (n=0) or (n=1) then fib:=1 else fib:=fib(n1) + fib(n2) 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  Theory Explanation. 
Question 33 
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.
A  Theory Explanation. 
Question 34 
The root directory of a disk should be placed
A  at a fixed address in main memory 
B  at a fixed location on the disk 
C  anywhere on the disk 
D  at a fixed location on the system disk 
E  anywhere on the system disk 
Question 35 
Consider a simple connected graph G with n vertices and nedges (n>2). Then, which of the following statements are true?
A  G has no cycles. 
B  The graph obtained by removing any edge from G is not connected. 
C  G has at least one cycle. 
D  The graph obtained by removing any two edges from G is not connected. 
E  Both C and D. 
For example let us consider, n=3.
Question 36 
where O(n) stands for order n is:
A  O(n) 
B  O(n^{2}) 
C  O(n^{3}) 
D  O(3n^{2}) 
E  O(1.5n^{2}) 
F  B, C, D and E 
⇒ In this 'n' is constant. So, n is added to n times itself which is O(n^{2}).
Hence, (a) is wrong. And rest (B), (C), (D), (E) are correct.
Question 37 
Consider the recursive algorithm given below:
procedure bubblersort (n); var i,j: index; temp : item; begin for i:=1 to n1 do if A[i] > A [i+1] then begin temp : A[i]; A[i]:=A[i+1]; A[i+1]:=temp end; bubblesort (n1) 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_{n1}. Solve for a_{n}.
A  Theory Explanation. 
Question 38 
A  
B  
C  
D 
In this question they given three main constraints
 The input array is in sorted order
 Use recursive binary search
 Worst case number of operations
If the array is in sorted order then the worst case time complexity is O(logn)
Ex: 10, 20, 30
The binary search approach is using either recursive or iterative method is
Step1: element = middle, the element is found and return the index.
Step2: element > middle, search for the element in the subarray starting from middle+1 index to n.
Step3: element < middle, search for element in the subarray starting from 0 index to middle 1.
Note: The worst case happens when we want to find the smallest/largest farthest node. So, it will not take more than O(logn) time.
Question 39 
Which one of the following options is correct about the recurrence T(n)?
A  
B  
C  
D 
Question 40 
S_{1}: There exists a minimum weighted edge in G which is present in every minimum spanning tree of G.
S_{2}:If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which of the following options is correct?
A  S_{1}is false and S_{2}is true.

B  S_{1}is true and S_{2}is false. 
C  Both S_{1} and S_{2}are false. 
D  Both S_{1} and S_{2}are true. 
Statement1: FALSE: The given statement is not valid for all the cases because they are not mentioned, edge weights are in distinct or duplicate. So, we can take any random edge weights for the given statement.
Example:
Statement2: TRUE: Using the kruskal’s (or) prim's algorithm we get a unique MST when there is a unique edge weight.
Example:
Based on the above graph, we get the MST is
Question 41 
The sum of the qualityscores of all the vertices in the graph shown above is _________.
A  929 
Question 42 
A  
B  
C  
D 
The heap is nothing but a complete binary tree and uses linear search to find the elements.
In min heap, the parent key is less than or equal to (≤) the child keys. The maximum values should present in the farthest leaf node for the worst case time complexity.
To traverse all the elements in a heap will take O(n) time for the worst case because it uses the linear search to find the element.
Question 43 
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
A  O(log n) 
B  O(n) 
C  O(n log log n) 
D  O(n log n) 
And we know that time complexity for building the heap is O(n).
Question 44 
Which one of the following binary trees has its inorder and preorder traversals as BCAD and ABCD, respectively?
A  
B  
C  
D 
Left root right.
Preorder traversal is,
Root left right.
Question 45 
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?
A  f(n) + g(n) = O(h(n)) + h(n)) 
B  f(n) = O(h(n)) 
C  fh(n) ≠ O(f(n)) 
D  f(n)h(n) ≠ O(g(n)h(n)) 
So, f(n)g(n) = O(g(n)h(n)) is True.
Hence, (D) is false.
Question 46 
Consider the undirected graph below:
Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?
A  (E, G), (C, F), (F, G), (A, D), (A, B), (A, C) 
B  (A, D), (A, B), (A, C), (C, F), (G, E), (F, G) 
C  (A, B), (A, D), (D, F), (F, G), (G, E), (F, C) 
D  (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)

(C) produces connected component every instead a new edge is added but when first vertex is chosen (first vertex is chosen randomly) first edge must be minimum weight edge that is chosen. Therefore, (A, D) must be chosen before (A, B). Therefore (C) is false.
Question 47 
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(nk) + T(k) + cn Q. Merge sort II. T(n) = 2T(n1) + 1 R. Quick sort III. T(n) = 2T(n/2) + cn S. Tower of Hanoi IV. T(n) = T(n/2) + 1
A  PII, QIII, RIV, SI 
B  PIV, QIII, RI, SII 
C  PIII, QII, RIV, SI 
D  PIV, QII, RI, SIII 
Binary search  T(n/2) + 1
Merge sort  T(n) = 2T(n/2)+ cn
Tower of hanoi  T(n) = 2T(n1) +1
Question 48 
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
A  p 
B  p + 1 
C  n  p 
D  n  p + 1 
RST contains elements = p
Root contains = 1 element
1^{st} contains = n  (p + 1) element
Root contains the value is n  p.
Question 49 
In a depthfirst traversal of a graph G with n vertices, k edges are marked as tree edges. The number of connected components in G is
A  k 
B  k + 1 
C  n  k  1 
D  n  k 
In this question, we are going to applying the depth first search traversal on each component of graph where G is connected (or) disconnected which gives minimum spanning tree
i.e., k = np
p = n  k
Question 50 
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. BellmanFord algorithm A: O ( m log n) 2. Kruskal’s algorithm B: O (n^{3}) 3. FloydWarshall algorithm C: O (nm) 4. Topological sorting D: O (n + m)
A  1→ C, 2 → A, 3 → B, 4 → D 
B  1→ B, 2 → D, 3 → C, 4 → A 
C  1→ C, 2 → D, 3 → A, 4 → B 
D  1→ B, 2 → A, 3 → C, 4 → D 
Krushkal's algorithm → O(m log n)
FloydWarshall algorithm → O(n^{3})
Topological sorting → O(n+m)