5 Algorithm

Practice Questions

Q.1 Consider a job scheduling problem with Q.4 Breath First Search (BFS) has been
6 jobs J1 , J 2 , J 3 , J 4 , J 5 and J 6 with implemented using queue data structure.
[MSQ]
corresponding deadlines
T R
(d1 , d2 , d3 , d4 , d5 , d6 ) (6, 4,3,5, 4,3).
Which of the following schedules are
feasible without violating any job P M N
schedule? [MSQ]
(A) J1 , J 2 , J 3 , J 4 , J 5 , J 6
Q S
(B) J 3 , J 6 , J 2 , J 5 , J 4 , J1
Which of the following is/are not
(C) J 6 , J 5 , J 3 , J 2 , J 4 , J1
possible sequence of BFS.
(D) J 6 , J 5 , J 4 , J 3 , J 2 , J1 (A) M, N, P, R, T, Q, S
Q.2 A edTech Company uses a compression (B) N, M, P, Q, S, T, R
technique to encode the message before (C) Q, S, N, M, P, T, R
transmitting over the network. Suppose (D) R, T, Q, P, N, M, S
the message contains the following Q.5 Suppose we run Dijkstra’s single source
string. Message "gate academy" shortest-path algorithm on the following
Each character in input message takes 1 edge weighted directed graph with
byte. If the compression technique used Vertex. P as the source. In what order do
is Huffman coding. The number of bits the nodes get included into the set of
saved in the message is________. vertices to reach ‘U’ Vetex. For which
Q.3 Which of the following pair of the shortest path distances are finalized?
algorithms are Greedy algorithms?
[MSQ]
(A) Prism’s and Kruskal’s
(B) Huffman coding and optimal merge
pattern.
(C) Dijkshtra and Bellman ford
(D) Dijkshtra and floyd warshall.

Algorithm 1
 (A) P, Q, S, T, U The number of largest common length
(B) P, Q, S, U subsequence is ' a ',
(C) P, Q, T, U The number of smallest common two
(D) P, Q, R, V, U length subsequences is ' b '.
Q.6 Consider the above question the shortest Then b  a ____________.
path selected by the Dijkstra algorithm Q.11 What is the time complexity f following
having minimum cost of _____. code
Q.7 Consider the string pqrrrqqpsppeerep gateacademy()
each letter in the string must be assigned {
a binary code. int i = 1, s =1
Satisfying the following properties: while ( s  n)
I. For any two letters, the code
{
assigned to one letter must not be
ij
prefix of the code assigned to the
other letter. s s  i;
II. For any two letter of the same printf (“gate academy”);
frequency, the letter which occurs }
earlier in the dictionary order is }
assigned a code whose length is at Q.12 What is complexity of following
most the length of the code assigned recurrence relation?
to the other letter T (n) nT n  100 n
The minimum length of encoded string
“peers” is ________. (A) T (n log log n)
Q.8 Consider the question 7, which of the (B) T (n log n log n)
following is the binary encoded code for (C) T (n)
“Peers”. [MSQ]
(D) T (n log n)
(A) 11 101 101 01 100
Q.13 Gate Academy contains 500 employees
(B) 11 100 100 101 01 whose monthly salary is stored in the
(C) 00 100 100 11 01 form of array and assume every
(D) 00 0100 10 100 11 employees salary is based on
Q.9 Consider the following two sequences : performance means each employee has
distinct salary. Now Gate Academy
P  M , N , O, N , R, M , N !
wants to find min and max salary
Q  N , R, O, M , N , M ! crediting to employee for which
The length of longest common minimum number of salary
subsequence of P and Q is _____. comparisions needed is ________.
Q.10 Consider the following two sequences. Q.14 A array contains elements which can be
P  M , N , O, N , R, M , N ! changed dynamically (periodic) then
Q  N , R, O, M , N , M ! which of the following algorithm gives

2 Algorithm
 surety that time complexity of sorting The minimum possible sum of weights
array element will never change? of remaining edges (other than MST
(A) Insertion sort (B) Bubble sort edges) is _________.
(C) Merge sort (D) Quick sort B E
1 cos x 1sin x
6
Q.15 Let f (n) n and g (n) n
A 2 15 F
where n is a positive number. Which of
9
the following is/are correct C 10 D
(I) f (n) 0( g (n))
Q.19 A BST contains n elements in the tree if
(II) f (n) : ( g (n)) further n elements are inserted in the
(III) f (n) 0( g (n)) BST then worst case complexity is
(IV) f (n) : ( g (n)) _____
(A) I and II (A) T (n log n) (B) 0(n 2 )
(B) III and IV (C) 0(n) (D) 0(n2 log n)
(C) All are correct
Q.20 Which one of the following is the
(D) All are incorrect recurrence equation for the worst case
Q.16 Consider the equality [MSQ] time complexity of Quick sort algorithm
n2
for sorting n elements. Consider pivoted
X ¦i
i 0
2
 i and the choices for X are,
element is last element of array.
I. 0(n6 ) II. 0(n5 ) §n·
(A) T (n) 2T ¨ ¸  C ˜ n
III. : (n4 ) IV. : (n6 ) ©2¹
(B) T (n) 2T (n  2)  C ˜ n
(A) I (B) II
(C) III (D) IV §n·
(C) T (n) T ¨ ¸  C ˜ n
Q.17 An unordered list contains n distinct ©2¹
elements which is stored in array. The (D) T (n) T (n  1)  C ˜ n
number of minimum comparisions
Q.21 The minimum number of scalar
required to find element in array is not a
multiplication required for
minimax is_________.
parenthesized of a matrix chain product
(A) T (log n) (B) T (n log n) whose sequence of dimensions for four
(C) T (n) (D) T (1) matrices is :
Q.18 The graph shown below 8 edges with  5,7, 4,10,12 !
distinct integer edge weight. The Q.22 For the above given matrix chain
minimum spanning tree (MST) is of multiplication which of the following
weight 42 and contains the edges parenthesis is selected for the minimum
^( A, C),( B, C),(C, D),( D, E),( E, F )`. number of scalar multiplications?
The edge weights of only those edges (A) ( A ( B (CD))) (B) ((( AB )C ) D)
which are in the MST are given in the (C) (( AB ) (CD)) (D) ( A( BC ) D)
figure shown.

Algorithm 3
 Q.23 Let T (n) be the function defined by Q.27 Optimal merge pattern algorithm used
T (1) 1, T (n) 2T («¬n / 2»¼)  n for then minimum number of comparisons
is_____________.
n t2 .
Files a b c d e f
Which of the following statements is
true? Records 30 5 10 8 15 20

(A) T (n) O( n ) (B) T (n) O(n) Q.28 Consider the 15 u15 upper triangular
matrix whose elements are stored in an
(C) T (n) O(log n) (D) None of these
array having starting index ‘0’. The
Q.24 Consider a given array, 8, 3, 4, 6, 7, 2, 1, position of array (7, 9) is _____.
9,5 performed quick sort to sort array by
Q.29 Match the following
considering last element as pivot. Which
of the following will be the correct array A. Prims
after performing pivoting on 5? B. Quick sort
(A) 1, 2, 3, 4, 5, 6, 7, 8, 9 C. Bellman ford
(B) 1, 2, 3, 4, 5, 6, 9, 8, 7 D. Subset sum problem
(C) 3, 4, 2, 1, 5, 8, 6, 9, 7 1. Divide and conquer
(D) 1, 3, 2, 4, 5, 6, 7, 9, 8
2. Dynamic programming
Q.25 Which of the following sorting
algorithm is used to sort largest element 3. Recursion
of the unsorted array or to find next 4. Greedy algorithm
largest element in each iteration? 5. Backtracking
Note : We need to arrange elements in (A) A-4, B-1, C-2, D-4
increasing order.
(B) A-4, B-1, C-2, D-2
(A) Bubble sort (B) Selection sort
(C) A-3, B-1, C-4, D-4
(C) Insertion sort (D) Quick sort
Q.26 Which of the following is the correct (D) A-2, B-3, C-4, D-2
pair of the time complexity with Q.30 Let G be connected undirected graph of
algorithm in undirected graph with 50 vertices and 150 edges. The weight of
given weight to find shortest path. a minimum spanning tree of G is 250.
Algorithm Time Complexity When the weight of each edge of G is
1. Bellman ford a. E log V increased by five, the weight of a
minimum spanning tree becomes _____.
2. Floyd warshall b. EV
3. Dijkshtra c. V 3 Q.31 Consider a complete undirected graph
with vertex set {1, 2, 3, 4, 5}. Entry Wij
4. Breadth first search d. V 2
e. ( E  V ) in the matrix W below is the weight of
the edge {i, j}. The minimum possible
(A) 1-b, 2-c, 3-a, 4-d
(B) 1-d, 2-c, 3-a, 4-e weight of a spanning tree T in this graph
(C) 1-c, 2-b, 3-a, 4-e such that vertex 1 is a leaf node in the
tree T is ___________.
(D) 1-a, 2-c, 3-b, 4-d

4 Algorithm
 ª0 1 6 1 3º (A) Minimum spanning tree of G does
«1 0 10 4 7 » not change
« »
W «6 10 0 5 2» (B) If e is the minimum weighted edge
« » of some cycle in G then every MST
«1 4 5 0 2 » of G includes e.
«¬4 7 3 2 0»¼
(C) Shortest path between any pair of
Q.32 The number of distinct minimum
vertices does not change.
spanning tree for the weighted graph
(D) If e is the maximum weighted edge
below is _____.
1 2 of some cycle in G then every MST
of G excludes e.
2 2 1 1
2 1 Q.35 If algorithm X is having better
1 2
asymptotic time complexity than
2 2 1 1
algorithm Y, then which of the following
2 is/are TRUE? (Mark all choices which
Q.33 An undirected graph G has n nodes. Its are CORRECT)
adjacency matrix is given by an n u n (A) X will outperform Y for all inputs
square matrix whose (i) diagonal (B) X will outperform Y for all small
elements are 0’s and (ii) non-diagonal inputs
elements are distinct. Let emax be the (C) X will outperform Y for all large
edge with maximum weight and emin be inputs
the edge with minimum weight. Which (D) X will outperform Y for all inputs
of the following is/are correct? above 1 million in size
[MSQ] Q.36 Suppose you are given the following set
(A) Graph G has multiple minimum of keys to insert into a hash table that
spanning trees of same cost (n  1) holds exactly 10 values:
(B) Every minimum spanning tree of G 13,107,49,50,64,98,16,33. Which of the
must contain emin . following best demonstrates the
contents of the hash table after all the
(C) If emax is in a minimum spanning
keys have been inserted using linear
tree, then its removal must
probing and mod 10 as hash function
disconnect G.
(D) No minimum spanning tree contains (A) 50….13 64 33 16 107 98 49
emax . (B) 50 33….13 64 ….. 16 107 98 49
Q.34 G (V , E ) is an undirected graph with (C) 50 …… 33 13 64 …… 16 107 98
distinct positive edge weights. If every 49
edge weight is increased by same value, (D) 50…….33 64 13 16 107 98 49
and e be the particular edge of G which Q.37 An array of 8 integers is being sorted by
of the following statement is/are True the heapsort algorithm. After the initial
regarding minimum spanning tree. phase of the algorithm (constructing the
[MSQ] heap), which of the following is a

Algorithm 5
 possible ordering for the array? (Mark sorting algorithms is/are the most
all the appropriate choices) [MSQ] appropriate for this?
(A) 2 6 11 13 21 41 43 92 (A) Merge Sort
(B) 2 13 6 43 92 11 21 41 (B) Selection Sort
(C) 2 6 11 41 92 13 21 43 (C) Quick Sort
(D) 2 6 11 21 11 41 43 13 (D) Heap Sort
Q.38 Which of the following is/are TRUE Q.42 Consider the binary tree shown below,
about Huffman Coding? (Mark all the which is an almost max-heap with the
appropriate choices) [MSQ] node 22 violating the max -heap
(A) Huffman coding may become lossy property. Once heapify procedure is
in some cases applied to it which position will it be in?
1
(B) Huffman Coding does not always
36
have an exact solution 2 3
(C) In Huffman coding, no code is 22 29
4 5 6 7
prefix of any other code
42 9 10 4
(D) There exists a greedy algorithm to 8 9 10
do Huffman coding 6 26 3
Q.39 Consider the following functions Q.43 In a hash table with 20 slots 30 records
[MSQ] are inserted with collisions being
log10 n,log 2 n, ª«log 2 n º» , «¬log 2 n »¼ resolved by chaining what is the
expected number of key comparisons in
Which of the following is/are TRUE?
an unsuccessful search assuming
(Mark all the appropriate choices)
uniform hashing?
(A) log10 n O(log2 n)
Q.44 Which of the following is/are the
(B) log 2 n : «¬log 2 n »¼ possible array contents after second pass
(C) «ªlog 2 n»º O(¬«log 2 n¼») of Quick Sort for the following initial
ordering assuming first element is taken
(D) «ªlog 2 n»º :(¬«log 2 n¼») as pivot?
Q.40 Consider a min heap implemented as an 34, 8, 64, 51, 32, 21
array with the elements 1, 2, 3, 6,7,8, (A) 8, 21, 32, 34, 51, 64
9,10. The level (starting from 1) in (B) 8, 8, 32, 34, 51, 64, 21
which 7 is stored is _______. (C) 8, 34, 51, 64, 32, 21
(D) 8, 34, 64, 51, 32, 21
Q.41 It is required to sort a large number large
Q.45 Given an array of n elements, you have
number of records of employee details to design an algorithm to find the k
based on the employee IDs. Assuming smallest elements in sorted order. The
the records are already sorted on the time complexity of the best algorithm
basis of employee names and it is assuming comparison based sorting will
required to maintain name as the be
secondary sort order (similar to order by (A) O(k log n) (B) T(n  k log k )
id name in SQL), which of the following (C) T(n2 ) (D) T(n log k )

6 Algorithm
Q.46 Suppose that you store 6 records in a Q.49 You are given an empty hash table of
hash table of size 8 by chaining, and size 6 that uses open addressing. The
suppose that you have a good hash following sequence of keys is to be
function so that the probability that a key inserted: [MSQ]
is hashed into any of the 8 slots is 1/8. 32 7 14 22 29 3
For a particular slat in the hash table, If linear probing with h( x) x %6; is
what is the probability that this slot is used, which all elements will cause a
empty, that is, none of the 6 keys hashes collision? (Mark all choices which are
into this slot? CORRECT)
(A) 0.1256 (B) 0.8756 (A) 3 (B) 14
(C) 0.1668 (D) 0.8338 (C) 29 (D) 22
Q.47 Consider the following graph. If BFS is Q.50 Consider the following C function
implemented on the following graph int findme (int n)
then which of the following set of the {
nodes are present in the queue after if (n < = 0) return 1;
performing 5th dequeue operation? return findme (n/2) + findme (n-1)
(Root vertex is 1 and consider }
descending order while visiting the What will be the output if the above
vertices.) function is called with argument 12 ?
Q.51 For quick sort pivot selection you are
provided with an buggy implementation
of Median select which can return any
element between (n/3)rd smallest and
(2n/3)rd smallest in O(n) time. With this
function to choose the pivot, which of
the following is/are TRUE for the
Quicksort implementation? (Mark all
(A) 2, 7, 6 (B) 2, 3, 4 CORRECT choices) [MSQ]
(C) 3, 4, 6 (D) 8, 7, 6 (A) In best ease it can run in O(n) time
Q.48 Consider the following C function and
(B) In worst case it will take T(n2 ) time
an input array to it as [1, 4, 10, 12] and
len as 4. The return value of the function (C) In worst case it will take T(n log n)
will be time
int foo (int arr [], int len) (D) In best case, It will run in
{ :(n log n) time
int result = 0 ; Q.52 What is the time complexity of
for (int i = 0; i < len; ++) following code if foo(n) takes T(log n)
{ time to execute?
result + = arr [i] * (i+1)* (len – i); int i , j;
} for (i = n / 2; I < = n; i++)
return result: {

Algorithm 7
 for (j = 1; j < = n; j = j * 2) (B) The expected number of
{ comparisons in a successful binary
foo (j); search is O(log n)
} (C) The best case runtime of linear
} search is asymptotically better than
binary search
(A) T(n) (B) T(n lg n)2
(D) In worst case binary search can lead
(C) T(n (lg n)2 ) (D) T(n2 lg n) to :(n) comparisons
Q.53 The return value, time complexity and Q.56 Suppose the letters a, b, c, d have
space complexity of the following code probabilities 1/3, 1/6, 1/6, 3/10
are respectively. What is the average length
int foo (int n) of Huffman codes (correct to 1 decimal
{ point)?
int a = 0 Q.57 You are given an empty hash table of
while (n > 0) size 7 that uses open addressing. The
{ following sequence of keys is to be
a + = n; inserted:
n/=2; 13 18 25 11 20 29
} If hash function h1 ( x)%7; and double
return a; hashing with h2 ( x) x / 7 1 is
}
followed, which of the inserted elements
(A) T(log n,), T(log n), T(log n) causes a collision? (Mark all the
(B) T(n), T(log n), O(1) appropriate choices) [MSQ]
(C) T(log n), T(log n), O(1) (A) 25 (B) 11
(D) T(n2 ), O(n), O(1) (C) 20 (D) 29
Q.58 Which of the following statements is/are
Q.54 Suppose you are having 5 notes each
TRUE? (Mark all the appropriate
with denominations of 2000, 500,300
choices) [MSQ]
and 50 and you are asked to make a sum
(A) The worst case runtime for searching
of Rs 4650. For each note you choose
in a binary tree can be O(n).
you are asked to pay a service charge of
(B) The minimum number of
Rs. 2.5 which is irrespective of the
comparisons to sort 5 elements is 4.
denomination of the note, what will he
the minimum amount in rupees you'll ª n º
(C) There can be at most « h1 » nodes of
have to pay as service charge? ¬2 ¼
Q.55 Which of the following statements is/are height h (h starting from 1) in any n
TRUE? (Mark all CORRECT choices) element heap.
(A) The expected number of (D) The time to find the maximal
comparisons in a successful linear element in a min-heap of 2n – 1
search is n elements is :(2n )

8 Algorithm
Q.59 Four matrices M1 , M 2 , M 3 and M 4 of for (i = 1; i < size; i++)
dimensions p u q, q u r, r u s and s u t {
respectively can be multiplied is several value = arr [i];
ways with different number of total j = i;
scalar multination’s. For example, when while (________)
multiplied as (( M1 u M 2 ) u ( M 2 u M 4 )) , {
the total number of multiplications is arr [j] = arr [j - 1];
pqr  rst  prt . When multiplied as J = j – 1;
(((M1 u M 2 ) u M 3 ) u M 4 ) , the total }
number of scalar multiplications is arr [j] = value
pqr  prs  pst . }
}
If p 20, q 90, r 10, s 15 and t =
Which condition will correctly
40, then the minimum number of scalar
implement the which loop?
multiplications needed is
(A) (j > 0) || (arr [j – 1] > value)
Q.60 Maximum Subarray Sum problem is to
find the subarray with maximum sum. (B) (j > 0) && (arr [j – 1] > value)
For example, given an array {12, –13, – (C) (j>0) && (arr[j+1]) > value)
5, 25, –20, 30, 10}, the maximum (D) (j>0)&&(arr[j+1]<value)
subarray sum is 45. The best possible Q.63 Consider the following C function for
algorithm to compute the maximum arguments m, n > 1
subarray sum will run in int foo (int n, int m)
(Mark all the appropriate choices) {
(A) O(n) (B) :(n log n) While (m! = n)
(C) O(log n) (D) O(n2 ) {
Q.61 During solution of T (n) recurrence if (m>n)
relation we find the following series, m = m – n;
solve it and find the value of T (n) . else
n = n – m;
T (n) 1.21  2.22  3.22
}
4.24  5.25  6.26
return n;
7.27  ...n.2n }
(A) O (2n ) (B) O (2n ) Which of the following is/are true about
(C) O (n.2n ) (D) O (n2 .2n ) the above function? (Mark all
Q.62 Consider the code given below, which CORRECT choices)
runs insertion sort; (A) If m = 9 , n = 13 the function returns
void insertion Sort (int arr [], int size) 1.
{ (B) The asymptotic time complexity of
int i, j, value the function is O(log(max(m,n)))

Algorithm 9
 (C) For any positive integers m, n the Q.66 You're working on a dynamic
function returns the least common programming problem that has a
multiple of m, n. recurrence elation
(D) The space complexity of the A(i, j ) F ( A(«¬i / 2»¼ , j ) A,(i, «¬ j / 2»¼))
function is :(1og)(min(m, n))
where F is a known function that can be
Q.64 Which of the following statements is/are evaluated in constant time and
TRUE? (Mark all CORRECT choices} A(i, j ) 0 when i 0 or j 0 . To
(A) When 90% of the input is already in
compute A(m, n) for some m and n, you
sorted order, insertion sort will do
can use either a top – down or a bottom
less number of comparisons than
– up method. Which one is more
merge sort for all sufficiently large
efficient in solving this problem?
inputs
(B) If the number of inversions in an (A) Top Down will take asymptotically
array is O(n), then insertion sort will lesser time than bottom up
be having fewer comparisons than (B) Bottom-up will take asymptotically
quick sort for all inputs lesser time than Top Down
(C) If the number of inversions in an (C) Both will take the same time
array is O(n), bubble sort will be (D) None of them
having fewer number of Q.67 In bottom-up dynamic programming, we
comparisons than merge sort for all
need an order to fill m the solution cells
inputs
(D) If the number of inversions in an m a table, such that all needed
array is O(n), heap sort will be subproblems are solved before solving a
having fewer number of subproblem. For the following relation,
comparisons than insertion sort for give a valid traversal order.
all inputs A(i, j ) F ( A(i, j 1), A(i 1, j 1)
Q.65 Consider the following recurrence A(i 1, j  1))
relation which is applicable on two A(0, j ) 0
arrays x and y , xi and yi , are the i th A(i,0) 0
elements of x and y array respectively. Where F(.) is a function.
­ 0 (A) Fill values of A(i, j) column-wise,
°
c(i, j ) ® c(i  1, j 1)  1 i.e., fill the first column then the
°min(c(i 1, j ), c(i, j 1)) second column, and so on.
¯
if i 0or j 0 (B) Fill the last column of A(i,j). then the
if i, j ! 0and xi yi second last column, and so on.
if i, j ! 0and xi z yi (C) Fill values of A(i, j) row-wise i.e.
fill the first row then the second
Suppose each array is of n size and time
complexity to compute c (n,n) using row, and so on.
dynamic programming is O(na (log n)b ) (D) No order is possible as there Is cyclic
then what will be value of a + b? dependency in subproblems.

10 Algorithm
Q.68 Consider the following code snippet : distinct weight from 1, 3, 9, 27, 81 and
int i 0; 243. Which of the following will not be
while (i  n) the weight of the minimum spanning
tree of G? [MSQ]
{
(A) 121 (B) 13
printf (“computer science batch1”);
(C) 40 (D) 31
while (i  n)
Q.71 Consider the following 0 -1 knapsack
{
problem with the item’s weight and
printf (“computer network”); value given in the table
while (i  n) Item Weight Value
{ 1 3 Rs 25
printf (“compiler design”); 2 2 Rs 20
i  ;
3 1 Rs 15
}
4 4 Rs 40
i  ;
5 5 Rs 50
}
Capacity W = 6
i  ;
If the capacity of the knapsack (W), is 6
} then how many optimal solutions
What will be the time complexity of (number of set of items) are possible?
above code snippet? (A) 1 (B) 2
(A) T(n5 ) (B) T(n6 ) (C) 3 (D) 4
(C) T(n4 ) (D) T(n3 ) Q.72 For a given sequence of integers
Q.69 While walking on the beach one day you a1 , a2 ,..., an decreasing subsequence is
find a treasure trove. Inside there are n one for which every integer is strictly
treasures with weights w1.., wn and smaller than the previous one.
values v1….vn. Unfortunately, you have a The longest decreasing subsequence is
knapsack that only holds a total weight the longest among all decreasing
M. Fortunately, there is a knife handy so subsequences of a given sequence.
that you can cut treasure if necessary to For example, decreasing subsequences
take home treasure of maximal value: a of 5, 2, 4, 8,3, 40 are .
cut treasure retains its fractional value • 5, 2
(so, for example a third of treasure I has • 5, 4
weight wi / 3 and value vi/3). What is the
• 4, 3
maximum value that can take home if
• 5, 4, 3 etc
we have 3 treasures with weights (18,
And longest among all possible
15, 10) and values (25, 24, 15) and also
a knapsack of total weight 20? decreasing subsequences is 5, 4, 3.
Q.70 Consider G (V, E) be a complete For a given sequence of integers
undirected graph with 6 edges having a a1, a2,.....an let L(j) be length of the

Algorithm 11
 longest decreasing subsequence that product of 6 matrices whose sequence of
starts with a j . dimensions is 5,10,3, 12,5,50 and 6.
That is 5 u10 is dimension of first
L ( n) 1
matrix, 10 u 3 is dimension of second
­1 if a j min(a j , a j 1, a j 2 ,.., an ) matrix and so on.
L( j ) ®
¯? otherwise Q.75 The number of longest common
Complete the above recurrence relation subsequences for "bacb" and 'abcabc'
with the appropriate value of ? are:
(A) 1 + min{L(k):j < k d n and a j ! ak (A) 2 (B) 3
} (C) 4 (D) 5
(B) 1 + max {L(k) : j < k d n and Q.76 For the given recurrences calculate the
a j ! ak } tightest bound on time and space that
would be required by a dynamic
(C) 1 + max {L(k) : j < k d n and
programming algorithm to compute
a j  ak } OPT(n).
(D) 1+ min {L(k): j < k d n and a j ! ak OPT(i) min{OPT( j) / j  w( j)}
1d j i
} where OPT(l) = l
Q.73 Consider a DAG G = (V, E) which has
(A) Time = O(n2 ) , space = O(n)
topological ordering of vertices
v1 , v2 ,....., vn . We want to count number (B) Time = O(n3 ) , Space = O(n2 )
of paths from vertex v1 to vertex vn . Let (C) Time = O(n2 ) , Space = O(n2 )
Paths(i) represents total number of paths (D) Time = O(n), Space = O(n).
from i to n. Q.77 Suppose you have a row of coins with
Complete the following recurrence for values that are positive integers
Paths (i). c1 ,......, cn . These values might not be
­1 if i n distinct. Your task is to pick up coins
Paths(i) ®
¯? otherwise that have as much total value as possible,
subject to the constraint that you don't
In options, 6 j:(i , j )E Paths (j) is a
ever pick up two coins that lie beside
quantity which sums Paths (j) for all each other. For example - Given c1 to c6
outgoing edges from i i.e., for edges
as follows- (5, 1, 2, 10, 6, 2), the
io j
maximum value is 17 and using coins
(A) 6 j:(i , j )E (1+Paths (j)) {c1 5, c1 10, c6 2}
(B) 6 j:(i , j )E Paths (j) Let f (n) be maximum total value with n
(C) 1  6 j:(i , j )E Paths (j) coins with f (0) 0 and f (1) c1 then
(D) 1+Paths (j) for some edge i o j what will be correct recurrence for f (n)
Q.74 Find total number of scalar ?
multiplications of a matrix-chain (A) f (n) max(cn  f (n  2), f (n  1))

12 Algorithm
 (B) f (n) max(cn1  f (n  2), f (n  1)) (A) Only S1
(C) f (n) max(cn1  f (n  1), f (n  2)) (B) Only S 2
(D) f (n) max(cn  f (n  1), f (n  2)) (C) Both S1 and S 2
Q.78 Consider the following code snippet. It (D) Neither S1 or S 2
accepts a positive integer n as input,
Q.82 Consider the directed acyclic graph
int i = 0, j = 0, val = 1;
given below. How many topological
for (i = 1, i < = n; i++){
ordering are possible for the given
j = n;
graph?
if (i % 2 = = 0){
while (j >1) {
val = val * j;
j = j/2
}
}
} Q.83 Match the following and choose the
What is the worst-case time complexity correct solution for the order A,B,C,D
of the algorithm?
Strassen p Decrease and
(A) O (n) (B) O (n log n)
A matrix Conquer
(C) O (n 2 ) (D) O (n2 log n) multiplication
Q.79 The time required by an efficient B Insertion sort q Dynamic
algorithm to determine whether an programming
arbitrary array of size n is min-heap or
C Gaussian r Divide and
not is
Elimination conquer
(A) O (log n) (B) O (n)
D Floyd shortest s Transform and
(C) O (n log n) (D) None of these
path algorithm Conquer
Q.80 What is time complexity of matrix
multiplication (Strassen’s) using divide
(A) r,s,p,q (B) r,p,s,q
and conquer approach?
(C) q,p,s,q (D) s,p,q,r
(A) O (nlog2 5 ) (B) O (nlog2 6 )
Q.84 Consider the following functions:
(C) O (nlog2 7 ) (D) None of these f (n) 2n , g (n) n!, h(n) nlog n
Q.81 Consider the following steps :
Which of the following statements about
S1 : Characterize the structure of an
the asymptotic behavior of f (n) , g (n)
optimal solution. and h (n) is true?
S 2 : Compute the value of an optimal
(A) f (n) O ( g (n)); g (n) O (h(n))
solution in bottom-up fashion.
(B) f (n) O ( g (n)); g (n) O (h(n))
Which of the following step (s) is/are
common to both dynamic programming (C) g (n) O ( f (n)); h (n) O ( f (n))
and Greedy algorithm? (D) h(n) O ( f (n)); f (n) O ( g (n))

Algorithm 13
 Q.85 The weight of a sequence a0, a1, ..., an-1 Assume that node ‘S’ is the starting
of real numbers is defined as vertex for prim’s algorithm. Which of
a0+a1/2+...+ aa-1/2n-1. A subsequence of a the following can be the correct order of
sequence is obtained by deleting some edges in which they are added to
elements from the sequence, keeping the construct the minimal spanning tree?
order of the remaining elements the (A) 4, 2, 1, 6, 8 (B) 4, 1, 2, 6, 8
same. Let X denote the maximum (C) 4, 2, 1, 7, 10 (D) None of these
possible weight of a subsequence of a0,
Q.88 The minimum number of comparisons
a1, ...,an-1 and Y the maximum possible
required to find maximum element in a
weight of a subsequence of a1, a2, ...,an-1.
min-heap of n elements (assume n ! 1 )?
Then X is equal to
(A) max(Y, a0+Y) «n»
(A) n  1 (B) « »  1
(B) max(Y, a0+Y/2) ¬2¼
(C) max(Y, a0+2Y) ªnº
(C) « »  1 (D) n
(D) a0+Y/2 «2»
Q.86 Consider the following C code segment: Q.89 The running time of an algorithm is
int f (int x) given by
{ T (n) T (n  1)  T (n  2)  T (n  3), if n ! 3
if ( x  1) return 1; ,T(n)= n otherwise, then what should be
else return ( f ( x  1)  g ( x)); the relation between T(1),T(2) and
} T(3), so that the order of the algorithm is
int g (int x) constant?
{ (A) T(1) = T(2) = T(3)
if ( x  2) return 2; (B) T(1) + T(3) = 2*T(2)
else return ( f ( x  1)  g ( x / 2)); (C) T(1) – T(3) = T(2)
} (D) T(1) + T(2) = T(3)
Of the following, which best describes Q.90 What is the time complexity for the
the growth of f ( x) as a function of x ? following C module? Assume that n>0
(A) K1 x  K 2 (B) K x int module (int n)
(C) Kx 2 (D) Kx 3 {
Q.87 Consider the following graph. if (n = = 1)
return 1;
else
return (n + module (n-1));
}
(A) O(n) (B) O(log n)
(C) O(n 2 ) (D) O(n!)

14 Algorithm
Q.91 Match the following: Q.95 The characters a to f have set of
frequencies as
a : 5, b : 9, c : 12, d : 13, e : 16, f : 55
Huffman coding is used to encode the
character what is the average number of
bits required for character_________.
Codes: Q.96 Find the average number of comparisons
(A) P-3, Q-2, R-1 (B) P-3, Q-2, R-2 in a binary search on sorted array of 7
(C) P-2, Q-1, R-1 (D) P-2, Q-1, R-4 elements ________.
Q.92 Let T (n) T (n / 5)  T (7n /10)  c.n
Q.97 Consider 5 items along their respective
where c is a constant. Find running time weights and values
of T (n) .
I [ I , I 2 , I3 , I 4 , I5 ]
(A) 4 (n) (B) 4 (n log n)
W [5,10, 20,30, 40]
(C) 4 (n2 ) (D) None of these
V [30, 20,100,90,160]
Q.93 Consider the following two functions :
­n3 for 0 d n d 10,000 The capacity of knapsack W 60 . Find
g1 (n) ® 2 the maximum value using fractional
¯ n for n t 10,000 knapsack is ____
­n for 0 d n d 100 Q.98 Consider the program
g2 (n) ® 3
¯ n for n ! 100 gate academy (int n)
Which of the following is true? {
(A) g1 (n)is O( g2 (n)) int i, j, c = 0
1
(B) g1 (n)is O(n 2 ) § n ·
for ¨ i 1; i  ; i   ¸
(C) g2 (n)is O( g1 (n)) © 2 ¹
{
(D) g2 (n)is O(n)
for ( j 1; j  n; j j 2)
Q.94 A Priority-Queue is implemented as a
Max- Heap. Initially, it has 5 elements. {
The level- order traversal of the heap is c++;
given below: }
10, 8, 5, 3, 2 }
Two new elements ‘1’ and ‘7’ are }
inserted in the heap in that order. The
The complexity of the program is?
level- order traversal of the heap after
(A) O (log n)
the insertion of the elements is:
(A) 10, 8, 7, 5, 3, 2, 1 (B) O (n 2 )
(B) 10, 8, 7, 2, 3, 1, 5 (C) O (n2 log n)
(C) 10, 8, 7, 1, 2, 3, 5
(D) 10, 8, 7, 3, 2, 1, 5 (D) O (n log n)

Algorithm 15
 Answers Algorithm

1. A,B 2. 56 3. A,B 4. C,D 5. B

6. 8 7. 13 8. A.D 9. 4 10. 13

11. 0 n 12. A 13. 748 14. C 15. D

16. C,D 17. D 18. 61 19. B 20. D

21. 860 22. C 23. B 24. C 25. A

26. C 27. 207 28. 77 29. B 30 495

31. 9 32. 24 33. B,C 34. A,D 35. C

36. A 37. A,C 38. C,D 39. A,B,C,D 40 3

41. A 42. 9 43. 1.5 44. A 45. B

46. B 47. A 48. 136 49. A,B 50. 94

51. C,D 52. C 53. B 54. 12.5 55. B

56. 2 57. A,B,C,D 58. A,D 59. 32000 60. A

61. C 62. B 63. A 64. B 65. 2

66. A 67. C 68. D 69. 28 70. A,C

71. A 72. B 73. B 74. 1860 75. C

76. A 77. A 78. B 79. B 80. C

81. A 82. 8 83. B 84. D 85. B

86. B 87. D 88. C 89. A 90. A

91. C 92. A 93. A 94. D 95. 2.12

96. 2.428 97. 270 98. D

Algorithm 16
 Explanations Algorithm

1. (A,B)
Total bits without compression 11u 8 88
(A) 1 2 3 4 5 6 bits
J1 J2 J3 J4 J5 Number of bits
(1u 4)  (3 u 2)  (1u 4)
Invalid  (2 u 3)  (1u 3)  (1u 3)
(B) 1 2 3 4 5 6  (1u 3)  (1u 3)
J3 J6 J2 J5 J4 J1 Valid 4  6  4  6  3  3  3  3 32 bits
(C) 1 2 3 4 5 6
Number of hits saved 88  32 56 bits
J6 J5 J3 J2 J4 J1
Hence, the correct answer is 56.
Valid
3. (A,B)
(D) 1 2 3 4 5 6
J6 J5 J4 J3 Dijkshtra algorithm is greedy algorithm but
Bellman ford and floyd warshall are dynamic
Invalid programming algorithms.
Hence, the correct option are (A,B). Hence, the correct option are (A,B).
2. 56 4. (C,D)
g 1 1110 (A) Starting from M which is connected all
a 3 10 nodes so any sequence Ÿ all valid
t 1 1111 (B) N o M Ÿ all valid
e2 110 (C) QoS oN
c 1 000 Invalid

d 1 001 (D) R oT oQ
m 1 010 Invalid

y 1 011 Hence, the correct option are (C,D).

5. (B)

P Q R
0 1 3

Q R S T
1 3 3 5

R S T V
3 3 5 5

S T V U
3 5 5 8

Algorithm 17
 T V U 16

5 5 8 1
0
V U 9
0 1
5 8 7
4 p
U - 0 1
5
q r 0 1
8 -
3 4 s e
node π distance 1 3
P – –
Q 1 P
9
R 3 P
S Q 3
4 p 7
T Q 5
5
U S 8
V R 5 s e q r
1 3 3 4
Selected shortest path by Dijkstra Peers Ÿ p  e  e  r  s
1 2 5 p
P Q S U
2  3  3  2  3 13
Note : P 
1
o Q 
4
oT 
3
oU . This is also
Hence, the correct answer is 13.
shortest path but it will not be selected by
Dijkstra. 8. (A,D)
Hence, the correct option is (B). Frequency
6. 8 p  5 Ÿ 11

Selected path by Dijkstra’s algorithm, q  3 Ÿ 00

1
Q
2 5 r  4 Ÿ 01
P S U
s  1 Ÿ 100
Cost 1  2  5 8
e  3 Ÿ 101
Hence, the correct answer is 8.
p e e r s
7. 13 p p p p p
11 101 101 01 100

Frequency binary code =

p  5 Ÿ 11 11 101 101 01 100
q  3 Ÿ 00 1’s complement
r  4 Ÿ 01 This is also a binary
0 0 010 01010011 Ÿ
s  1 Ÿ 100 code (valid)
e  3 Ÿ 101 Hence, the correct option are (A,D).

18 Algorithm
 9. 4 12. (A)
P M , N , O, N , R, M , N T ( x) nT n  100 n
Q N , R, O, M , N , M
Let, n 2k Ÿ k log n
1. MNM 3 2. NRMN 4
3. RMN 3 4. NONM 4 T (2k ) (2)k /2 T (2k /2 )  200 u 2k
5. NONM 4 (dividing by 2k )
Hence, the correct answer is 4. T (2k ) 2k /2 T (2k /2 )
 100
10. 13 2k 2k
Longest common length subsequences : T (2k ) T (2k /2 )
 100
1. NRMN 2k 2k /2
2. NONM T (2k )
Let, y (k ) , then …(i)
3. NOMN 2k
a 3 §k·
Smallest common length subsequences : y (k ) y ¨ ¸  100
© 2¹
1. MN 2. NM
Now, applying master theorem [a bk 1]
3. RM 4. RN
5. NR 6. NO y(k ) log k
7. ON 8. OM From (i) we also know that T (2k ) 2k y (k ) ,
9. NN 10. MM then
b 10 T (2k ) 2k log k T (n)
b  a 10  3 13
n log log n (because n 2k and k log n )
Hence, the correct answer is 13.
Finally, T (n) T (n log log n)
11.
Hence, the correct option is (A).
i 1, s 1 13. 748
i 1 2 3 4 5
n 500 (array)
s 1 3 6 10 15
I. linear comparision :
We see that s is the sum of n terms function is Total comparisons
k (k  1) 2n 2 u 500 1000
s
2 II. Using Divide and Conquer approach :
But s d n must be true
3n
So, the maximum value of s is Total comparisons  2 (go through
2
k (k  1) k2  k minmax algorithm)
nŸ n
2 2 3 u 500
 2 748
k2 2n 2
k 0 n Min (748, 1000) 748
Hence, the correct answer is 0 n . Hence, the correct answer is 748.

Algorithm 19
 14. (C) comparisons. But here we have to find the
number which is not minimax so, simply we can
Merge sort does not depend on input data but
pic 3 number and compare them the middle
Selection, Bubble and Quick sort depends on
element of three of will be not an minimax, so
input data based on that their time complexity
always required only 2 comparisions
varies.
So, T (1) time complexity.
Hence, the correct option is (C).
15. (D) Hence, the correct option is (D).
18. 61
Note : cos x and sin x are periodic functions.
(0,1) S /2 edge AB 10 ( AC 9 selected)
BC 2
edge BE 16 ( DE 15)
S (1,0) (1,0)0, S cos x  sin x
CE 17
edge BD 11 (CD 10)

(0,  1) 3S /2
edge DF 7 ( EF 6)

Range of cos x & sin x is [–1, 1] Minimum sum AB  BD  BE  CE  DF

Ÿ f (n) n1cos x 10  11  16  17  7 61
Hence, the correct answer is 61.
Ÿ 0(1),0(n),0(n2 ) possible values
19. (B)
g (n) 0(1),0(n),0(n2 )
If we consider Left skewed or Right skewed
So, we can’t predict or conclude exact relation then in worst case we need to traverse n nodes
between f (n) and g (n). so, its complexity becomes 0 (n). For 1
Hence, the correct option is (D). insertion, we have to insert n elements,
16. (C, D) Time Complexity n ˜ 0(n)
n2 (n2  1) (2n2  1) n2(n2  1) 0 (n 2 )
X 
6 2 Hence, the correct option is (B).
n ª¬n  n  1  n  1º¼
2 4 2 2
20. (D)
n n n n n n
6 4 4 2 4 2
Quick sort algorithm Recurrence Relation is,
n6  3n4  2n2 T (n) T (k )  T (n  k  1)  0(n)
(lower terms neglected)
6
Worst case : k 0 (last element is sorted in its
0 (n )
position only).
Hence, the correct option are (C,D). T (n) T (0)  T (n  0  1)  0(n)
17. (D)
T (n) T (n  1)  0(n)
To find minimax algorithm we can use divide T (n) 1
3n
and conquer algorithm with  2 minimum Hence, the correct option is (D).
2

20 Algorithm
 21. 860
Dimensions of four matrices ABCD.
A 5 u 7, B 7 u 4, C 4 u10, D 10 u12

1236 (ABCD) 860 940

5 u 7 u12 420 (AB) ( CD) ( ABC) D

A(BCD) 5u 4 4 u12
480 5 u10 u 12 600
816 7 u 10 5 u 7 u 4 140
700 340

5 u 12 5 u 10

7 u 4 u12 336 7 u 10 u 10 700 A(BC) ( AB) C

B(CD) (BC)D
7 u 12 u 5 420 7 u 12 5 u 4 5 u 4 u10 200
4 u 12 7 u10
280 140
4 u 10 u 12 480 7 u 4 u 10 280

Hence, the correct answer is 860.

22. (C) Hence, the correct option is (B).

Settle above multiplication tree (( AB ) (CD)) 24. (C)

gives minimal scalar products as 860 with 8 3 4 6 7 2 1 9 5

dimension 5 u12 A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
Hence, the correct option is (C).
5 as pivot
23. (B) So i is 1 and j is 0 [check A[i ]  5 ]
§n· Check A[ j ]  5 false i i  1
Given : T (n) 2T ¨ ¸  n
©2¹ Check A[2]  5 true
As we know by Masters theorem : j m j  1 and exchange A[i] l A[ j ]
§n· So, A[1] and A[2] are exchange then i m i  1
For T (n) aT ¨ ¸  T(nk log p n)
©b¹
3 8 4 6 7 2 1 9 5
a ! bk Ÿ T (n) T(nlogba )
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]
1
a 2, b 2, k , p 0 Check A[3]  5 true j m j  1
2
2 ! 21/2 {a ! bk } So, A[2] and A[3] are exchange, i m i  1

T (n) T(n) 3 4 8 6 7 2 1 9 5

T(nlogb a ) T(n1 ) T(n) A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9]

Algorithm 21
 Check A[4]  5 false, i m i  1 88 87

Check A[5]  5 false, i m i  1 35

35 34 53 52
Check A[6]  5 true
e f 22
e
So j m j  1 and exchange A[i] l A[ j ] 15 20
f 23 a
15 20 30
So, A[3] and A[6] are changed 50i m i  1
c 13 12
3 4 2 6 7 8 1 9 5 10

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] b d

5 8
Check A[7]  5 true
Minimum record movements
So j m j  1 and exchange A[i] l A[i] 12  22  34  52  87 207
So, A[4] and A[7] are exchanged, i  i Hence, the correct answer is 207.
3 4 2 1 7 8 6 9 5 28. 77

A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] Index position in upper triangular matrix is,
Check A[8]  5 false (i  1) u (i  2)
n (i  1)   j i
2
So, j  j  1 and exchange A[ j  1] with our
(7  1) u (7  2)
data (5) 15(7  1)  97
2
3 4 2 1 5 8 6 9 7 6u5
15 u 6  2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] 2
The answer is 3 4 2 1 5 8 6 9 7. 90  15  2 77
Hence, the correct option is (C). Hence, the correct answer is 77.
29. (B)
25. (A)
A o Prim’s algorithm Ÿ Greedy algorithm
Bubble sort is the sorting algorithm in which
B o Quick sort Ÿ Divide and conquer
every iteration it eliminates largest element
C o Bellman ford Ÿ D.P.
form the given array and reduces the array size
D o Subset sum problem Ÿ D.P.
for the next iteration.
Hence, the correct option is (B).
Hence, the correct option is (A).
30. 495
26. (C)
Number of vertices (n) 50
1. Dijkshtra Ÿ 0( E  V ) log V or E log V Number of edges in minimum spanning tree
2. Floyd warshall Ÿ n or V
3 3
(n  1)
3. Bellman Ÿ n3 or V 3 (50  1) (49)
4. BFS Ÿ 0( E  V ) Weight of every edge increased by 5 49 5
245
Hence, the correct option is (C).
New weight 250  245 495
27. 207 Hence, the correct answer is 495.

22 Algorithm
 31. 9 Node 4 : min edge Ÿ (4, 5)
4
We will use Kruskal’s algorithm (For MST) 2 4
1 2 3 4 5
1 1 6 1 3 2
0
2 1 0 10 4 7 2
3 5
3 6 10 0 5 2
4 Final tree with node 1 as leaf node
1 4 5 0 2
4
5 4 7 3 2 0
4 2
node 1 : Minimum weight edge (1, 2) & (1, 4) 2 5
Note : node 1 is a leaf node so out of (1, 2) or
1 2
(1, 4) only 1 can be considered.
Leaf node 3
Node 2 :
4 Total weight of MST 4  2  1  2 9
2 4
Hence, the correct answer is 9.
Node 3 : min edge Ÿ (3, 5)
2
3 5

32. 24

Total MST possible 3 u 2 u 4 24 Hence, the correct option are (B,C).

Hence, the correct answer is 24. 34. (A,D)
33. (B,C)
(A) True :
(A) False : Due to distinct weight there will (C) False : Shortest path may differ.
be unique MST. Ex : 5 edges with shortest path 15 and
(B) True : emin will always be part of MST other path with 2 edges with weight 25
due to distinct weight but now 10 cost increased then,
(C) True : If emax is a part of MST it means 5 10 50  15 65
it is bridge whose removal disconnects 2 10 20  25 45 this becomes now
graph. shortest path.
(D) False : Option C is the reason (B) False :

Algorithm 23
 a 2 b a 2 b 4 64
5 33
5 4 3 Ÿ 5 4 3
 6 16
7 107
d 6 c a b 8 98
( Creates Cycle) even 9 49
though it is minimum Hence, the correct option is (A).
(D) True :
37. (A,C)
Hence, the correct option are (A,D).
We know, that heap can be either min heap or
35. (C)
max heap, but not both at the same time (Similar
Asymptotically better means for sufficiently to EXOR gate in digital logic).
large inputs, X is better than Y. i.e., beyond a 2
large input size N, time taken by X is lower than
that taken by Y. Only option C is TRUE. 6 11

Option D is wrong because "1 million" is not a 13 21 41 43

limit to be "large" - this limit can be any value -
1 million +100,1 billion or even larger value. All 92
we need is to ensure such a limit exists, however (A) Min Heap
large that may be. 2
Hence, the correct option is (C).
13 6
36. (A)
43 92 11 21
Given that, the values: 13, 107, 49, 50, 64, 98,
16, 33 41
y 13 mod 10 3  No collision (B) Not a min heap, or not a max heap
y 107 mod 10 7  No collision 2
y 49 mod 10 9  No collision
6 11
y 50 mod 10 0  No collision
y 64 mod 10 4  No collision 41 92 13 21
y 98 mod 10 8  No collision
43
y 16 mod 10 6  No collision
(C) Min heap
y 33 mod 10 3  There is collision, so 33
2
will go to next free slot.
Hash Table 6 11
Index Values
21 11 41 43
0 50
1 13
2 (D) Not a min heap, or not a max heap
3 13 Hence, the correct option are (A,C).

24 Algorithm
 1
38. (C,D)
36
2 3
Huffman coding is a lossless coding and has an
42 29
exact greedy algorithm. In this coding, the codes 4 5 6 7
are represented by the binary paths from root to 22 9 10 4
leaf and thus no code can be a prefix of another. 8 9 10
6 26 3
39. (A,B,C,D)
Swapped 22 and 26, we get max-heap.
Ceil and floor do not affect the asymptotic 1
growth. And the base of logarithm also does not 36
2 3
affect the asymptotic growth. So, here, 42 29
log10 n 4(log2 n) 4 >log2 n@ 4 >log2 n@ 4 5 6 7
26 9 10 4
Hence, the correct option are (A,B,C,D). 8 9 10
6 22 3
40. 3
Hence, the correct answer is 9.
1
43. 1.5

2 3 In a hash-table with chaining and uniform

hashing, the expected number of comparisons in
6 7 8 9 an unsuccessful search is given by D where
m
D is the load factor.
10 n
7 is in level 3. 3
Here, D 1.5 . So, expected number of
Hence, the correct answer is 3. 2
comparisons for an unsuccessful search 1.5
41. (A)
Hence, the correct answer is 1.5.
Question is implying a stable sort. Among the
44. (A)
ones in options, only Merge Sort is stable.
Hence, the correct option is (A). In first pass 34 is the pivot. So, it'll get position
as in the final sorted order which is 4th position.
42. 9
This is true only for option A.
We need to perform swapping, to get max-heap. Hence, the correct option is (A).
1
45. (B)
36
2 3 The best possible algorithm will find the k th
22 29 smallest element in O(n) time and then move all
4 5 6 7
elements smaller than this to its left - partition
42 9 10 4
part of quick sort which again takes O(n) .
8 9 10
6 26 3 Finally, these k elements can be sorted in 0(k log
k) time.
Swapped 22 and 42, we get
Hence, the correct option is (B).

Algorithm 25
 46. (B) y When
i 2 | result result  arr[2]* 2 1 *
We want all the n keys to go to m  1 locations
only. Probability for this will be 42 28  10*3*2 88
m 1
n
6
y When
n
Ÿ 1  0.125 0.8756 i 3| result result  arr[3]* 3  1 *
m
Hence, the correct option is (B). 4 1 88  12*4*1 136
47. (A) Hence, the correct answer is 136.
Enqueue node 1 in the queue. 49. (A,B)
Queue: 1 y 32 mod 6 2  occupies slot 2
Mark it as visited. Dequeue 1 and enqueue its y 7 mod 6 1  occupies slot 1
non-visited adjacent nodes in ascending order. y 14 mod 6 2  collide. Occupies next
Queue: 8 5 4 3 2 slot which is slot 3
Mark 8 as visited. Dequeue 8 and enqueuer its y 22 mod 6 4  occupies slot 1
non-visited adjacent nodes in ascending order. y 29 mod 6 5  occupies slot 5
Queue :5 4 3 2 7 6 y 3 mod 6 3  collide on slot 3.
Mark 5 as visited. Dequeue 5 and enqueue it Occupies next slot which is slot 0.
non-visited adjacent nodes. Hence, the correct option are (A,B).
Queue :4 3 2 7 6 50. 94
Mark 4 as visited. Dequeue 4 and enqueue it Solve in bottom-up fashion.
non-visited adjacent nodes. Find me (0) = 1
Queue :3 2 7 6 y findme 1 findme 0  findme 0 2
Mark 3 as visited. Dequeue 3 and enqueue it
non-visited adjacent nodes. y findme 2 findme 1  findme 1 4
Queue: 2 7 6 y findme 3 findme 1  findme 2 6
Hence, the correct option is (A). y findme 4 findme 1  findme 3 10
48. 136
y findme 5 findme 2  findme 4 14
Given that,
y findme 6 findme 3  findme 5 20
arr[0] 1, arr[1] 4, arr[2] 10
arr[3] 12,and len 4 y findme 7 findme 3  findme 6 26
initially, the value of result = 0 y findme 8 findme 4  findme 7 36
y When y findme 9 findme 4  findme 8 46
i 0 | result result  arr[0]*
y findme 10 findme 5  findme 9 60
0 1 * 4  0 0  1*1*4 4
y findme 11 findme 5  findme 10 74
y When
i 1| result result  arr[1]* 1  1 y findme 12 findme 6  findme 11 94
* 4 1 4  4*2*3 28 Hence, the correct answer is 94.

26 Algorithm
 51. (C,D) ª n  1º
2n « 2 n 1 4 n .
17 Worst case complexity of quick sort occurs ¬ n »¼
in 2 cases, when smallest or largest element of Hence, the correct option is (B).
array is chosen as pivot element of array. So 54. 12.5
both the case of worst cases are avoided and
2 u 2000  2 u 300  1u 50 4650.
hence worst case can’t be O nš 2 . So, 5 notes in minimum Ÿ 5 u 2.5 12.5
Hence, the correct option are (C,D). Hence, the correct answer is 12.5.
52. (C) 55. (B)
The i loop iterates n / 2 : n times Only B option is true here.
j loop does call to foo(j). So, enumerating the The expected number of comparisons in a
calls to foo(j) we get successful linear search is > n / 2@ As the
foo 1  foo 2  foo 22  ...  foo 2lg n successful item is equally likely to be in any of
the n location.
Complexity of foo k 4 log k
In best case both linear search and binary
So, we get complexity of j loop as search can work in : log n comparisons as
4 lg1  4 lg 2  4 lg 22  ...  4 lg 2lg n after each search half the elements get
4 1  2  3  ...  lg n eliminated.
2
Hence, the correct option is (B).
4 lg n
56. 2
So, the time complexity of entire code
Arranging by the order of probability of
2
4 lg n . occurrences we get
Hence, the correct option is (C). y a : 0.33
y d : 0.3
53. (B)
y c : 0.2
The while loop is iterating lg n times as in each y b : 0.16
iteration n is halved. So times complexity will So, first we combine c and b nodes. Sum of their
be 4 lg n . probabilities will be 0.36.
There is only constant amount of space required Next, we combine the two smallest probabilities
in the function. So, space complexity is O 1 . which are for a and d. This will give sum as
0.63.
D value is incremented as
So, we get complete and full binary tree with 3
n  n / 2  n / 4  ...n / 2lg n levels and so all codes are of length 2. So,
n[1  1/ 2  1/ 4  ...1/ n] expected length of the binary codes will be 2.
ª¬1  1/ 2lg n º¼ Hence, the correct answer is 2.
n (Sum to n terms of GP
0.5 57. A,B,C,D
D 1  r n
with D  r 0.5 h x, i h1 x  i u h2 x mod m.
1 r

Algorithm 27
 13: h1 x 6.goes to slot 6 These two will give the total number of
multiplications as
18 : h1 x 4.goes to slot 4
>20 u 90 u10@  >20 u10 u15@ 
25: h1 x 4.goes to slot 4, collision
>20 u15 u 40@ 33000
h2 x 4, 2 u 4 mod 7 1  goes to slot1
And
11: h1 x 4.goes toslot 4, collision-
>20 u 90 u10@  >10 u15 u 40@ 
h2 x 2, 4 u 2 mod 7 6  collision
>20 u10 u 40@ 32000
4  2 u 2 mod 7 1 collision-
So, minimum number of multiplication required
4  3 u 2 mod 7 3  goes to slot 3. 32000.
20 : h1 x 6  goes to slot 6, collision- Hence, the correct answer is 32000.
h2 x 3, 6  3 mod 7 2  goes to slot 2. 60. (A)
29 : h1 x 1  goes to slot1 . Collision. Maximum subarray sum can be found in linear
Thus, 25,11,20,29 all collide. time using dynamic programming.
Hence, the correct option are (A,B,C,D). So, option A is TRUE.
58. (A,D) Hence, the correct option is (A).
A is TRUE. Happens for a left-skewed or right- 61. (C)
skewed binary tree. Given : Series
B is FALSE. Minimum number of comparisons
T (n) 1.21  2.22  3.23  4.24
to sort 5 elements is 7
ª n º 5.25  6.26  7.27  ...n.2n
C is FALSE. There can be at most « h1 » nodes Above series is bot A.P AND G.P series
¬2 ¼
of height h in any n element heap when h starts Convert it into G.P. series by method given
ª n º below
from 1 and this changes to « h1 » when h starts
¬2 ¼ 2.T (n) 1.22  2.23  3.24  4.25
from 0. 5.26  6.27  7.28  ...n.2n1
D is TRUE as maximum element in a min-heap T (n)  2.T (n) 1.21  (2 1).22 
will be at the last level and it can be any one of
(3  2).23  (4  3).24  ...  n.2n1
the possible n / 2 elements in the last level.
Hence, the correct option are (A,D). T (n) 21  22  23  24  25
59. 32000 26  27  ...  2n  n.2n1
By a quick look we can see that 90 is by far the Now we get the G.P series
largest dimension. So, we must do M1 u M 2 T (n) 2.((2n  1) / (2  1))  n.2n1
to get rid of this dimension. This means the only T (n) 2  n.2n1  2n1
orderings left are M1 u M 2 u M 3 u M 4 and T (n) O (n.2n )
M1 u M 2 u M 3 u M 4 . Hence, the correct option is (C).

28 Algorithm
 62. (B) 65. 2
for ( j 2 to array. length) This recurrence is same as LCS problem. In
key = array [j]; LCS we had “max” but here we have “min”.
i j  1; Time complexity of LCS is O(mn) .

While ( i ! 0 && array >i @ ! key ) Here it will be O(n2 ).a 2, b 0 .

Hence, the correct answer is 2.
array [i  1] array[i];
66. (A)
i i  1;
(This question aim to make you understand that
array [i  1] key;
top down is better if there are only few sub
above is the standard algorithm of insertion sort, problems to be computed)
from this we can easily infer that
Bottom-up approach will fill m u n matrix, and
(j ! 0) & & (arr[ j  1] ! value) is the right each sub problem will take T(1) so total time in
option. bottom up T(mn)
Hence, the correct option is (B).
The top-down approach will start with a
63. (A) function call A(n, n) and call sub problems
Only Option A is correct recursively. And will only call required sub
Option A: simple calculation or GCD 9,13 1 problems, not all sub problems.
Top-down method only calculates the needed
Option B: what if I take m 2 the code will run
sub problems, which are of the form
for n / 2  steps :(n); So, Option B is wrong.
§« m » « m »·
Option C: Given algorithm is doing GCD not A¨ « 6 » , « f » ¸ . There are only
LCM
© ¬2 ¼ ¬2 ¼¹
4(log m log n) such sub problems, hence its
Option D: space complexity is 0(1) for the given
algorithm time complexity is only 4(log m log n) .
Hence, the correct option is (A). Buttom-up method will require computing
every sub problem, resulting in time complexity
64. (B)
4(mn) .
Even to sort 10% of the elements insertion sort Hence, the correct option is (A).
in worst case can take 4(n2 ) comparisons.
67. (C)
Number of comparisons in insertion sort is
O(k), where k is the number of inversions in the
input array. A >i  1, j  1@
A >i  1, j  1@
For option C, consider the case where the
smallest element is at the end of the array for
A >i , j @
ascending sort. A >i , j  1@
This element will come to the correct position
only after 4(n 2 ) comparisons in bubble sort.
Hence, the correct option is (B). Hence, the correct option is (C).

Algorithm 29
 68. (D) Data:
Number of edges in G e 6
1. Control enters into the first while (i  n)
Number of vertices in G n
(condition is true)
Formula:
2. Control also enters into the inner while For a complete graph,
(i  n) loop. Degree of each vertex n  1
3. Control again enter into innermost while From handshaking Lemma
(i  n3 ) loop and then continues its 2 u 6 n u (n  1)
execution until iis equal to n3 . Then the Calculation:
control cannot go inside any of the while 2 u 6 n2  n
loop because all the 3 conditions will ? n2  n  12 0
result in false. (n  4) u (n  3) 0
Hence total iteration is n3 (inner most while) + ? n 4or n 3
1 (inner while) + 1 (outer most while)
Since n z 3
Hence time complexity O(n3 ) , ? n 4
Hence, the correct option is (D). For a minimum spanning tree,
69. 28 Number of edges needed 4  1 3
One of the minimum spanning tree will
Capacity = 20
defiantly be
Weights are (18,15,10)
1 o 3 o 9(13)
Profit values (25, 24, 15)
Other possible
Weight 18 15 10
Find Ÿ , , Graph: G
value 25 24 15
Ÿ 0.72, 0.625, 0.666
Select the item with highest ratio.
After selection of the 1st item, remaining
Capacity = 2 and value = 25
Now select 1/5 part of 3rd item, Weight for minimum spanning tree
Remaining capacity = 0
Total value =25+(15/5)=28 .
Hence, the correct answer is 28.
70. (A,C)
Concept : A minimum spanning tree (MST) or
minimum weight spanning tree is a subset of the Possible weight of a minimum spanning tree
edges (V  1) of a connected, edge-weighted 1  3  27 31
undirected graph G (V,E) that connects all the Only two MST is possible
vertices, without any cycles and with the Therefore option 1 and 3 are not possible
minimum possible total edge weight. Hence, the correct option are (A,C).

30 Algorithm
 71. (A) Ÿ L[ s] 1
For 0/1 knapsack problem, So basically use are Checking that what hen the
than minimum element. If so than mark 1 in L[j]
1. Each item either can be chosen (or)
.
cannot be chosen
2. Also, sum of the weights of the items in L 1 1 k a j 1 to an
the knapsack should be less than (or) 1 2 3 4 5 6
equal to W which is 6 1 2 3 4 5 6
Considering these two. Some of the possible a 5 2 4 8 3 40 a[ j ] 8
solutions which satisfy the above two
constraints.
j k
Set 1: items (l, 2, 3), total value 60
Set 2: items (4,2), total value 60 L 1 1

Set 3: items (4, 3), total value 55 1 2 3 4 5 6

Set 4: items (5,3), total value 65 min (3, 4 0) 3
Set 5: items (l, 2), total value 45 and a[ j ] t min a[ j  1], a[ j  2]..., a[n]
Set 7: items (l, 3), total value 40
So apply second case
Set 8: items (2,3), total value 35
i) a[4] ! a[5]
Out of these, clearly optimal solution is 65 and
only Set 4 has this max value. max 1
Hence, the correct option is (A). ii) a[4] ! a[5]
72. (B) So condition doesn’t work
1  max L[5] 2
a 5 2 4 8 3 40
1 2 3 4 5 6 2 1 1
L 1 2 3 4 5 6
1 2 3 4 5 6
Like this way before last step ;
a[ j ] d min a[ j  g ] a[n] a 5 2 4 8 3 40
1 2 3 4 5 6
Base Case :
L(6) 1 L 1 2 2 1 1
L 1 1 2 3 4 5 6
e) Now analyze for a[1]
a 5 2 4 8 3 40 k a j 1 to an
1 2 3 4 5 6 j k

j k a 5 2 4 8 3 40
min a[6] 40 1 2 3 4 5 6
a[ j ] 3 L 1 2 2 1 1
a[ j ] d min a[6] 1 2 3 4 5 6

Algorithm 31
 We can see But we only want the count of paths which can
a[1] ! min a [ j  1]...a [n] be possible only when we return 1 from the end
of any particular path & just take summation
5 ! 2, So apply second condition
over that 1’s which is what Option B is doing.
So apply second case :
Hence, the correct option is (B).
(i) a[1] ! a[2]
74. 1860
max 1
(ii) a[1] ! a[3] The number of scalar multiplications required
max 2 for multiplying matrices Amxn , Bnxp is m * n * p .
(iii) a[1]  a[4] Assuming we need to get least number of scalar
max 2 [Conditional able so max multiplications, we eliminate the larger
remains some] dimensions first.
(iv) a[1] ! a[5] Following are the 6 matrices and their
max 2 dimensions
(v) a[1]  a[6] A5u10 , B10u3 , C3u12 , D12u5 , E5u50 , F50u6
max 2 o 5 u10,10 u 3,3 u12,12 u 5,5 u 6
So, L[1] 1  max (Multiplying matrices
1 2 3 E5u50 , F50u6 ,50*5*6 1500 multiplications)
L 3 1 2 2 1 1
o 5 u10,10 u 3,3 u 5,5 u 6
So length of longest decreasing subsequence is (Multiplying matrices
3 C3u12 , D12u5 ,3*12*5 180 multiplications)
Another example :
o 5 u 3,3 u 5,5 u 6
a 1 2 3 4
(Multiplying matrices with dimensions
L 1 3 u 5,5 u 6,3*5*6 90 multiplications)
o 5u 6
o Here use can see everytime condition 1
will apply (Multiplying matrices with dimensions
So, 5 u 3,3 u 6 total 90 multiplications)
L 1 1 1 1 Total scalar multiplications = 1860
Hence, the correct answer is 1860.
So length of longest decreasing subsequence is
1. 75. (C)
Hence, the correct option is (B). 0 1 2 3 4 5 6

73. (B) 0 0 0 0 0 0 0 0
1 0 0 1 1 1 1 1 b
In the question we miss the point that we have
2 0 1 1 1 2 2 2 a
to count the number of paths from vi to vn, not
3 0 1 1 2 2 2 3 c
the count of nodes in that path.
Option C will return all nodes count in all the 4 0 0 2 2 2 3 3 b
a b c a b c
paths starting from i.

32 Algorithm
There are four longest common subsequences : Index 0 1 2 3 4 5 6
" bac " and " bab " and " bcb " and " acb " 0 5
Hence, the correct option is (C). So, f [1] is the maximum value with 1 coin.
76. (A) f [2] is the maximum value with 2
Given, coins:
OPT [1] 1 o We have two choices either taking c1 or
For OPT [2] we need to look at OPT [1] c2 . We can't take both coins due to the
For OPT [3] we need to look at OPT [1] and given constraint. So
OPT [2]. max( f [1], c2  f [0]) 5 . With two
For OPT[n] we need to look from OPT [1] to
coins maximum value is 5.
OPT > n  1@ .
Index 0 1 2 3 4 5 6
At first, for loop will run a single time, then two 0 5 5
times, …… then n  1 times. f [3] is the maximum value with 3
So the time complexity T (n) will be: coins:
o We have two choices either (taking
T (n) 1  2  3  4  ..........  (n  1)
f [2] which is the maximum value with
T (n) O(n2 )
2 coins) or ( c3  f [1] which is the
Space complexity will be O n because we are
maximum value with 1 coin). So
taking one extra array OPT which is a single- max( f [2], c3  f [1]) 7 .
dimensional array.
Index 0 1 2 3 4 5 6
Hence, the correct option is (A).
0 5 5 7
77. (A)
f [4] is the maximum value with 4
Option A– this is correct as this is satisfying the coins:
given constraint. For calculating f (n) which is o We have two choices either (taking
the maximum value with n coins we are either f [3] which is the maximum value with
taking (cn  f (n  2) or f (n  1)) . So we are 3 coins) or ( c4  f [2] which is the
making sure that we are not taking coins that lie maximum value with 2 coin). So,
beside each other.
max( f [3], c4  f [2]) 15 .
Option B, D – this is not correct as it is not
satisfying the given constraint “don't ever pick Index 0 1 2 3 4 5 6
up two coins that lie beside each other”. 0 5 5 7 15
Option C – this is not correct as it is not taking f [5] is the maximum value with 5
the value of the current coin. coins:
Row of coins with values
o We have two choices either (taking
f [4] which is the maximum value with
5 1 2 10 6 2
c1 c2 c3 c4 c5 c6 4 coins) or ( c5  f [3] which is the
Given, f (0) 0, f (1) 5 maximum value with 3 coin). So
max( f [4], c5  f [3]) 15 .
f [n] be maximum total value with n coins:

Algorithm 33
 Index 0 1 2 3 4 5 6 79. (B)
0 5 5 7 15 15
Level - 1 is compared with root – 2
f [6] is the maximum value with 6 comparisons.
coins: Level – 2 is compared with level – 1 elements –
o We have two choices either (taking 4 comparisons.
f [5] which is the maximum value with 2  4  8  ....  2k where, n 2k
5 coins) or ( c6  f [4] which is the Ÿ 2(1  2  ....  2k 1 )
maximum value with 4 coin).
Ÿ 2(2k  1) 2(n  1) 2n  2 O(n)
So, max( f [5], c6  f [4]) 17 .
Hence, the correct option is (B).
Index 0 1 2 3 4 5 6 80. (C)
0 5 5 7 15 15 17
§n·
So, maximum value with 6 coins is 17. T (n) 7T ¨ ¸  k ˜ n2
Hence, the correct option is (A). ©2¹
Using master theorem [nlog2 7 ! kn2 ]
78. (B)
T (n) O (nlog2 7 )
Code Explanation:
int i = 0, j = 0, val = 1 Hence, the correct option is (C).
for (i = 1; i < = n; i++)// n times Time 81. (A)
complexity O (n) Both dynamic and Greedy algorithm find
{ optimal substructure in the problem but only
j = n; dynamic programming uses the bottom-up
if (i % 2 = =0)// out of n only n/2 times if will approach, whereas greedy algorithm uses top-
run down approach. So, S1 is true so,
{ Hence, the correct option is (A).
while (j < 1) {// log n times, since j = n} 82. 8
val = val * j;
In the above graph, there are three stages with 2
j = j/2; // j decrease in power of 2 leads
vertices. Topological sort picks the element
to log n
with zero in degree at any point of time. At each
} of two vertices stages, either the top vertex or
} the bottom vertex can be processed. So at each
} of these stages there will be two possibilities.
Outer for loop O (n) Total number of possibilities 2 u 2 u 2 8
Inner for loop O (log n) Hence, the correct answer is 8.
Since nested loop 83. (B)
Time complexity Strassen matrix multiplication o Divide and
O (n) u O (log n) O (n log n) conquer
Hence, the correct option is (B). Insertion sort o Decrease and Conquer

34 Algorithm
Gaussian Elimination o Transform and 87. (D)
Conquer
In a connected graph, a vertex v is said to be an
Floyd shortest path algorithm o Dynamic
articulation point if by removing that vertex
programming
together with its edges the graph become
Hence, the correct option is (B).
disconnected. In the given graph there is no
84. (D) articulation point.
f (n) 2n d g (n) n! for n t 4 Hence, the correct option is (D).
f (n) O ( g (n)) 88. (C)
h (n) nlog n d f (n) 2n for n t 2 ªnº
There are « » number of leaf nodes. It requires
h(n) O ( f (n)) «2»
Hence, the correct option is (D). ªnº
85. (B) «« 2 »» 1 number of comparisons to find the
S (a0 , S1 ) maximum elements.
S1 (a1 , a2 , a3 ,.....an1 ) Hence, the correct option is (C).

Two possible cases arise : 89. (A)

1. a0 is included in the max weight T (n) T (n  1)  T (n  2)  T (n  3)

subsequence of S : Better way of solving is substitute
In this case, T (1) 1
Y T (2) 2
X = weight (a0 , S1 ) a0 
2 T (3) 3
2. a0 is not included in the max weight
T (4) T (3)  T (2)  T (1) 4
subsequence of S : T (5) T (4)  T (3)  T (2) 5
In this case, X weight (S1 ) Y
:
Since the value of a0 can be anything (negative :
Y T (n) T (n 1)  T (n  2)  T (n  3)
or  in general) { ai  } , it is possible that
2 n 1  n  2  n  3 n
Y
Y ! a0  . So order is O(n)
2 Hence, the correct option is (A).
The maximum possible weight of a subsequence
90. (A)
of S is given by
§ Y· Above code segment recurrence relation is
X max ¨ Y , a0  ¸ T (n) T (n  1)  c
© 2¹
Hence, the correct option is (B). T (n) T (n  1)  1
86. (B) T (0) 1
f ( x) grows exponentially as a function of x T (n  1) T (n  1  1)  1
Hence, the correct option is (B). T (n) [T (n  2)  1]  1 T (n  2)  2

Algorithm 35
 T (n  2) T (n  2  1)  1 log n
§n·
T (n) [(T (n  3)  1)  1]  1
R. T (n) ¦ ¨© 2 ¸¹
n 1

T (n  3)  3 n
u log 2 n O (n log n)
T ( n) T ( n  k )  k 2
Note: let k=n Assume n 2k
Then T (n) T (0)  n 1  n Ÿ log n k
? O(n)
k
§n·
n
¦¨© 2 ¸¹ 2
k
Hence, the correct option is (A). n 1

91. (C) Hence, the correct option is (C).

92. (A)
§n·
P. T (n) 3T ¨ ¸  O(n2 ) T (n) T (n / 5)  T (7n /10)  n
©4¹
n
a 3, b 4, f (n) cn2 log
5

From case 3 of Master Method. ¦ ˜n

i 0
4(n)

T (n) 4( f (n)) 4(n2 ) §n·

n ¨ ¸
§n· § 2n · © 10 ¹
Q. T (n) T ¨ ¸  T ¨ ¸  O(n)
© 3¹ © 3¹ Hence, the correct option is (A).
Use substitution with good guess 93. (A)
T (n) n log n
­n3 for 0 d n d 10,000
§n· § 2n · 1n n §n· Given : g1 (n) ® 2
T ¨ ¸ T ¨ ¸  log ¨ ¸  ¯ n for n t 10,000
©3¹ © 3¹ 3 3 ©3¹
­n for 0 d n d 100
2n § 2n · 1n g2 (n) ® 3
log ¨ ¸  ¯ n for n ! 100
3 © 3¹ 3
For n> 10,000,
n 2n
(log n  log3)  (log (2n)  log3) g1 (n) 0(n2 )
3 3
n g2 (n) 0(n3 )

3 We can conclude
n n 2n g1 (n) 0( g2 (n))
log n  log3  (log 2n)
3 3 3
Function g1 (n) is said to be Big-Oh of g2 (n) if
2n n
 log3  g1 (n) d cg3 (n) , for c ! 0 and
3 3
n 2n n n t n0
log n  (log 2  log n)  log3
3 3 3 n0 ! 0
2n n Hence, the correct option is (A).
 log3 
3 3
94. (D)
2n n
n log n   n log 3  n log n Max- heap using priority Queue
3 3

36 Algorithm
 96. 2.428
Average number of Comparison in Binary
search with n keys in array can be calculated by
a simple trick.
Make Almost complete BST, compute level
Insert 1 and 7 wise comparisons for example, at level 1, one
Adjust comparison on each element, at level 2, 2
10 10
comparisons on each element. At level 3, 3
8 5 8 7 comparisons on each element and so on.
Then Calculate Average by
3 2 1 7 3 2 1 5
Total number of Comparisons
Hence, the correct option is (D).
Number of Elements
95. 2.12 Example:-
a b c d e f Level 1
5 9 12 13 16 55
Level 2
30

14 25 Level 3

e Average number of comparisons

16 1u1  2 u 2  3 u 4 1  4  12
a b c d 2.428
5 9 12 13 7 7
0 110 Hence, the correct answer is 2.428.
55 1
0
0
30 1 97. 270
25
1 f
1
14 First we draw table
0 55
1
c
0 c Item Wi Vi
d 16
12 13 a b
I1 5 30
Huffman Tree.
a 0100 (4 bit) I2 10 20
b 0101 (4 bit) I3 20 100
c 000 (3 bit) 30 90
I4
d 001 (3 bit)
e 011 (3 bit) I5 40 160
f 1 (1 bit) Taking value per weight ratio i.e., Pi Vi / Wi
Average length
5 u 4  9 u 4  12 u 3  13 u 3  16 u 3  55 u1 Item Wi Vi Vi
Pi
110 Wi
2.12 I1 5 30 6
Hence, the correct answer is 2.12.

Algorithm 37
 I2 10 20 2 i- is the outer loop & j–is the inner loop so the
20 100 5 total time complexity is O(n log 2 n)
I3
Hence, the correct option is (D).
I4 30 90 3
™™™™
I5 40 160 4

o Now arrange the value Pi in decreasing order

Item Wi Vi Pi
I1 5 30 6
I3 20 100 5
I5 40 160 4
I4 30 90 3
I2 10 20 2

I1 7 I5
I3
8
W 60 55 35 0
We have remaining W is 35 but I 5 required 40
35 7
so we get only u I5 I5
40 8
So the maximum profit or a value is
7
30  100  u160
8
30  100  140 270
98. (D)

ª n
n º
i loops are execute «¬1to 2 times »¼
2
times

But j 1oop are executes log n time

Because j 1, 2, 4,8,     2K
Until 2K d n
So the maximum value of K is 2K n
Apply log 2 on both side
log2 2K log2 n
K.log22 log2 n
K log 2 n

38 Algorithm