Algorithm Questions (Ddpanda)
Algorithm Questions (Ddpanda)
You are given a list of positive integers along with a sequence of operations from the set {∗, +}
.You construct expressions from these two lists so that:
The numbers in the expression are drawn from the first list, without repetition and without
altering their order.
All the operators in the second list are used in the expression, in the same order.
For example, if the two lists are [1, 3, 2, 1, 4] and [' ∗ ', ' + '] the set of possible expressions you
can form are
1 ∗ 3 + 2, 1 ∗ 3 + 1, 1 ∗ 3 + 4, 1 ∗ 2 + 1, 1 ∗ 2 + 4, … , 2 ∗ 1 + 4, 1 ∗ 3 + 2, 1 ∗ 3 + 1, 1 ∗ 3 + 4, 1 ∗
For each expression, the value is computed by bracketing operators from the right. That is, the
expressions above are evaluated as
Answer
Let A be an array of n integers, sorted, so that A[1] ≤ A[2] ≤ … A[n]. Suppose you are given a
number x and you wish to find out if there are indices k and l such that A[k] + A[l] = x .
Answer
Let A be an array of n integers, sorted so that A[1] ≤ A[2] ≤ … A[n]. Suppose you are given a
number x and you wish to find out if there exist indices k and l such that A[k] + A[l] = x .
Answer
Let T be a Depth First Tree of a undirected graph G. An array P indexed by the vertices of G is
given. P[V ] is the parent of vertex V , in T . Parent of the root is the root itself.
Give a method for finding and printing the cycle formed if the edge (u, v) of G not in T (i.e.,
e ∈ G − T ) is now added to T .
Time taken by your method must be proportional to the length of the cycle.
Describe the algorithm in a PASCAL (C) – like language. Assume that the variables have been
suitably declared.
gate1992 algorithms descriptive algorithm-design
Answer
An element in an array X is called a leader if it is greater than all elements to the right of it in X.
The best algorithm to find all leaders in an array
Answer
Given two arrays of numbers a1 , . . . , an and b1 , . . . , bn where each number is 0 or 1, the fastest
algorithm to find the largest span (i, j) such that ai + ai+1 + ⋯ + aj = bi + bi+1 + ⋯ + bj or
report that there is not such span,
Answer
You are given two strings S and T , each of length α, consisting only of lower case English letters
(a, b, … , z). Propose an O(α)-time algorithm to decide whether S can be obtained by permuting
the symbols of T . For example, if S = algorithm, T = logarithm, your algorithm should
return Y ES ; but if S = trainee, T = retinaa, your algorithm should return NO.
descriptive isi2015 algorithms algorithm-design
Answer
You are given ten rings numbered from 1 to 10, and three pegs labeled A, B, and C . Initially all the
rings are on peg A, arranged from top to bottom in ascending order of their numbers. The goal is to
move all the rings to peg B in the minimum number of moves obeying the following constraints:
A. 501
B. 1023
C. 2011
D. 10079
E. None of the above.
Answer
Selected Answer
Suppose the first list has m numbers and the second list has n operators, here (m > n).
So, at each expression we will have (n + 1) numbers.
Note that maximum value of the expression occurs when (n + 1) maximum numbers out of m
numbers in the first list will be present in the expression.
So, our goal is to find (n + 1) maximum numbers out of m numbers in the first list.
Now, finding the maximum number out of m numbers in the first list can be done in O(n) time.
Build a max heap and extract the root node. Building a max heap takes O(n) time.
Now, the remaining n maximum numbers can be determined in O(logn) time. (Call max-heapify
on the max-heap and delete the root node).
Selected Answer
Selected Answer
Here is the algorithm, which returns True if there is a number x present such that (
A[k] + A[l] == x ) else returns False.
// Consider this algorithm is called as
// AlgorithmCheck(A,1,size,x);
// Where A is the sorted array
Selected Answer
Ref: [Link]
Selected Answer
Option B) We can move from right to left, while keeping a note of the maximum element so far
(let's call it current_max).
Starting from the rightmost element, we initialize our current_max with it, since the rightmost
element will always be a leader.
Moving from right to left, if an element x is greater than our current_max, then x is also a
leader. Add this element to list of leaders (or simply print it). Set current_max to x and carry-
on leftward.
Selected Answer
Since array is binary, the max sum will go until n and so the sum difference of the two arrays can
vary between −n and n. We use array start to keep the starting index of each possible sum
(hence of size 2n + 1) and array end to keep the ending index (these two arrays work like hash
tables and since we have only 2n + 1 possible keys, we can do a perfect hashing). So, our
required solution will be max(end[i] − start[i]) provided both are assigned values.
1. Initialize diff array to contain the difference of sum of elements of array a and b. i.e.,
diff[i] = ∑ni=0 a[i] − b[i] .
2. Now diff[i] can have values from −n to n which gives 2n + 1 possible values and the first
occurrence of a diff value marks the beginning of a span and the last occurrence marks the
end. We use start and end array for storing these two positions for the 2n + 1 possible
values.
3. Now, the largest value of end[i] − start[i] for any i, will be the largest span and the start of it
will be start[i] + 1, and end will be end[i]. If the span is starting from first position itself
(arrays a and b have same first elements), then it will start from start[i] itself.
#include <stdio.h>
#define size 100 //assume n is less than 100
int main()
{
int n, a[size], b[size];
int start[2*size+1], end[2*size+1];
int sum1 = 0, sum2 = 0, i;
int diff[size];
printf("Enter n: ");
scanf("%d", &n);
for(i = 0; i < n; i++)
{
printf("Enter a[%d]: ", i);
scanf("%d", &a[i]);
}
Selected Answer
1) Take an array of 26 elements where 'a' corresponds to index 0,....,z corresponds to index 25,
initially initialized to all 0s
2) For the first string, increment the corresponding positions of the array by 1 corresponding to
every character as the string is traversed.
3) For the second string, decrement the corresponding positions of the array by 1 corresponding to
every character as the string is traversed.
4) If all the elements of the array are 0 finally, then output YES, else NO.
0 votes -- Prasita Mukherjee (429 points)
Selected Answer
[Link]
Answer
Answer
Answer
Given below are some algorithms, and some algorithm design paradigms.
i. Divide and
1. Dijkstra's Shortest Path
Conquer
ii. Dynamic
2. Floyd-Warshall algorithm to compute all pairs shortest path
Programming
3. Binary search on a sorted array iii. Greedy design
iv. Depth-first
4. Backtracking search on a graph
search
v. Breadth-first
search
Match the above algorithms on the left to the corresponding design paradigm they follow.
Answer
Match the algorithms to the design paradigms they are based on.
Answer
[Link]
Selected Answer
Selected Answer
[Link]
[Link]
[Link]
[Link]
Selected Answer
Option is C.
Answer: C
In Kruskal, in every iteration, an edge of the most minimum weight (greediest) possible is
selected and added to MST construction. Hence, greedy.
In Quick Sort, we partition the problem into subproblems, solve them and then combine. Hence, it
is Divide & Conquer.
g2 (n) = {
n for 0 ≤ n ≤ 100
n3 for n > 100
Which of the following is true?
Answer
log n
A. 100n log n = O( n 100 )
−−−−
B. √log n = O(log log n)
C. If 0 < x < y then nx = O (ny )
D. 2n ≠ O (nk)
Answer
Answer
f(n) = 3n√n
g(n) = 2√nlog2 n
h(n) = n!
Which of the following is true?
A. h(n) is O(f(n))
B. h(n) is O(g(n))
C. g(n) is not O(f(n))
D. f(n) is O(g(n))
Answer
Let f(n) = n2 log n and g(n) = n(log n)10 be two positive functions of n. Which of the following
statements is correct?
Answer
A. I and II
B. I and III
C. II and III
D. I, II, and III
Answer
Letf(n), g(n) and h(n) be functions defined for positive integers 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?
Answer
A. T (n) = O(n2 )
T (n) = Θ(n log n)
© Copyright GATE Overflow. All rights reserved.
18 1 Algorithms (323)
Answer
f(n) = 2n
g(n) = n!
h(n) = nlog n
Which of the following statements about the asymptotic behavior of f(n), g(n) and h(n) is true?
A. f (n) = O (g (n)) ; g (n) = O (h (n))
B. f (n) = Ω (g (n)) ; g(n) = O (h (n))
C. g (n) = O (f (n)) ; h (n) = O (f (n))
D. h (n) = O (f (n)) ; g (n) = Ω (f (n))
Answer
A. n1/3
B. en
C. n7/4
D. n log9 n
E. 1.0000001n
A. a, d, c, e, b
B. d, a, c, e, b
C. a, c, d, e, b
D. a, c, d, b, e
Answer
Which of the given options provides the increasing order of asymptotic complexity of functions
f1 , f2 , f3
and f4 ?
f1 (n) = 2n
f2 (n) = n3/2
f3 (n) = n log2 n
f4 (n) = nlog2 n
f3 , f2 , f4 , f1
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 19
A. f3 , f2 , f4 , f1
B. f3 , f2 , f1 , f4
C. f2 , f3 , f1 , f4
D. f2 , f3 , f4 , f1
Answer
L e t W(n) and A(n) denote respectively, the worst case and average case running time of an
algorithm executed on an input of size n. Which of the following is ALWAYS TRUE?
A. A(n) = Ω(W(n))
B. A(n) = Θ(W(n))
C. A(n) = O(W(n))
D. A(n) = o(W(n))
Answer
n
Consider the equality ∑i3 = X and the following choices for X:
i=0
I. Θ(n4 )
II. Θ(n5 )
III. O(n5 )
IV. Ω(n3 )
The equality above remains correct if X is replaced by
A. Only I
B. Only II
C. I or III or IV but not II
D. II or III or IV but not I
Answer
L e t f(n) = n and g(n) = n(1+sin n) , where n is a positive integer. Which of the following
statements is/are correct?
I. f(n) = O(g(n))
II. f(n) = Ω(g(n))
A. Only I
B. Only II
C. Both I and II
D. Neither I nor II
Answer
10, √−
n , n, log2 n, 100
n .
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:
log2 n, 100 −
n , 10, √n , n
A.
100 −
n , 10, log2 n , √n , n
B.
10, 100 −
n , √n , log2 n , n
C.
100 −
n , log2 n , 10, √n , n
D.
Answer
tifr2011 asymptotic-notations
Answer
Answer
Answer
tifr2016 asymptotic-notations
Answer
Which of the following functions asymptotically grows the fastest as n goes to infinity?
Answer
Which of the following statements is TRUE for all sufficiently large integers n ?
√loglogn
A. 22 < 2√logn < n
√loglogn
B. 2√logn < n < 22
√loglogn
C. n < 2√logn < 22
√loglogn
D. n < 22 < 2√logn
√loglogn
E. 2√logn < 22 <n
tifr2018 asymptotic-notations
Answer
Which of the following functions, given by there recurrence, grows the fastest asymptotically ?
A. T(n) = 4T( n
2 ) + 10n
B. T(n) = 8T( 3 ) + 24n2
n
2
C. T(n) = 16T( n
4 ) + 10n
1.99
5 ) + 20(nlogn)
D. T(n) = 25T( n
E. They all are asymptotically the same
Answer
Selected Answer
For asymptotic complexity, we assume sufficiently large n. So, g1 (n) = n2 and g2 (n) = n3 .
Growth rate of g1 is less than that of g2 , i.e., g1 (n) = O(g2 (n)).
Selected Answer
log n
A. 100n log n = O( n 100 ) : Big-O denotes the growth rate of functions and multiplication or
division by a constant does not change the growth rate. So, this is TRUE and here O can even
be replaced by Θ or Ω.
−−−−
B. √log n = O(log log n) : FALSE. Take any long value like 256. LHS results in 16 but RHS
results in 4 only . Generally we take log on the left side but that is wrong.
C. 0 < x < y then nx = O (ny ) : TRUE since y is always greater than x. So, RHS is always
greater than LHS.
D. 2n ≠ O (nk) : TRUE since k is constant. So, for large values of n, LHS is much higher than
RHS (exponential function always greater than linear).
Only
B is FALSE.
Selected Answer
n(n+1)
(M) T (n) = Sum of first n natural numbers = 2 = O(n2 )
(f(n) = n = Ω (nlogb a+ϵ ) = Ω (nlog2 1+ϵ ) = Ω (n0+ϵ ) , satisfied for any positive ϵ ≤ 1. Also,
af ( nb ) < cf(n) ⟹ f ( n2 ) < cf(n) ⟹ n2 < cn , satisfied for any c between 0 and 0.5)
(O) T (n) = Θ(n log n) = O(n log n), third case of Master theorem
(f(n) = n log n = Ω (nlogb a+ϵ ) = Ω (nlog2 1+ϵ ) = Ω (n0.5+ϵ ) , satisfied for positive ϵ = 0.5.
Also, af ( nb ) < cf(n) ⟹ f ( n 2 ) < cf(n) ⟹ 2 log 2 < cn log n , satisfied for c = 0.5)
n n
(P) Like in (M), here we are adding the log of the first n natural numbers. So,
Selected Answer
n = 256 n = 65536
3 × 65536256
16
3 × 256
f(n) = 3n√n = 3 × 216×256
128
=3×2
= 3 × 24096
216×8 2256×16
g(n) = 2√nlog2 n
= 2128 = 24096
256! 65536!
256 65536
h(n) = n! = O ((28 ) ) = O ((216 ) )
= O (22048 ) = O (21M )
Case of h(n) is given only by an upper bound but factorial has higher growth rate than
exponential.
[Link]
exponential-functions
f(n) and g(n) are having same order of growth as f(n) is simply 3 × g(n) (we can prove this by
taking log also). So, (d) is correct and all other choices are false.
Selected Answer
f(n) = n2 log n
g(n) = n(log n)10
We can use the limit definition of O-notation
[Link]
f(n)
lim = 0, ⟹ f(n) = o(g(n))
n→∞ g(n)
small o implying f is strictly asymptotically lower than g. Also by definition,
o ⟹ O but O / ⟹ o.
f(n)
lim = c, c > 0 ⟹ f(n) = Θ(g(n))
n→∞ g(n)
f(n)
lim = ∞, ⟹ f(n) = ω(g(n))
n→∞ g(n)
small ω implying f is strictly asymptotically higher than g. Also by definition,
ω ⟹ Ω, but Ω / ⟹ ω.
We can use this to prove the above question
k ∗ (log n)k−1
= lim
n→∞ n
k!
= lim =0
n→∞ n
10 2
n(log n = O( log n)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 25
f(n) g(n)
10 10 10 10 10
n=2 10 ∗ 2 ∗ 2 2 ∗ 10
n = 2256 256 ∗ 2256 ∗ 2256 2256 ∗ 25610
So, as n is going larger, f(n) is overtaking g(n) and the growth rate of f is faster than that of g.
So, g(n) = O(f(n)) and f(n) ≠ O(g(n)).
B choice.
Selected Answer
I. Rate of growth of (n + k)m is same as that of (nm ) as k and m are constants. (If either k or m
is a variable then the equality does not hold), i.e., for sufficiently large values of n,
As 2n+1 is both upper and lower bounded by 2n we can say 2n+1 = O (2n ) . (Θ implies both O
as well as Ω)
So, TRUE.
22n = 2n 2 = 2n × 2n
2n is upper bounded by (2n )2 , not the other way round as 22n is increasing by a factor of 2n
which is not a constant.
So, FALSE.
Answer is
(D).
We can verify as : f⩽g but g f . Therefore,
f < g.
Also,
g = h, as g = O(h) and h = O(g).
Selected Answer
Selected Answer
g(n) = n!.
On expanding the factorial we get g(n) = O(nn ) :
nn > nlog n
nn > 2n
This condition is violated by options A, B and C by first statements of each. Hence, they cannot
be said to be TRUE.
Selected Answer
In C we have a term n3/4 and correspondingly in D we have log9 n (after taking n out).
n3/4 is asymptotically larger than log9 n as when n = 10100 , log9 n gives 1009 , while n3/4 gives
1075 > 10037 a much higher value and this is true for all higher values of n. So, D < C.
Thus, A is correct.
28 votes -- Arjun Suresh (350k points)
Selected Answer
Answer is (A).
n log2 n < n3/2 is quite straightforward as n3/2 = n × n1/2 and log n < n1/2 as logarithmic
growth is smaller than exponential growth however small be the exponentiation factor.
Selected Answer
Worst case complexity can never be lower than the average case complexity, but it can be higher.
So, (C) is the answer.
A(n) = O(W(n)).
31 votes -- Arjun Suresh (350k points)
Selected Answer
Sum of the cubes of the first n natural numbers is given by (n(n + 1)/2)2 which is Θ(n4 ). So, I,
III and IV are correct. II is wrong.
∴ (C) is correct.
Selected Answer
Selected Answer
log2 n : Growth rate is logarithmic. For asymptotic growth, the base does not matter.
100
n : Growth rate decreases with n.
10−
,Constant
√ ,Square root
n
n, polynomial
log2 n, Logorithmic
100
n . Constant division by polynomial (clearly less than constant for every value of n
>100)
Now we know Constant division by polynomial < Constant < Logorithmic <Square
root < polynomial
Selected Answer
Since exponentials grow faster than polynomials, h(n) > g(n) for large n.
x
Since linear functions grow faster than square roots, 100 > √−
x for large x. Thus, h(n) > f(n)
for large n.
(D)
© Copyright GATE Overflow. All rights reserved.
30 1 Algorithms (323)
(D) is correct.
Selected Answer
Take n = 21024
Selected Answer
b. en−0.9 ln n = e (n − 0.9 ln n)
n
c. 2n = (e ln 2 ) = e (n ln 2)
n−1
d. (ln n)n−1 = (e ln ln n ) = e (n ln ln n − ln ln n)
Now, if we just compare the exponents of all, we can clearly see that (n ln ln n − ln ln n) grows
(C)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 31
faster than the rest. Note that in option (C), the multiplicative ln 2 is a constant, and hence grows
slower than the multiplicative ln ln n from option (D).
This implies that e (n ln ln n − ln ln n) grows the fastest, and hence, (ln n)n−1 grows the fastest.
Thus, option
(D) is the correct answer.
log n/ log
m n = m!
log n
4 24 4/2 = 2
6 720 9/3 = 3
8 720 ∗ 56 15/3 = 5
720 ∗ 56 21/4 = 5
10
∗ 90
If we see, m is growing at same rate as log n/ log log n.
Selected Answer
Let N = 2256
A. (log log N)! = 8!
B. (log log N )log N = (8)256 = 2768
C. (log log N )log log log N = 83 = 512
D. (log N )log log N = (256)8 = 264
E. 2√log log N = 22√2
Let N = 216
A. (log log N)! = 4!
B. (log log N )log N = (4)16 = 232
C. (log log N )log log log N = 42 = 16
D. (log N )log log N = (16)4 = 216
E. 2√log log N = 22 = 4
Taking ratio for both N values,
Option B = (log log N)log N asymptotically grows the fastest, as for the same change in N , the
value increased the most (growth) for option B and this growth is monotonic (continuous).
n = 22
k
Take
(A) gives n = 22
k
Now, option
√log22k √2k
Option (B) gives 2 =2
√log(log22k ) √k
Option (C) gives 22 = 22
Now, check power only for (B) and (C).
Take log of power of both functions, i.e.,
−−
(log(2√k ) = O(log(√2k )
−
√k = O( k2 )
Selected Answer
Answer
Which entry of the array X, if TRUE, implies that there is a subset whose elements sum to W ?
A. X[1, W]
B. X[n, 0]
C. X[n, W]
D. X[n − 1, n]
Answer
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none
or all) left out. We are given two sequences X[m] and Y [n] of lengths m and n, respectively with
indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y [n] as
l(m, n), where an incomplete recursive definition for the function I(i, j) to compute the length of
the LCS of X[m] and Y [n] is given below:
l(i,j) = 0, if either i = 0 or j = 0
= expr1, if i,j > 0 and X[i-1] = Y[j-1]
= expr2, if i,j > 0 and X[i-1] ≠ Y[j-1]
A. expr1 = l (i − 1, j) + 1
B. expr1 = l (i, j − 1)
C. expr2 = max (l (i − 1, j) , l (i, j − 1))
expr2 = max (l (i − 1, j − 1) , l (i, j))
© Copyright GATE Overflow. All rights reserved.
34 1 Algorithms (323)
Answer
A sub-sequence of a given sequence is just the given sequence with some elements (possibly none
or all) left out. We are given two sequences X[m] and Y [n] of lengths m and n, respectively with
indexes of X and Y starting from 0.
We wish to find the length of the longest common sub-sequence (LCS) of X[m] and Y [n] as
l(m, n), where an incomplete recursive definition for the function I(i, j) to compute the length of
the LCS of X[m] and Y [n] is given below:
l(i, j) = 0, if either i = 0 or j = 0
= expr1, if i, j > 0 and X[i − 1] = Y [j − 1]
= expr2, if i, j > 0 and X[i − 1] ≠ Y [j − 1]
The value of l(i, j) could be obtained by dynamic programming based on the correct recursive
definition of l(i, j) of the form given above, using an array L[M, N], where M = m + 1 and
N = n + 1 , such that L[i, j] = l(i, j).
Which one of the following statements would be TRUE regarding the dynamic programming solution
for the recursive definition of l(i, j)?
A. All elements of L should be initialized to 0 for the values of l(i, j) to be properly computed.
B. The values of l(i, j) may be computed in a row major order or column major order of L[M, N].
C. The values of l(i, j) cannot be computed in either row major order or column major order of
L[M, N].
D. L[p, q] needs to be computed before L[r, s] if either p < r or q < s.
Answer
A. max(Y , a0 + Y )
B. max(Y , a0 + Y /2)
C. max(Y , a0 + 2Y )
D. a0 + Y /2
Answer
An algorithm to find the length of the longest monotonically increasing sequence of numbers in an
A[0 : n − 1]
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 35
Initialize Ln−1 = 1.
For all i such that 0 ≤ i ≤ n − 2
Li = {
1 + Li+1 if A[i] < A[i+1]
1 Otherwise
Finally, the length of the longest monotonically increasing sequence is max (L0 , L1 , … , Ln−1 ).
Which of the following statements is TRUE?
Answer
If p = 10, q = 100, r = 20, s = 5 and t = 80, then the minimum number of scalar multiplications
needed is
A. 248000
B. 44000
C. 19000
D. 25000
gate2011 algorithms dynamic-programming normal
Answer
Consider two strings A="qpqrr" and B="pqprqrp". Let x be the length of the longest common
subsequence (not necessarily contiguous) between A and B and let y be the number of such
longest common subsequences between A and B. Then x + 10y = ___.
Answer
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right
by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers
i, j with i < j . Given a shortcut (i, j), if you are at position i on the number line, you may directly
move to j. Suppose T (k) denotes the smallest number of steps needed to move from k to 100.
Suppose further that there is at most 1 shortcut involving any number, and in particular, from 9
there is a shortcut to 15. Let y and z be such that T (9) = 1 + min(T (y), T (z)). Then the value of
the product yz is _____.
Answer
A. Greedy paradigm.
B. Divide-and-conquer paradigm.
C. Dynamic Programming paradigm.
D. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.
Answer
Answer
A. F1 F2 and F3 F4 only
B. F2 F3 only
C. F3 F4 only
D. F2 F2 and F4 F5 only
Answer
Selected Answer
Case (2): Or we do not consider the item(in this case the element ai ) in which case we only
consider the solution to previous subproblem, which is,
A[i − 1][J]
Since the whole solution to this subset-sum problem is Logical OR(+) of cases 1 and 2, we
eliminate options C and D because both are considering the Logical AND of the two parts of the
solution.
Now, since here in the given question we are given a boolean array X[n][W + 1]
So, an entry X[i][j] is true only if sum j is possible with array elements from 0 to i.
So, for Each element of array, ai , we consider two possibilites:
(1) EIther we can ignore it and still get our possible sum, which is,
X[i − 1][j]
OR
(2) We could include element ai and then get our required sum, which is,
X[i − 1][j − ai ]
And finally, to get X[i][j], we take logical or of the above two cases.
Hence, answer is option B.
Reference :
Video:
By using the analogy of the problem and solution between subset-sum problem and 0/1 knapsack
problem, the above video clearly explains the how the solution to the problem is structured .
Video:
Selected Answer
ANSWER is C.
If LAST ROW and LAST COLUMN entry is 1, then there exists a subset whose elements sum to W .
Selected Answer
Answer is C. When the currently compared elements doesn't match, we have two possibilities for
the LCS, one including X[i] but not Y[j] and other including Y[j] but not X[i].
Selected Answer
Answer is B. Dynamic programming is used to save the previously found LCS. So, for any index
[p,q] all smaller ones should have been computed earlier. Option D is not correct as the condition
given requires even L[3,2] to be computed before L[2,4] which is not a necessity if we follow row-
major order.
else
L[i][j] = max(L[i-1][j], L[i][j-1]);
}
}
Selected Answer
S = ⟨a0 , S1 ⟩
S1 = ⟨a1 , a2 , a3 … an−1 ⟩
Two possible cases arise:
X = max (Y , a0 + )
Y
2
Thus, option B is correct.
Selected Answer
[Link]
Now, branch and bound comes when we explore all possible solutions (branch) and we
backtrack as soon as we realise we won't get a solution (in classical backtracking we will retreat
only when we won't find the solution). In backtracking : In each step, you check if this step
satisfies all the conditions.
If it does : you continue generating subsequent solutions
If not : you go one step backward to check for another path
So, backtracking gives all possible solutions while branch and bound will give only the optimal
one. [Link]
The given algorithm here is neither backtracking nor branch and bound. Because we are not
branching anywhere in the solution space.
And the algorithm is not divide and conquer as we are not dividing the problem and then merging
the solution as in the case of merge sort (where merge is the conquer step).
[Link]
Selected Answer
Answer is C.
No. of possible ordering for 4 matrices is C3 where C3 is the 3rd Catalan number and given by
1 2n
n = 3 in n+1 Cn = 5.
So, here we have
1. (M1 × M2 ) × (M3 × M4 )
2. (M1 × (M2 × M3 )) × M4
3. ((M1 × M2 ) × M3 ) × M4
1 ×( 2 ×( 3 × 4 ))
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 41
4. M1 × (M2 × (M3 × M4 ))
5. M1 × ((M2 × M3 ) × M4 ))
Each of these would give no. of multiplications required as
0 if i = j
m[i, j] = {
mini≤k<j m[i]k] + m[k + 1][j] + pi−1 pj pk if i < j
So, we can fill the following table starting with the diagonals and moving upward diagonally. Here
k < j but ≥ i.
j=1 j=2 j=3
Selected Answer
Answer is 34.
In first string, if we want to get 4 as maximum length then LCS should end with either "rr" or "qr".
Only 4 combinations are possible for LCS with length 4:
"qpqr"
"qqrr"
"pqrr"
"qprr"
Now, check for matching sequences in second string, except for "qqrr" all are possible.
Selected Answer
One number that can be reached from 9 is 10, which is the number obtained if we simply move
one position right on the number line. Another number is 15, the shortcut path from 9, as given in
the question. So, we have two paths from 9, one is 10 and the other is 15.
Therefore, the value of y and z is 10 and 15 (either variable may take either of the values).
Thus, yz = 150.
17 votes -- Divya Bharti (8.1k points)
Hence ,y = 10 , z = 15
yz = 10 × 15 = 150
31 votes -- Srinath Jayachandran (3.7k points)
Selected Answer
In Floyd Warshall's, we calculate all possibilities and select best one so its neither Divide & Conquer
nor Greedy but based on Dynamic Programming Paradigm.
Selected Answer
Answer is 1500.
A1 A2 A3 A4
20
10 × 5 5 × 20 10 × 5
× 10
A12 = 10 × 5 × 20 = 1000
A23 = 5 × 20 × 10 = 1000
A34 = 20 × 10 × 5 = 1000
A12 + A33 + 5 × 20 × 10 = 2000
A13 = min {
A11 + A23 + 10 × 5 × 10 = 1500
A23 + A44 + 5 × 10 × 5 = 1250
A24 = min {
A22 + A34 + 5 × 20 × 5 = 1500
⎧
⎪ A11 + A24 + 10 × 5 × 5 = 1500
A14 = min ⎨ A12 + A34 + 10 × 20 × 5 ⩾ 2000
⎩
⎪
A13 + A44 + 10 × 20 × 5 = 2000
Answer is 1500.
Selected Answer
If we multiply anything with F5 we will get much greater multiplication cost because F5 is
1 ∗ 1000 matrix so 1000 will play vital role in cost. So we will multiply F5 at very last step.
So, here is the sequence giving minimal cost:
A. Optimal binary search tree construction can be performed efficiently using dynamic programming
C. Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely
constructed.
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:
Answer
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
Answer
Which one of the following algorithm design techniques is used in finding all pairs of shortest
distances in a graph?
A. Dynamic programming
B. Backtracking
C. Greedy
Answer
is:
A. X - 1, Y - 2, Z-3
B. X - 3, Y - 1, Z-2
C. X - 3, Y - 2, Z-1
D. X - 2, Y - 3, Z-1
gate2000 algorithms easy graph-algorithms
Answer
Answer
Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths
in a directed graph G with n ∗ n adjacency matrix A. A[i, j] equals 1 if there is an edge in G from
i to j, and 0 otherwise. Your aim in filling in the blanks is to ensure that the algorithm is correct.
INITIALIZATION: For i = 1 ... n
{For j = 1 ... n
{ if a[i,j] = 0 then P[i,j] =_______ else P[i,j] =_______;}
}
a. Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
b. Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
c. Fill in the blank: The running time of the Algorithm is O(___).
Answer
I. abeghf
II. abfehg
III. abfhge
IV. afghbe
A. I, II and IV only
B. I and IV only
C. II, III and IV only
D. I, III and IV only
Answer
w(e) = {
0, if e ∈ E1
1, otherwise
A single-source shortest path algorithm is executed on the weighted graph (V , E, w) with an
arbitrary vertex v1 of V1 as the source. Which of the following can always be inferred from the path
costs computed?
C. V1 forms a clique in G
D. G1 is a tree
Answer
A[j, k] = {
1, if (j, k) ∈ E
0, otherwise
Consider the following algorithm:
for i=1 to n
for j=1 to n
for k=1 to n
A[j,k] = max(A[j,k], A[j,i] + A[i,k]);
Which of the following statements is necessarily true for all j and k after termination of the above
algorithm?
A. A[j, k] ≤ n
B. If A[j, j] ≥ n − 1 then G has a Hamiltonian cycle
C. If there exists a path from j to k, A[j, k] contains the longest path length from j to k
D. If there exists a path from j to k, every simple path from j to k contains at most A[j, k] edges
Answer
Suppose we run Dijkstra’s single source shortest-path algorithm on the following edge-weighted
directed graph with vertex P as the source.
In what order do the nodes get included into the set of vertices for which the shortest path distances
are finalized?
A. P, Q, R, S, T , U
B. P, Q, R, U, S, T
C. P, Q, R, U, T , S
D. P, Q, T , R, U, S
gate2004 algorithms graph-algorithms normal
Answer
Let G1 = (V , E1 ) and G2 = (V , E2 ) be connected graphs on the same vertex set V with more
than two vertices. If G1 ∩ G2 = (V , E1 ∩ E2 ) is not a connected graph, then the graph
G1 ∪ G2 = (V , E1 ∪ E2 )
A. cannot have a cut vertex
B. must have a cycle
C. must have a cut-edge (bridge)
D. has chromatic number strictly greater than those of G1 and G2
gate2004 algorithms graph-algorithms normal
Answer
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)
Answer
Let G(V , E) be an undirected graph with positive edge weights. Dijkstra’s single source shortest
path algorithm can be implemented using the binary heap data structure with time complexity:
A. O (|V |2 )
B. O (|E| + |V | log |V |)
C. O (|V | log |V |)
D. O ((|E| + |V |) log |V |)
Answer
Let s and t be two vertices in a undirected graph G = (V , E) having distinct positive edge weights.
L e t [X, Y ] be a partition of V such that s ∈ X and t ∈ Y . Consider the edge e having the
minimum weight amongst all those edges that have one vertex in X and one vertex in Y .
Answer
Let s and t be two vertices in a undirected graph G = (V , E) having distinct positive edge weights.
L e t [X, Y ] be a partition of V such that s ∈ X and t ∈ Y . Consider the edge e having the
minimum weight amongst all those edges that have one vertex in X and one vertex in Y .
Let the weight of an edge e denote the congestion on that edge. The congestion on a path is defined
to be the maximum of the congestions on the edges of the path. We wish to find the path from s to t
having minimum congestion. Which of the following paths is always such a path of minimum
congestion?
Answer
In a depth-first 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
gate2005-it algorithms graph-algorithms normal
Answer
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.
A:O
(m log n)
B:O
1. Bellman-Ford algorithm
2. Kruskal’s algorithm (n3 )
3. Floyd-Warshall algorithm C:O
4. Topological sorting (nm)
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
gate2005-it algorithms graph-algorithms normal
Answer
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and
there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its
adjacency matrix A, where A[i][j] = 1 if there is an edge directed from vertex i to j and 0
otherwise. The following algorithm determines whether there is a sink in the graph G.
i = 0;
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists");
else printf ("Sink does not exist");
Answer
A sink in a directed graph is a vertex i such that there is an edge from every vertex j ≠ i to i and
there is no edge from i to any other vertex. A directed graph G with n vertices is represented by its
adjacency matrix A, where A[i][j] = 1 if there is an edge directed from vertex i to j and 0
otherwise. The following algorithm determines whether there is a sink in the graph G.
i = 0;
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists") ;
else printf ("Sink does not exist");
Answer
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time,
the data structure to be used is:
A. Queue
B. Stack
C. Heap
D. B-Tree
Answer
Let T be a depth first search tree in an undirected graph G. Vertices u and ν are leaves of this tree
T . The degrees of both u and ν in G are at least 2. which one of the following statements is true?
G
© Copyright GATE Overflow. All rights reserved.
52 1 Algorithms (323)
Answer
Which of the following is the correct decomposition of the directed graph given below into its
strongly connected components?
A. {P, Q, R, S} , {T } , {U} , {V }
B. {P, Q, R, S, T , V } , {U}
C. {P, Q, S, T , V } , {R} , {U}
D. {P, Q, R, S, T , U, V }
Answer
Consider the depth-first-search of an undirected graph with 3 vertices P , Q, and R. Let discovery
time d(u) represent the time instant when the vertex u is first visited, and finish time f(u)
represent the time instant when the vertex u is last visited. Given that
d(P) f(P)
=5 = 12
units units
d(Q) f(Q)
=6 = 10
units units
d(R) f(R)
= 14 = 18
unit units
Answer
In an unweighted, undirected connected graph, the shortest path from a node S to every other node
is computed most efficiently, in terms of time complexity, by
B. Warshall’s algorithm.
Answer
A. 123456
B. 132456
C. 132465
D. 324165
gate2007 algorithms graph-algorithms
Answer
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which
vertex u is visited for the first time and f[u] the time at which the DFS call to the vertex u
terminates. Which of the following statements is always TRUE for all edges (u, v) in the graph ?
Answer
Consider a weighted, undirected graph with positive edge weights and let uv be an edge in the
graph. It is known that the shortest path from the source vertex s to u has weight 53 and the
shortest path from s to v has weight 65. Which one of the following statements is always TRUE?
A. Weight (u, v) ≤ 12
B. Weight (u, v) = 12
C. Weight (u, v) ≥ 12
D. Weight (u, v) > 12
Answer
The Breadth First Search algorithm has been implemented using the queue data structure. One
possible order of visiting the nodes of the following graph is:
A. MNOPQR
B. NQMPOR
C. QMNPRO
D. QMNPOR
gate2008 normal algorithms graph-algorithms
Answer
Dijkstra's single source shortest path algorithm when run from vertex a in the above graph,
computes the correct shortest path distance to
A. only vertex a
B. only vertices a, e, f, g, h
C. only vertices a, b, c, d
D. all the vertices
Answer
The most efficient algorithm for finding the number of connected components in an undirected graph
on n vertices and m edges has time complexity
A. Θ(n)
B. Θ(m)
C. Θ(m + n)
D. Θ(mn)
Answer
Consider the following sequence of nodes for the undirected graph given below:
1. abefdgc
2. abefcgd
3. adgebcf
4. adbcgef
A Depth First Search (DFS) is started at node a. The nodes are listed in the order they are first
visited. Which of the above is/are possible output(s)?
A. 1 and 3 only
B. 2 and 3 only
C. 2, 3 and 4 only
D. 1, 2 and 3 only
gate2008-it algorithms graph-algorithms normal
Answer
Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?
Q: Finds whether any negative weighted cycle is reachable from the source.
A. P only
B. Q only
C. Both P and Q
D. Neither P nor Q
Answer
Consider the directed graph shown in the figure below. There are multiple shortest paths between
vertices S and T . Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in
any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is
discovered.
A. SDT
B. SBDT
C. SACDT
D. SACET
gate2012 algorithms graph-algorithms normal
Answer
What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete
graph of n vertices?
A. θ(n2 )
B. θ(n2 log n)
C. θ(n3 )
D. θ(n3 log n)
Answer
Let G be a graph with n vertices and m [Link] is the tightest upper bound on the running time
of Depth First Search on G, when G is represented as an adjacency matrix?
A. Θ(n)
B. Θ(n + m)
C. Θ(n2 )
D. Θ(m2 )
Answer
Answer
Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected,
undirected graph. The tree T formed by the tree arcs is a data structure for computing
Answer
Suppose depth first search is executed on the graph below starting at some unknown vertex.
Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not
been visited earlier. Then the maximum possible recursion depth (including the initial call) is
_________.
Answer
Let G = (V , E) be a simple undirected graph, and s be a particular vertex in it called the source.
For x ∈ V , let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is
(u, v) G
© Copyright GATE Overflow. All rights reserved.
58 1 Algorithms (323)
performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T,
then which one of the following CANNOT be the value of d(u) − d(v)?
A. −1
B. 0
C. 1
D. 2
gate2015-1 algorithms graph-algorithms normal
Answer
The number of different topological orderings of the vertices of the graph is _____________.
Answer
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a
vertex t at a distance four from the root. If t is the nth vertex in this BFS traversal, then the
maximum possible value of n is __________
gate2016-2 algorithms graph-algorithms normal numerical-answers
Answer
In an adjacency list representation of an undirected simple graph G = (V , E) , each edge (u, v) has
two adjacency list entries: [v] in the adjacency list of u, and [u] in the adjacency list of v. These are
called twins of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If
|E| = m and |V | = n , and the memory size is not a constraint, what is the time complexity of the
most efficient algorithm to set the twin pointer in each entry in each adjacency list?
A. Θ (n2 )
B. Θ (n + m)
C. Θ (m2 )
D. Θ (n4 )
Answer
Let G = (V , E) be any connected, undirected, edge-weighted graph. The weights of the edges in
E are positive and distinct. Consider the following statements:
I. Minimum Spanning Tree of G is always unique.
II. Shortest path between any two vertices of G is always unique.
A. I only
B. II only
C. both I and II
D. neither I nor II
Answer
The Breadth First Search (BFS) algorithm has been implemented using the queue data structure.
Which one of the following is a possible order of visiting the nodes in the graph below?
A. MNOPQR
B. NQMPOR
C. QMNROP
D. POQNMR
gate2017-2 algorithms graph-algorithms
Answer
Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting
depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited
after visiting u in the traversal. Which of the following statement is always true?
Answer
Given a weighted directed graph with n vertices where edge weights are integers (positive, zero,
or negative), determining whether there are paths of arbitrarily large weight can be performed in
time
A. O(n)
O(n. log(n)) O(n)
© Copyright GATE Overflow. All rights reserved.
60 1 Algorithms (323)
Answer
Suppose a depth-first traversal of this graph is performed, assuming that whenever there is a
choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree
edges is T , the number of back edges is B and the number of cross edges is C . Then
a. B = 1, C = 1 , and T = 4.
b. B = 0, C = 2 , and T = 4.
c. B = 2, C = 1 , and T = 3.
d. B = 1, C = 2 , and T = 3.
e. B = 2, C = 2 , and T = 1.
tifr2014 algorithms graph-algorithms
Answer
Selected Answer
Answer is B.
A. True.
B. False.
C. True.
D. True.
Selected Answer
a. While adding vertex u to I it should not have an edge with any node in I .
b. The algorithm runs till V is empty (in O(n) time) and is checking u with each vertex v in set I
(in O(n) time). So, overall complexity O(n2 ).
Selected Answer
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S=∅
3 Q = G. V
4 while Q ≠ ∅
5 u = EXTRACT-MIN(Q)
6 S = S ∪ {u}
7 for each vertex v ∈ G. Adj[u]
8 RELAX(u, v, w)
Correct Solutions:
(A).
⎧0 ∞ ∞ ∞ ∞ ∞ ⎫
Q = ⎨A , B , C , D , E , F ⎬
⎩ ⎭
(B). A A−B−D−C−F−E
© Copyright GATE Overflow. All rights reserved.
62 1 Algorithms (323)
Answer is (A) because Floyd Warshall algorithm is used to find all shortest paths which is a
dynamic programming approach.
Selected Answer
Answer is C.
X - 3 DFS uses stack implicitly
Y - 2 BFS uses queue explicitly in Algo
Z - 1 Heap-Heapsort
Selected Answer
Answer is (C).
BFS is used to count shortest path from source (If all path costs are 1)
Selected Answer
For GATE purpose, without actually applying DFS, we can answer by just seeing options.
In DFS, we go in depth first i.e., one node to another in depth first order.
In all the other options we can reach directly from the node to the next node.
Selected Answer
After applying the shortest path algorithm, check cost of vertex from source to every vertex in G1 .
If G1 is connected all these costs must be 0 as edge weights of subgraph G1 is 0 and that should
be the shortest path. If cost is not 0, to at least one vertex in G1 (not necessarily G), then G1 is
disconnected.
Answer is B.
Selected Answer
D is correct.
A 1 2
1 1 2
2 1 2
1. A[1][1] and A[2][2] > n − 1 and there exists no Hamiltonian cycle. Hence invalid.
2. The longest path between V1 and V2 is 1, but A[1][2] is 2, which is invalid. And no path
between V2 and V1 yet A[2][1] = 1 // it should be max cost path between j and k, not
path length.
Now consider a graph with 2 nodes and two edges, one from V1 and V2 and other form V2 and
V1 . Running the above algorithm will result in A being
A 1 2
1 2 3
2 3 4
Selected Answer
Answer is (B). In Dijkstra's algorithm at each point we choose the smallest weight edge which
starts from any one of the vertices in the shortest path found so far and add it to the shortest path.
Selected Answer
There are two connected graphs G1 and G2 , with same vertices. In least case, both graphs will
have n − 1 edges with n vertices as both the given graphs are connected.
When we UNION both the graphs as G = G1 ∪ G2 then G will be having at most (2n − 2) edges
in the best case when both the graphs don't have any common edges between them (or) at least
more than n − 1 edges if they have few common edges between them as the intersection of these
two graphs is not connected.
Suppose if both the graphs G1 and G2 have exactly the same edges then their intersection will be
a connected graph.
A graph with
n vertices and more than n − 1 edges will definitely have a cycle.
Hence (B) is the correct option.
Selected Answer
Answer is D.
A and B produce disconnected components with the GIVEN order in options which is NEVER
allowed by prims's algorithm.
C produces connected component every instant a new edge is added BUT when first vertex is
chosen(first vertex is chosen randomly) first edge must be the minimum weight edge that is
chosen . Therefore, (A, D) MUST be chosen BEFORE (A, B). Therefore, C is FALSE.
Selected Answer
Option (D) : Binary heap. |E| decrease key operations and each taking O (log |V |) time + |V |
O (log |V |)
© Copyright GATE Overflow. All rights reserved.
66 1 Algorithms (323)
Option (A) : Array. Finding min-vertex in each iteration takes O(V ) and this needs to be done
|V | times.
Binomial Heap is same as Binary heap here, as the critical operations are decrease key and
extract-min.
Selected Answer
For 82a: The answer should be Option A because edge e is the lightest safe edge connecting X
and Y so the minimum spanning tree of G must contain e (Greedy and optimal choice).
While option (B) might seem correct but it is not always true. One such case is when G is not
connected therefore there might not be any path between s and t.
Since the question is about definitely TRUE, (B) is incorrect and (A) is the only correct option.
Selected Answer
Selected Answer
Tree edges are those edges which appear in the final DFS forest. For example in case of connected
graph (i.e. resulting DFS forest containing only one tree), if we run DFS over it, edges belonging to
the resulting DFS tree are called tree edges.
Let us assume the graph has x number of connected (or strongly connected in case of a directed
graph) components. And assume 1st component has K1 tree edges, 2nd component has K2 tree
edges and xth component has Kx tree edges.
Or in other way we can imagine like, the final DFS forest has x trees and those trees are having
K1 , K2 , K3 , … , Kx edges respectively.
Now we know that a tree having Kx edges contains Kx + 1 nodes. Similarly a tree having
K1 edges contains K1 + 1 nodes, etc. and so on.
So, Summation of nodes in each tree =n
(K1 + 1) + (K2 + 1) + (K3 + 1) + … + (Kx + 1) = n ⟹ (K1 + K2 + K3 + … + Kx ) +
Selected Answer
Answer
(A).
Selected Answer
If there is a sink in the graph, the adjacency matrix will contain all 1's (except diagonal) in one
column and all 0's (except diagonal) in the corresponding row of that vertex. The given algorithm
is a smart way of doing this as it finds the sink in O(n) time complexity.
The first part of the code, is finding if there is any vertex which doesn't have any outgoing edge to
any vertex coming after it in adjacency matrix. The smart part of the code is E2 , which makes
rows skip when there is no edge from i to it, making it impossible for them to form a sink. This is
done through
E1 : A[i][j]
and
E2 : i = j ;
E1 makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If
A[i][j] becomes 1, i can no longer be a sink, similarly all previous j can also not be a sink (as
there was no edge from i to them and a sink requires an edge from all other vertices). Now, the
next potential candidate for sink is j. So, in E2 , we must make i = j.
For E3 , [Link]
Selected Answer
If there is a sink in the graph, the adjacency matrix will contain all 1s (except diagonal) in one
column and all 0s (except diagonal) in the corresponding row of that vertex. The given algorithm is
a smart way of doing this as it finds the sink in O(n) time complexity.
The first part of the code, is finding if there is any vertex which does not have any outgoing edge
to any vertex coming after it in adjacency matrix. The smart part of the code is E2 , which makes
rows skip when there is no edge from i to it, making it impossible them to form a sink. This is done
through
E1 : !A[i][j]
and
E2 : i = j ;
E1 makes sure that there is no edge from i to j and i is a potential sink till A[i][j] becomes 1. If
A[i][j] becomes 1, i can no longer be a sink, similarly all previous j can also not be a sink (as
there was no edge from i to them and a sink requires an edge from all other vertices). Now, the
next potential candidate for sink is j. So, in E2 , we must make i = j.
Now, the loop breaks when we found a potential sink- that is a vertex which does not have any
outgoing edge to any coming after it in adjacency matrix. So, if the column in which this vertex
comes is all 1s and the row is all 0s (except diagonal), this is the sink. Otherwise there is no sink in
the graph. So, E3 is checking this condition.
But in the code flag is used for storing the state that sink is present or not. And as per the usage
of flag in code, by default sink is considered present. So, the condition in E3 must make flag = 0,
if the found i is not a sink. So, the condition should be:
A[i][j] || !A[j][i]
So, (D) is the answer.
Selected Answer
Answer is A: Queue
We can find single source shortest path in unweighted graph by using Breadth First Search (BFS)
algorithm by using "Queue" data structure , in time O(m + n) (i.e. linear with respect to the
number of vertices and edges. )
Selected Answer
Selected Answer
A graph is said to be strongly connected if every vertex is reachable from every other vertex.
The strongly connected component is always maximal that is if x is strongly connected component
there should not exist another strongly connected component which contains x.
If we take R as a strongly connected component but which is part of PQRS and PQRS is part of
PQRSV T .
Selected Answer
As seen in question, after 10 we have to go for p again and since p is finished and then r is started
so r must be disconnected because if there is edges from q to r then r must be visited before q
and p end.
D is answer.
Selected Answer
Dijkastra and Warshall 's algorithm used only for weighted graph.
Both DFS and BFS can be used for finding path between 2 vertices in undirected and
unweighted graph but BFS can only give the shortest path as concerned in given question.
So, BFS is answer.
Note : Finding only path(DFS) and finding shortest path(BFS) matters a lot.
ust Read:
[Link]
BFS-What-are-the-applications-and-downsides-of-each
Selected Answer
Go with vertex with indegree 0. Remove the vertex with all edges going from it . Follow that
procedure.
We see 3 cannot come at first because indegree is not 0. So, D is answer here.
ALL other options are in Topological order.
Selected Answer
A. d[u] < d[v], Counter Example ⟹ Well if we directly start DFS on V first, then I call DFS on
X which visits U .
B. d[u] < f[v], Counter example ⟹ Same as A
C. f[u] < f[v], Counter example ⟹ Same as A again
So, answer is D.
Selected Answer
C. Weight (u, v) ≥ 12
If weight(u, v) < 12, then the min. weight of (s, v) =weight of (s, u)+ weight of
(u, v) = 53 + (< 12) will be less than 65.
27 votes -- Arjun Suresh (350k points)
Selected Answer
A. MNOPQR: If you try to run BFS, after M, you must traverse NQR (In some order). Here, P is
traversed before Q, which is wrong.
B. NQMPOR: This is also not BFS. P is traversed before O.
C. QMNPRO: Correct.
D. QMNPOR: Incorrect. Because R needs to be traversed before O.(Because M is ahead of N in
queue).
Answer :- C
Selected Answer
D. all the vertices. Just simulate the Dijkstra's algorithm on it. Dijkstra's algorithm is not meant for
graphs with negative-edge-weight-cycle, but here it does give the correct shortest path.
Selected Answer
Run DFS to find connected components. Its time complexity is Θ(m + n), hence (C) is the
answer.
Selected Answer
Answer: B
Selected Answer
Bellman-ford Algorithm
−−−−−−−−−−−−−−−−−−−
Single source shortest Path O(V E)
Relax every edge once in each iteration
E × (V − 1) = E. V − E = O(V . E)
As we can see that the last step is the verification step. In that step, values remained unchanged.
If there was a negative edge weight cycle reachable from source, then at verification step also,
those values will be different from the values above.
In case the cycle is not reachable from source then we can see that they will be at ∞ distance(or
cost) from the source from the beginning till the last step. As take anything away from the ∞ it
will still be infinite.
But it can also be the case that there are some points which are not forming a cycle and are still
unreachable from source, those also will be at ∞ distance from the source from the beginning till
end.
Hence, we won't be able to make a distinction among the cycle and such vertices. Thus, we say
that this algorithm can detect negative edge weight cycles only if they are reachable from the
source.
Answer is option B
Selected Answer
A B C D E F
S4
3(by ∞ 7 ∞ ∞ ∞
s)
B 4(by 7
∞ ∞ ∞ ∞
s) ∵ (4 + 3 also = 7)(S → d)
5
A 7 ∞ ∞ ∞
(S → B → A)
6
C 7 ∞ ∞
(S → B → C)
7 8
E ∞
(S → D) (S → A →
D 12(S → B → D) 8
E 12
T 12
Now We see for S to T its (S → A → C → E → T )
which is Option : D
Selected Answer
complexity becomes Θ (|V |3 ) . And given here is n vertices. So, the answer ends up to be
Θ (n3 ).
35 votes -- Gate Keeda (19.6k points)
Selected Answer
Depth First Search of a graph takes O(m + n) time when the graph is represented using
adjacency list. In adjacency matrix representation, graph is represented as an n ∗ n matrix. To do
DFS, for every vertex, we traverse the row corresponding to that vertex to find all adjacent
vertices (In adjacency list representation we traverse only the adjacent vertices of the vertex).
Therefore time complexity becomes O(n2 ).
Selected Answer
Selected Answer
BFS always has a starting node. It does not calculate shortest path between every pair but it
computes shortest path between W and any other vertex.
Selected Answer
Total 21 nodes are there. 2 nodes require back track here in this question.
So, max recursion depth is 21 − 2 = 19
( Do DFS from extreme ends such that max recursion depth will occur i.e. take leftmost top node
as initial node for DFS as shown in below image)
Selected Answer
2 is the answer.
d(u) − d(v) = 0 is possible when both u and v have an edge from t and t is in the shortest path
from s to u or v.
d(u) − d(v) = 1 is possible when v and t are in the shortest path from s to u and both t and v
are siblings- same distance from s to both t and v causing t − u edge to be in BFS tree and not
v − u.
d(u) − d(v) = −1 is possible as explained above by interchanging u and v.
d(u) − d(v) = 2 is not possible. This is because on BFS traversal we either visit u first or v. Let's
take u first. Now, we put all neighbors of u on queue. Since v is a neighbour and v is not visited
before as assumed, d(v) will become d(u) + 1. Similarly, for v being visited first.
Selected Answer
a _ _ _ _
f
Blank spaces are to be filled with
b,
c,
d,
e such that
b comes before
c, and
d comes before
e.
Number of ways to arrange
b,
c,
d,
e such that
b comes before
c and
d comes before
e, will be =
4!/(2! ∗ 2!) = 6
In topological sorting all nodes are like tasks and edges show the dependency among the tasks.
Node i to j an edge is there means task i must complete before task j.(in the mean time some
other task may get complete after task i and before task j..but task i and j sequence need to be
maintained)
Selected Answer
Selected Answer
Applying BFS on undirected graph gives you twin pointer. Visit every vertex level-wise. For every
vertex, fill adjacent vertex in the adjacency list. BFS takes Θ (n + m) time.
Take extra field for storing number of linked lists for particular vertex. Take extra m + n time( m
vertex and n edges).
Selected Answer
Answer is A.
MST is not unique only when edges are not distinct. Here the edges are distinct. Be careful for
the keyword DISTINCT.
Shortest Path can be different even if the edges are distinct. Example is shown below. Shortest
path from A to C is not unique here.
Selected Answer
In BFS, starting from a node, we traverse all node adjacent to it at first then repeat same for
next nodes.
Selected Answer
u = D and v = F
So, we conclude that
Selected Answer
O(V E)
Changing sign of weights of edges.
Selected Answer
Since they said that whenever there is a choice we will have to select the node which is
alphabetically earlier, therefore we choose the starting node as A.
The tree then becomes A−B−E−C . Therefore number of tree edges is 3, that is, (T = 3)
.
Now, there is one cycle B − E − C , so, we will get a back edge from C to B while performing
DFS. Hence B = 1.
Now, D becomes disconnected node and it can only contribute in forming cross edge . There are 2
cross edges D − A , D − B. Therefore C = 2 .
Answer is Option D.
Let G be a graph with 100! vertices!, with each vertex labelled by a distinct permutation od the
numbers 1, 2, ..., 100. There is an edge between vertices u and v if and only if the label of u can be
obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in
G, and z denote the number of connected components in G. Then y + 10z = ____
gate2018 algorithms graph-algorithms graph-connectivity numerical-answers
Answer
Selected Answer
Answer: 109
Explanation:
We have to find 2 things here, the degree of every vertex(which will be same for all vertices) and
number of connected components.
Here we got "3" because we can chose any 3 pairs of adjacenet numbers. So, with n, we have
n − 1 adjacent pairs to swap. So, degree will be n-1.
In our question, degree will be 100 − 1 = 99
Now let's see how many connected components we have.
It will be 1. Why?
If one can reach from one vertex to any other vertex, then that means that the graph is
connected.
Now if we start with a vertex say {1, 2, 3, 4} we can reach to other vertex, say {4, 3, 2, 1} by the
following path:
{1234} -> {1243} -> {1423} -> {4123} -> {4132} -> {4312} -> {4321}
Just take two adjacent numbers and swap them. With this operation you can create any
permutation, from any given initial permutation.
This way you can show that from any given vertex we can reach any other vertex. This shows that
the graph is connected and the number of connected components is 1.
y = 99 and z = 1
You are given n positive integers, d1 , d2 … dn , each greater than 0. Design a greedy algorithm to
test whether these integers correspond to the degrees of some n-vertex simple undirected graph
G = (V , E) . [A simple graph has no self-loops and at most one edge between any pair of vertices].
cmi2015 descriptive algorithms greedy-algorithm
Answer
The minimum number of record movements required to merge five files A (with 10 records), B (with
20 records), C (with 15 records), D (with 5 records) and E (with 25 records) is:
A. 165
B. 90
C. 75
D. 65
gate1999 algorithms normal greedy-algorithm
Answer
The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively
in chronological order: “as bs cs ae ds ce es fs be de gs ee fe hs ge he ” . Here, xs denotes the
starting time and xe denotes the ending time of activity X. We need to schedule the activities in a
set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for
the activity for its entire duration. What is the minimum number of rooms required?
A. 3
B. 4
C. 5
D. 6
gate2003 algorithms normal greedy-algorithm
Answer
We are given 9 tasks T1 , T2 , … , T9 . The execution of each task requires one unit of time. We can
execute one task at a time. Each task Ti has a profit Pi and a deadline di . Profit Pi is earned if the
task is completed before the end of the dith unit of time.
Task T1 T2 T3 T4 T5 T6 T7 T8 T9
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3
Are all tasks completed in the schedule that gives maximum profit?
Answer
We are given 9 tasks T1 , T2 , … , T9 . The execution of each task requires one unit of time. We can
execute one task at a time. Each task Ti has a profit Pi and a deadline di . Profit Pi is earned if the
task is completed before the end of the dith unit of time.
Task T1 T2 T3 T4 T5 T6 T7 T8 T9
Profit 15 20 30 18 18 10 23 16 25
Deadline 7 2 5 3 4 5 2 7 3
A. 147
B. 165
C. 167
D. 175
gate2005 algorithms greedy-algorithm process-schedule normal
Answer
The characters a to h have the set of frequencies based on the first 8 Fibonacci numbers as follows
a : 1, b : 1, c : 2, d : 3, e : 5, f : 8, g : 13, h : 21
A Huffman code is used to represent the characters. What is the sequence of characters
corresponding to the following code?
110111100111010
fdheg
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 83
A. fdheg
B. ecgdf
C. dchfg
D. fehdg
Answer
have probabilities 12 , 14 , 18 , 16
1 1 1
Suppose the letters a, b, c, d, e, f , 32 , 32 , respectively.
Answer
Consider the weights and values of items listed below. Note that there is only one unit of each item.
Answer
Selected Answer
Selected Answer
5 10 15 20 25
D A C B E
75
30 45
C B E
15 15 20 25
D A
5 10
No. of movements = 15 + 30 + 45 + 75 = 165.
23 votes -- Pooja Palod (31.3k points)
Selected Answer
Solution: B
The problem can be modeled as a graph coloring problem. Construct a graph with one node
corresponding to each activity A, B, C, D, E, F, G and H . Connect the activities that occur
between the start and end time of an activity. Now, the chromatic number of the graph is the
number of rooms required.
Selected Answer
Step -1 Sort the tasks in decreasing order of profit and if any conflict arises between two or more
tasks,resolve them by sorting them on basis of having greater deadline first(Because we have
more time to complete the task with greater deadline and same profit).
Step 2- Since Maximum deadline given is 7, so we consider we have 7 time slots ranging from
0 − 7 where a task Ti having deadline say 2 can be filled in slots either 0 − 1 or 1 − 2 and not
beyond 2 because this task has deadline of 2 time units, so this task has to be completed by
atmost time T = 2 .
Now according to question, since Each task completes in Unit time, so a single tasks takes only one
slot as shown.
Now Take the first task in the list i.e. T3 which has a deadline of 5, so it can be completed in
maximum 5 time units, so place it in slot 4 − 5 which is the maximum deadline by which this task
can be completed.
So, Task
T6 will be left out.
So, option (d) is the answer.
Selected Answer
This shows that we can greedily choose the better task and that should give us the optimal
solution. The best task would be the one with maximum profit. Thus we can sort the tasks based
on deadline and then profit as follows:
Task T7 T2 T9 T4 T5 T3 T6 T8 T1
Deadline 2 2 3 3 4 5 5 7 7
0 --T7 -- 1 -- T2 -- 2 -- T9 -- 3 -- T5 -- 4 -- T3 -- 5 -- T8 -- 6 -- T1 -- 7
so we know that T4 and T6 are left
Selected Answer
Answer is A. Huffman's tree is as follows. The two least frequent characters are taken as the
children of a newly made node and the frequency of the newly made node is made equal to the
sum of those two child nodes. Then the same procedure is repeated till all nodes are finished.
Selected Answer
Based on the probabilities, we can say the probable frequency of the letters will be
16, 8, 4, 2, 1, 1
Now, the Huffman tree can be constructed as follows:
Selected Answer
Voptimal is clearly 60. You can go for brute force or by normal intuition you can get it.
Now solving for Vgreedy.
Item
Weight Value Value/Weight
name
1 10 60 6
2 7 28 4
3 4 20 5
4 2 24 12
Sort them in descending order of Value/Weight as per the question.
Item
Weight Value Value/Weight
name
4 2 24 12
1 10 60 6
3 4 20 5
2 7 28 4
Now start picking items.(Note: You cannot take a fraction of the given weight as per the
question). Max weight size is given as 11(Inclusive).
have probabilities 12 , 14 , 18 , 16
1 1 1
Suppose the letters a, b, c, d, e, f , 32 , 32 , respectively.
What is the average length of the Huffman code for the letters a, b, c, d, e, f ?
A. 3
B. 2.1875
C. 2.25
D. 1.9375
gate2007 algorithms greedy-algorithm normal huffman-code
Answer
A message is made up entirely of characters from the set X = {P, Q, R, S, T } . The table of
probabilities for each of the characters is shown below:
Character Probability
P 0.22
Q 0.34
R 0.17
S 0.19
T 0.08
T otal 1.00
If a message of 100 characters over X is encoded using Huffman coding, then the expected length
of the encoded message in bits is ______.
Answer
Selected Answer
Answer should be D.
Letter Probability
a 1/2
b 1/4
c 1/8
d 1/16
e 1/32
f 1/32
a=0 1
b=10 2
c=110 3
d=1110 4
e=11110 5
f=11111 5
Avg length
1 1 1 1 1 1 16+16+12+8+5+5
= 2 ×1+ 4 ×2+ 8 ×3+ 16 ×4+ 32 ×5+ 32 ×5 = 32 = 1.9375
Selected Answer
X = {P, Q, R, S, T }
A finite sequence of bits is represented as a list with values from the set {0, 1}. For example,
[0, 1, 0], [1, 0, 1, 1], . . . .
[ ] denotes the empty list, and [b] is the list consisting of one bit b. The function length(l) returns
the length (number of bits) in the list l. For a nonempty list l, head(l) returns the first element of l,
tail(l)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 91
and tail(l) returns the list obtained by removing the first element from l. The operator ++ denotes
list concatenation.
For example:
i. Suppose s = t = 110100100. What are the first two bits of mystery2(s, t)?
Answer
A. Reversed
B. Sorted in descending order
C. Left unaltered
D. Sorted in ascending order
Answer
The following program computes values of a mathematical function f(x). Determine the form of
f(x).
main ()
{
int m, n; float x, y, t;
scanf ("%f%d", &x, &n);
t = 1; y = 0; m = 1;
do
{
t *= (-x/m);
y += t;
} while (m++ < n);
printf ("The value of y is %f", y);
}
Answer
Choose the correct alternatives (more than one may be correct) and write the corresponding letters
only:
Function X(M:integer):integer;
Var i:integer;
Begin
i := 0;
while i*i < M
do i:= i+1
X := i
end
Answer
var a, b: integer;
begin
a:=a+b;
b:=a-b;
a:a-b;
end;
A. exchanges a and b
B. doubles a and stores in b
C. doubles b and stores in a
D. leaves a and b unchanged
E. none of the above
Answer
Answer
In the following Pascal program segment, what is the value of X after the execution of the program
segment?
X := -10; Y := 20;
If X > Y then if X < 0 then X := abs(X) else X := 2*X;
A. 10
B. −20
C. −10
D. None
Answer
Assume that X and Y are non-zero positive integers. What does the following Pascal program
segment do?
while X <> Y do
if X > Y then
X := X - Y
else
Y := Y - X;
write(X);
Answer
a. Consider the following Pascal function where A and B are non-zero positive integers. What is the
value of GET (3, 2)?
b. The Pascal procedure given for computing the transpose of an N × N, (N > 1) matrix A of
integers has an error. Find the error and correct it. Assume that the following declaration are
made in the main program
const
MAXSIZE=20;
type
INTARR=array [1..MAXSIZE,1..MAXSIZE] of integer;
Procedure TRANSPOSE (var A: INTARR; N : integer);
var
I, J, TMP: integer;
begin
for I:=1 to N – 1 do
for J:=1 to N do
begin
TMP:= A[I, J];
A[I, J]:= A[J, I];
A[J, I]:= TMP
end
end;
Answer
What value would the following function return for the input x = 95?
A. 89
B. 90
C. 91
D. 92
gate1998 algorithms recursion identify-function normal
Answer
Answer
Suppose you are given an array s[1....n] and a procedure reverse (s, i, j) which reverses the order
of elements in s between positions i and j (both inclusive). What does the following sequence do,
where 1 ⩽ k ⩽ n :
Answer
C
© Copyright GATE Overflow. All rights reserved.
96 1 Algorithms (323)
A. xy
B. ex
C. ln(1 + x)
D. xx
gate2003 algorithms identify-function normal
Answer
In the following C program fragment, j, k, n and TwoLog_n are integer variables, and A is an array
of integers. The variable n is initialized to an integer ⩾ 3, and TwoLog_n is initialized to the value of
2∗ ⌈log2 (n)⌉
for (k = 3; k <= n; k++)
A[k] = 0;
for (k = 2; k <= TwoLog_n; k++)
for (j = k+1; j <= n; j++)
A[j] = A[j] || (j%k);
for (j = 3; j <= n; j++)
if (!A[j]) printf("%d", j);
A. {m ∣ m ≤ n, (∃i) [m = i!]}
B. {m ∣ m ≤ n, (∃i) [m = i2 ]}
C. {m ∣ m ≤ n, m is prime}
D. { }
Answer
main()
{
int x, y, m, n;
scanf("%d %d", &x, &y);
/* Assume x>0 and y>0*/
m = x; n = y;
while(m != n)
{
if (m > n)
m = m-n;
else
n = n-m;
}
printf("%d", n);
}
Answer
A. log m
B. m2
1
C. m2
1
D. m3
gate2004 algorithms identify-function normal
Answer
int main() {
int a = 2048, sum = 0;
foo(a, sum);
printf("%d\n", sum);
}
A. 8, 4, 0, 2, 14
B. 8, 4, 0, 2, 0
C. 2, 0, 4, 8, 14
D. 2, 0, 4, 8, 0
gate2005 algorithms identify-function recursion normal
Answer
#include <stdio.h>
int main () {
printf("%d", f(20, 1));
return 0;
}
A. 5
B. 8
C. 9
D. 20
gate2005-it algorithms identify-function normal
Answer
x [i] = {
1 if i ∈ X
0 otherwise
Consider the following algorithm in which x, y, and z are Boolean arrays of size n:
algorithm zzz(x[], y[], z[]) {
int i;
for(i=0; i<n; ++i)
z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] ∧ y[i]);
}
C. (X − Y ) ∩ (Y − X)
D. (X − Y ) ∪ (Y − X)
Answer
Consider the following C-function in which a[n] and b[m] are two sorted integer arrays and
c[n + m] be another integer array,
void xyz(int a[], int b [], int c []){
int i,j,k;
i=j=k=0;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
Which of the following condition(s) hold(s) after the termination of the while loop?
Answer
In the above function, which of the following is the correct expression for E?
A. (n == 0)||(m == 1)
B. (n = = 0) && (m = = 1)
C. (n == 0)||(m == n)
D. (n = = 0) && (m = = n)
Answer
void f (int n)
{
if (n <=1) {
printf ("%d", n);
}
else {
f (n/2);
printf ("%d", n%2);
}
}
A. 010110101
B. 010101101
C. 10110101
D. 10101101
gate2008-it algorithms recursion identify-function normal
Answer
void f (int n)
{
if (n <= 1) {
printf ("%d", n);
}
else {
f (n/2);
printf ("%d", n%2);
}
}
Which of the following implementations will produce the same output for f(173) as the above code?
P1 P2
void f (int n)
{
void f (int n)
if (n <=1) {
{
printf ("%d", n);
if (n/2) {
}
f(n/2);
else {
}
printf ("%d", n%2);
printf ("%d", n%2);
f (n/2);
}
}
}
A. Both P1 and P2
B. P2 only
C. P1 only
D. Neither P1 nor P2
Answer
#include <stdio.h>
int fun(int n, int *f_p) {
int t, f;
if (n <= 1) {
*f_p = 1;
return 1;
}
t = fun(n-1, f_p);
f = t + *f_p;
*f_p = t;
return f;
}
int main() {
int x = 15;
printf("%d/n", fun(5, &x));
return 0;
}
A. 6
B. 8
C. 14
D. 15
gate2009 algorithms recursion identify-function normal
Answer
#include<stdio.h>
int main()
{
int a[] = (12, 7, 13, 4, 11, 6);
printf("%d", f(a, 6));
return 0;
}
A. −9
B. 5
C. 15
D. 19
Answer
What is the return value of the function foo when it is called as foo(345, 10)?
A. 345
B. 12
C. 5
D. 3
gate2011 algorithms recursion identify-function normal
Answer
What is the return value of the function foo when it is called as foo(513, 2)?
A. 9
B. 8
C. 5
D. 2
gate2011 algorithms recursion identify-function normal
Answer
int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);
A. Θ(n2 )
2
Θ( log n)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 103
B. Θ(n2 log n)
C. Θ(n3 )
D. Θ(n3 log n)
Answer
Consider the following C function in which size is the number of elements in the array E:
Answer
Answer
Let A be the square matrix of size n × n. Consider the following pseudocode. What is the expected
output?
C=100;
for i=1 to n do
for j=1 to n do
{
Temp = A[i][j]+C;
A[i][j] = A[j][i];
A[j][i] = Temp -C;
}
for i=1 to n do
for j=1 to n do
output (A[i][j]);
Answer
Which one of the following most closely approximates the return value of the function fun1?
A. n3
B. n(log n)2
C. n log n
D. n log(log n)
Answer
int fun(int n) {
int x=1, k;
if (n==1) return x;
for (k=1; k<n; ++k)
x = x + fun(k) * fun (n-k);
return x;
}
Answer
Suppose c = ⟨c[0], … , c[k − 1]⟩ is an array of length k, where all the entries are from the set
{0, 1}. For any positive integers a and n, consider the following pseudocode.
DOSOMETHING (c, a, n)
z←1
for i ← 0 to k − 1
do z ← z2 mod n
if c[i]=1
then z ← (z × a) mod n
return z
Answer
Consider the following program operating on four variables u, v, x, y , and two constants X and Y.
x, y, u, v:= X, Y, Y, X;
While (x ≠ y)
do
if (x > y) then x, v := x - y, v + u;
else if (y > x) then y, u:= y - x, u + v;
od;
print ((x + y) / 2); print ((u + v) / 2);
Given X > 0 ∧ Y > 0 , pick the true statement out of the following:
A. The program prints gcd(X, Y ) and the first prime larger than both X and Y .
B. The program prints gcd(X, Y ) followed by lcm(X, Y ).
C. The program prints gcd(X, Y ) followed by 12 × lcm(X, Y ) .
D. The program prints 12 × gcd(X, Y ) followed by 12 × lcm(X, Y ) .
E. The program does none of the above.
Answer
def brian(n):
count = 0
while ( n ! = 0 )
n = n & ( n-1 )
count = count + 1
return count
Here n is meant to be an unsigned integer. The operator & considers its arguments in binary and
computes their bit wise AND. For example, 22 & 15 gives 6, because the binary (say 8-bit)
representation of 22 is 00010110 and the binary representation of 15 is 00001111, and the bit-wise
AND of these binary strings is 00000110, which is the binary representation of 6. What does the
function brian return?
Answer
Which of the following statements about the contents of matrix A at the end of this program must
be TRUE?
Answer
Here, the op function takes two bits as input and outputs their XOR(⊕).
Let x1 and x2 be the two input bits in the function op.
u = s ⊕ s ⊕ s ⊕ s … ⊕ s 2length(t) times
i. Taking XOR of s, 2length(t) times does not change the length(s). So, our answer will be
length(s).
ii. In this problem the two bits of length s are 11, so taking the XOR of 1, even number of times
gives the output 0. So, our answer is 00.
Selected Answer
Selected Answer
Selected Answer
For N = 9 , it returns 3.
For N = 10 it returns 4.
For N = 16 it returns 4.
For N = 17 it returns 5.
So answer should be C.
Selected Answer
Answer is simply A i.e. it swaps the values of the two.. Take any two values for A and B. and
perform the given operations over them.
Selected Answer
answer - xn
7 votes -- Ankit Rokde (9k points)
Selected Answer
Answer is C . This is classic example of if − else issue. Always else matches for nesting to the
closest if in C Programming & Pascal .
[Link]
if (x>y)
{
if (x<0)
x=abs(x)
else
x=2*x
}
Selected Answer
Answer: C
Let X = 3 and Y = 7 .
1st pass: X = 3 , Y = 4
2nd pass: X = 3 , Y = 1
3rd pass: X = 2 , Y = 1
4th pass: X = 1 , Y = 1
write (X), which writes 1.
Ref: [Link]
Selected Answer
a. =3
b.
begin
for I:=2 to N do
for J:=1 to ( I-1) do
begin
TMP:= A[I, J];
A[I, J]:= A[J, I];
A[J, I]:= TMP
end
Selected Answer
Selected Answer
abc Return
The final return statement is
1 1 1 c < b, so this never returns.
Answer D.
Selected Answer
Answer is A.
Effect of the above 3 reversals for any K is equivalent to left rotation of the array of size n by k.
Let , S[1......7]
1 2 3 4 5 6 7
so,n = 7 ,k = 2
reverse (S, 1, 2) we get [2, 1, 3, 4, 5, 6, 7]
reverse (S, 3, 7) we get [2, 1, 7, 6, 5, 4, 3]
reverse (S, 1, 7) we get [3, 4, 5, 6, 7, 1, 2]
Hence, option (A) rotates s left by k positions and is correct.
Selected Answer
We can take p = 1, s = 1 initialization outside of for loop because there is no condition checking in
for loop involving p, s .
i p = p*(x/i) s = s+p
1 x 1+x
x2
1+x
2 2 2
+ x2
1+x
2
3 x3 + x2
6
x3
+ 6
1+x
2
+ x2
4 x4
x3
24 + 6
x4
+ 24
xn
n n! ex
∞
xn x2 x3 x4 xn
ex =∑ =1+x+ + + +…+
n=0
n! 2 6 24 n!
Selected Answer
The nested loop is taking all integers from 2 to 2 ∗ log2 n. Take all their non-multiples before n,
and make the corresponding entry in A as 1. For example, for 2, and n = 10, A[3], A[5], A[7],
and A[9]are made 1. Similarly for 3, 4, ... till 2 ∗ log n. So, if any entry A[p] is 1 means it must
be a multiple of 2, 3, . . . . 2 ∗ log2 n , which is (2 log n)! and is greater than n. So, for no index p,
A[p] will be 0. So, answer is D.
Suppose the line
is replaced with
Now, the nested loop is taking all integers from 2 to log2 n , take all their multiples before n, and
make the corresponding entry in A as 1. For example, for 2, and n = 10, A[4], A[6], A[8] and
A[10] are made 1. Similarly for 3, 4, . . . till 2 ∗ log n . So, for all non-prime indices of A, we will
have a 1, and for prime indices we have a 0. And we print i if A[j] is 0 meaning j is prime.
Selected Answer
Ref: [Link]
Selected Answer
⟹ 2x2 = x2 + m
⟹ x = m1/2
We can also check by putting 2 or 3 different values also.
30 votes -- gate_asp (749 points)
Selected Answer
Option is D.
foo is printing the lowest digit. But the printf inside it is after the recursive call. This forces the
output to be in reverse order
2, 0, 4, 8
The final value sum printed will be 0 as C uses pass by value and hence the modified value inside
foo won't be visible inside main.
Selected Answer
[Link]
Selected Answer
Option (D)
Z = (X ∧ ¬Y ) ∨ (¬X ∧ Y )
⟹ Z = (X − Y ) ∪ (Y − X)[∵ A ∧ ¬B = A − B]
Selected Answer
The while loop adds elements from a and b (whichever is smaller) to c and terminates when either
of them exhausts. So, when loop terminates either i = n or j = m .
Suppose i = n. This would mean all elements from array a are added to c => k must be
incremented by n. c would also contain j elements from array b. So, number of elements in c
would be n + j and hence k = n + j .
Similarly, when j = m, k = m + i .
Hence, option (D) is correct. (Had k started from −1 and not 0 and we used + + k inside loop,
answer would have been option (C))
Selected Answer
Answer: C
Selected Answer
Answer: D
Selected Answer
Selected Answer
The answer is B.
Let the address of x be 1000.
1.f(5, 1000) = 8
2.f(4, 1000) = 5
3.f(3, 1000) = 3
4.f(2, 1000) = 2
5.f(1, 1000) = 1.
The evaluation is done from 5 to 1. Since recursion is used.
11 votes -- Gate Keeda (19.6k points)
Selected Answer
Suppose int array takes 4 bytes for each element and stored at base address 100.
Follow below image. Red color shows the return value.
It will print
12 + (7 − (13 − (4 + (11 − (6 + 0)))))
= 12 + (7 − (13 − (4 + (11 − 6)))))
= 12 + 7 − 13 + 9
= 15
23 votes -- gatecse (18k points)
Selected Answer
Answer is
12.
Selected Answer
The function returns the sum of digits in a binary representation of the given number
so 1+0+0+0+0+0+0+0+0+1 =2
16 votes -- Sandeep_Uniyal (7.5k points)
Selected Answer
The outer loop is running for n/2 times and inner loop is running for log2 n times (each iteration
doubles j and j stops at n means log2 n times j loop will iterate).
Now in each iteration k is incremented by n/2. So, overall k will be added n/2 ∗ logn ∗ n/2 with
an initial value of 0. So, final value of k will be Θ(n2 logn)
Selected Answer
Selected Answer
Answer is 9.
435 − (110110011)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 117
435 − (110110011)
num >>= 1; implies a num is shifted one bit right in every while loop [Link] loop is
executed 9 times successfully and 10th time num is zero.
Shifting a number "1"bit position to the right will have the effect of dividing by 2:
Selected Answer
A.
In the computation of given pseudo code for each row and column of Matrix A, each upper
triangular element will be interchanged by its mirror image in the lower triangular and after that
the same lower triangular element will be again re-interchanged by its mirror image in the upper
triangular, resulting the final computed Matrix A same as input Matrix A.
Selected Answer
i loop is executing n times. j loop is executing log n times for each i, and so value of p is log n. k
loop is executing log p times, which is log log n times for each iteration of i. In each of these q is
incremented. So, over all iterations of i, q will be incremented n log log n times. So, D choice.
Selected Answer
fun(1) = 1;
fun(2) = 1 + fun(1) ∗ fun(1) = 1 + 1 = 2;
fun(3) = 1 + fun(1) ∗ fun(2) + fun(2) ∗ fun(1) = 5;
fun(4) = 1 + fun(1) ∗ fun(3) + fun(2) ∗ fun(2) + fun(3) ∗ fun(1) = 1 + 5 + 4 + 5 = 15;
fun(5) = 1 + fun(1) ∗ fun(4) + fun(2) ∗ fun(3) + fun(3) ∗ fun(2) + fun(4) ∗ fun(1) = 1
1, n = 1
f(n) = {
1 + ∑n−1
i=1 f(i) × f(n − i), n > 1
f(1) = 1
f(2) = 1 + f(1). f(1) = 1 + 1.1 = 2
f(3) = 1 + f(1). f(2) + f(2). f(1) = 1 + 1.2 + 2.1 = 5
f(4) = 1 + f(1). f(3) + f(2). f(2) + f(3). f(2) = 1 + 1.5 + 2.2 + 5.1 = 15
f(5) = 1 + f(1). f(4) + f(2). f(3) + f(3). f(2) + f(4). f(1) = 1 + 1.15 + 2.5 + 5.2 + 15.1 =
Selected Answer
z = 2 ∗ 2%8 = 4 (since now z = 2 ) (non zero value so considered as true and continue)
c[0] = 1, so in the if clause, z = 4 ∗ 2%8 = 0
Now no need to check further :
Reason : All the operations that update Z are multiplicative operations and hence the value of Z
will never change from 0.
X = 8 , v = 26
X = 5 , v = 29
X = 2 , v = 32
Y = 1 , u = 35
X = 1 , v = 67
This is the value obtained.
Selected Answer
For example,
Suppose n = 15 = 00001111(binary)
n − 1 = 14(00001110)
00001111
^ 00001110
---------------------
00001110
Selected Answer
[Link] i=1 to n:
2. for j=1 to n:
3. temp=A[i][j]+10
4. A[i][j]=A[j][i]
5. A[j][i]=temp-10
6. end for
[Link] for
The minimum number of comparisons required to find the minimum and the maximum of 100
numbers is ________
gate2014-1 algorithms numerical-answers normal minimum-maximum
Answer
Given a set of n distinct numbers, we would like to determine both the smallest and the
largest number. Which of the following statements is TRUE?
Answer
Consider the problem of computing the minimum of a set of n distinct numbers. We choose
a permutation uniformly at random (i.e., each of the n! permutations of ⟨1, . . . . , n⟩ is chosen with
probability (1/n!) and we inspect the numbers in the order given by this permutation. We maintain
a variable MIN that holds the minimum value seen so far. MIN is initialized to ∞ and if we see a
value smaller than MIN during our inspection, then MIN is updated. For example, in the
inspection given by the following sequence, MIN is updated four times.
5942680317
What is the expected number of times MIN is updated?
A. O(1)
B. Hn = ∑ni=1 1/i
−
C. √n
D. n/2
E. n
tifr2014 algorithms minimum-maximum
Answer
Given a set of n distinct numbers, we would like to determine the smallest three numbers in this
set using comparisons. Which of the following statements is TRUE?
Answer
Selected Answer
1. To find the smallest element in the array will take n − 1 comparisons = 99.
2. To find the largest element -
a. After the first round of Tournament , there will be exactly n/2 numbers = 50 that will loose the
round.
b. So, the biggest looser (the largest number) should be among these 50 [Link] find the
largest number will take n/2 − 1 comparisons = 49.
Total 99 + 49 = 148.
Selected Answer
Selected Answer
1, 2, 3 1
1, 3, 2 1
2, 1, 3 2
2, 3, 1 2
3, 1, 2 2
3, 2, 1 3
Total number of times MIN updated is : 11.
Average no of times MIN updated is : (11/6)
Now going by the options i am getting B .
Selected Answer
Here, at first level we are Given n elements, out of which we have to find smallest 3 numbers.
We compare 2 − 2 elements as shown in figure & get n/2 elements at Second level.
Note: Minimum element is in these
n/2 elements.
n/2
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 123
n/2
So, comparisons for this is n/2.
Similarly for next level we have n/4 Comparisons & n/2 elements and so on.
Total Comparisons till now is n/2 + n/4 + n/8+. . . . +4 + 2 + 1 = (2log n − 1) = n − 1 {Use
G.P. sum}
We have 1st smallest at last level already =>0 Comparison for this.
=> 2nd & 3rd smallest can be found in O(log n) time as shown below:
Minimum Element must have descended down from some path from top to Bottom.
Every element that is just below m1(first minimum) is a candidate for second minimum.
=> Similarly for 3rd minimum we get O(log n) time.. As, every element that is just below 1st &
2nd minimum is a candidate for 3rd minimum.
Given an undirected weighted graph G = (V , E) with non-negative edge weights, we can compute
a minimum cost spanning tree T = (V , E ′ ) . We can also compute, for a given source vertex sϵV ,
the shortest paths from s to every other vertex in V . We now increase the weight of every edge in
the graph by 1. Are the following true or false, regardless of the structure of G? Give a
mathematically sound argument if you claim the statement is true or a counterexample if the
statement is false.
i. All the shortest paths from s to the other vertices are unchanged.
Answer
Choose a value for x that will maximize the number of minimum weight spanning trees (MWSTs) of
G. The number of MWSTs of G for this value of x is ____.
gate2018 algorithms graph-algorithms minimum-spanning-trees numerical-answers
Answer
Selected Answer
The given statement "All the shortest paths from s to the other vertices are unchanged." is false .
From the above graph it is clear that the shortest path from S to D is
S ⟹ A ⟹ B ⟹ C ⟹ D and the cost is 6.
Now, we increment the edge cost of all the edges by 1.
After incrementation, the shortest path from S to D gets changed. Now the shortest path becomes
S ⟹ E ⟹ D and shortest path cost is 9. The above graph is the proof.
Selected Answer
Number of possible MSTs increase, when we have multiple edges with same edge weights.
There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have
coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively
from bags 1 to 5 Their total weight comes out to 323 gm. Then the product of the labels of the bags
having 11 gm coins is ___.
gate2014-1 algorithms numerical-answers normal numerical-computation
Answer
Consider the following game. There is a list of distinct numbers. At any round, a player
arbitrarily chooses two numbers a, b from the list and generates a new number c by subtracting the
smaller number from the larger one. The numbers a and b are put back in the list. If the number c is
non-zero and is not yet in the list, c is added to the list. The player is allowed to play as many
rounds as the player wants. The score of a player at the end is the size of the final list.
Suppose at the beginning of the game the list contains the following numbers: 48, 99, 120, 165 and
273. What is the score of the best player for this game?
A. 40
B. 16
C. 33
D. 91
E. 123
tifr2014 algorithms numerical-computation
Answer
Selected Answer
X + Y = 31 → (2)
Solving (1), (2), we get X = 13 and Y = 18. So, here number of coins of 11 gm is 13 and
the only possible combination for 13 coins is
Selected Answer
Option D is correct
Answer
Suppose we have constructed a polynomial time reduction from problem A to problem B. Which of
the following can we infer from this fact?
A. If the best algorithm for B takes exponential time, there is no polynomial time algorithm for A.
B. If the best algorithm for A takes exponential time, there is no polynomial time algorithm for B.
C. If we have a polynomial time algorithm for A, we must also have a polynomial time algorithm for
B.
D. If we don’t know whether there is a polynomial time algorithm for B, there cannot be a
polynomial time algorithm for A.
Answer
We have constructed a polynomial time reduction from problem A to problem B. Which of the
following is a valid inference?
A. If the best algorithm for B takes exponential time, then there is no polynomial time algorithm for
A
B. If the best algorithm for A takes exponential time, then there is no polynomial time algorithm for
B.
C. If we have a polynomial time algorithm for A, then we must also have a polynomial time
algorithm for B
D. If we don’t know whether there is a polynomial time algorithm for B, then there cannot be a
polynomial time algorithm for A.
Answer
Choose the correct alternatives (more than one may be correct) and write the corresponding letters
only:
Answer
Ram and Shyam have been asked to show that a certain problem Π is NP-complete. Ram shows a
polynomial time reduction from the 3-SAT problem to Π, and Shyam shows a polynomial time
reduction from Π to 3-SAT. Which of the following can be inferred from these reductions?
Answer
Answer
[Link]
Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is
polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following
statements is true?
A. R is NP-complete
B. R is NP-hard
C. Q is NP-complete
D. Q is NP-hard
Answer
The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive
integer W , determine whether there is a subset of S whose elements sum to W . An algorithm Q
solves this problem in O(nW) time. Which of the following statements is false?
A. Q solves the subset-sum problem in polynomial time when the input is encoded in unary
B. Q solves the subset-sum problem in polynomial time when the input is encoded in binary
C. The subset sum problem belongs to the class NP
D. The subset sum problem is NP-hard
Answer
Answer
Given an integer n ≥ 3, consider the problem of determining if there exist integers a, b ≥ 2 such
that n = ab . Call this the forward problem. The reverse problem is: given a and b, compute ab (mod
b). Note that the input length for the forward problem is ⌊log n⌋ + 1, while the input length for the
reverse problem is ⌊log a⌋ + ⌊log b⌋ + 2. Which of the following statements is TRUE?
a. Both the forward and reverse problems can be solved in time polynomial in the lengths of their
respective inputs.
b. The forward problem can be solved in polynomial time, however the reverse problem is NP -
hard.
c. The reverse problem can be solved in polynomial time, however the forward problem is NP -
hard.
d. Both the forward and reverse problem are NP -hard.
e. None of the above.
Answer
Answer
A. Only i and ii
B. Only ii and iv
Answer
Option is B.
2 votes -- shubham (221 points)
Selected Answer
Problem
A reduces to Problem
B,
Option (B) If the best algorithm for A takes exponential time, there is no polynomial time
algorithm for B. will be correct.
Option B- True. As per first line above, if A is expositional then B cannot be a polynomial time.
Option C - False. If we have polynomial time algorithm for A then we can have polynomial,
expositional, sub expositional algorithm for B.
Option D- False. A can be polynomial. B can be harder than polynomial ( as per first line, B is as
hard as A can be termed as B = Ω(A)).
Selected Answer
Selected Answer
Ram's reduction shows that Π is NP hard because it must be at least as hard as 3-SAT which is a
known NP-Complete problem. Here, Π need not be NP-Complete.
Now, Shyam's reduction shows that 3-SAT problem is at least as hard as Π or equivalently Π is
not harder than 3-SAT. Since 3-SAT is in NP, Π must also be in NP.
Selected Answer
Option is C.
[Link]
[Link]
Selected Answer
Answer B.
Therefore, R is NP -Hard.
Now Q is reduced to S in polynomial time.
If Q is reducible to S in polynomial time, Q could be NP because all NP problems can be
reduced to S. Since Q could be NP therefore Q could be P also as P is subset of NP . Also Q
could be NPC because every NPC problem can be reduced to another NPC problem in
polynomial time.
Selected Answer
Subset problem is NP-Complete - there is reduction proof but I don't remember (Can see the below
link). So, (C) and (D) are true as an NPC problem is in NP as well as NPH.
[Link]
A. Input is encoded in unary. So, length of input is equal to the value of the input. So, complexity
= O(nW) where both n and W are linear multiples of the length of the inputs. So, the
complexity is polynomial in terms of the input length. So, (A) is true.
B. Input is encoded in binary. So, length of W will be lgW . (for W = 1024, input length will be
just 10). So, now W is exponential in terms of the input length of W and O(nW) also
becomes exponential in terms of the input lengths. So, Q is not a polynomial time algorithm.
So, (B) is false.
Selected Answer
Selected Answer
The reverse problem can be solved in polynomial time as ab requires at most log b recursive calls
using the approach given below:
pow(int a, int b)
{
if(b%2)
return a* pow(a*a, b/2);
else
return pow(a*a, b/2);
}
Now, the forward problem is also solvable in polynomial time. We need to check for all the roots of
n − 1
(from √n till n log n ) whether it is an integer . But each of these check can be done in log n
time using a binary search on the set of integers from 2..n and so, the overall complexity will be
(log n)2 which is polynomial in log n (log n is the size of input). So, (a) must be the answer.
Selected Answer
Intractable Problems are problems that are decidable, although the algorithm to decide that
problem might be efficient (P) or inefficient (NP), but at least an algorithm exists to solve these
problems.
Undecidable Problems are problems for which there is no algorithm to solve these problems.
The language of Undecidable Problems are "Recursively Enumerable but not recursive
languages" & "Not Recursively Enumerable Languages".
Clearly we can talk about the intractability of any problem if we know at least one
algorithm to solve the problem, if there is no algorithm to solve a problem how can we talk about
efficiency?
I don't know the most efficient algorithms to solve these problems but at least I can say that Brute
force approach will work on all the other options except the Halting Problem.
What P = NP implies?
"Any problem that is solved by a non deterministic Turing machine in polynomial time
also be solved by some deterministic Turing machine in polynomial time, even if the
degree of the polynomial is higher."
and
There is neither a Non Deterministic Turing Machine nor Deterministic Turing Machine
that can solve the Halting Problem.
So any inference about P & NP is not going to affect the solvability of Halting Problem,
since it is undecidable.
Selected Answer
E. All of them. Because all of them can be solved by Depth first traversal.
T (n) = T (n − 1) + n
T (1) = 1
Answer
T (n) = T ( n2 ) + 1
T (1) = 1
Answer
T (n) = √−
n + T ( n2 )
T (1) = 1
gate1989 descriptive algorithms recurrence
Answer
Express T (n) in terms of the harmonic number Hn = ∑nt=1 1/i, n ≥ 1 , where T (n) satisfies the
recurrence relation,
T (n) = n T (n − 1)
n+1
+ 1 , for n ≥ ∑ and T (1) = 1
Answer
Consider the function F(n) for which the pseudocode is given below :
Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
else
For i = 1 to n do
begin
C ← 0
For j = 1 to n – 1 do
begin C ← C + 1 end
F1 = F1 * C
end
F = F1
end
Answer
Consider the function F(n) for which the pseudocode is given below :
Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
else
For i = 1 to n do
begin
C ← 0
For j = 1 to n – 1 do
begin C ← C + 1 end
F1 = F1 * C
end
F = F1
end
Answer
Let an 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 an in terms of an−1 . Solve for an .
Answer
The recurrence relation that arises in relation with the complexity of binary search is:
A. T (n) = 2T ( n2 ) + k, k is a constant
B. T (n) = T ( n2 ) + k, k is a constant
C. T (n) = T ( n2 ) + log n
D. T (n) = T ( n2 ) + n
Answer
T (1) = 2
T (n) = 3T ( n4 ) + n
has the solution T (n) equal to
A. O(n)
B. O(log n)
O (n 4 )
3
C.
Answer
A. T (n) = O√−
n
B. T (n) = O(n)
C. T (n) = O(log n)
D. None of the above
Answer
xn = 2xn−1 − 1, n > 1
x1 = 2
gate1998 algorithms recurrence descriptive
Answer
Answer
Procedure A(n)
If n ⩽ 2 return (1) else return (A(⌈√−
n ⌉));
is best described by
O(n)
© Copyright GATE Overflow. All rights reserved.
138 1 Algorithms (323)
A. O(n)
B. O(log n)
C. O(log log n)
D. O(1)
Answer
T (1) = 1
−−−−−
T (n + 1) = T (n) + ⌊√n + 1 ⌋ for all n≥1
The value of T (m2 ) for m ≥ 1 is
6 (21m − 39) + 4
A. m
2
B. m
6 (4m − 3m + 5)
m 2.5 − 11m + 20) − 5
2 (3m
C.
3 2 5
6 (5m − 34m + 137m − 104) + 6
m
D.
Answer
A. O(n)
B. O(n log n)
C. O(n2 )
D. O(2n )
Answer
A. 2n+1 − n − 2
n
−n
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 139
B. 2n − n
C. 2n+1 − 2n − 2
D. 2n + n
gate2004 algorithms recurrence normal
Answer
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 Recurrence
Algorithm Relation
T (n) = T (n
P. Binary search I. − k) + T (k)
+ cn
T (n) = 2T (n
Q. Merge sort II.
− 1) + 1
T (n) = 2T (n
R. Quick sort III.
/2) + cn
Tower of T (n) = T (n/2)
S. IV.
Hanoi +1
Which of the following is the correct match between the algorithms and their recurrence relations?
Answer
A. T (n) = Θ(log n)
B. T (n) = Θ(√−n)
C. T (n) = Θ(n)
D. T (n) = Θ(n log n)
Answer
T (n) = 2T (√−
n ) + 1, T (1) = 1
Answer
Let xn denote the number of binary strings of length n that contain no consecutive 0s.
Which of the following recurrences does xn satisfy?
A. xn = 2xn−1
B. xn = x⌊n/2⌋ + 1
C. xn = x⌊n/2⌋ + n
D. xn = xn−1 + xn−2
Answer
Let xn denote the number of binary strings of length n that contain no consecutive 0s.
The value of x5 is
A. 5
B. 7
C. 8
D. 16
gate2008 algorithms recurrence normal
Answer
A. √(n)(log n + 1)
B. √(n) log n
√(n) log √(n)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 141
Answer
n≤3
T (n) = {
n
T ( n3 ) + cn otherwise
Which one of the following represents the time complexity of the algorithm?
A. Θ(n)
B. Θ(n log n)
C. Θ(n2 )
D. Θ(n2 log n)
Answer
The recurrence relation capturing the optimal execution time of the T owers of Hanoi problem
with n discs is
A. T (n) = 2T (n − 2) + 2
B. T (n) = 2T (n − 1) + n
C. T (n) = 2T (n/2) + 1
D. T (n) = 2T (n − 1) + 1
Answer
Which one of the following correctly determines the solution of the recurrence relation with
T (1) = 1?
n
T (n) = 2T ( ) + log n
2
A. Θ(n)
B. Θ(n log n)
C. Θ(n2 )
D. Θ(log n)
Answer
Let an represent the number of bit strings of length n containing two consecutive 1s. What is the
recurrence relation for an ?
Answer
void get(int n)
{
if (n<1) return;
get (n-1);
get (n-3);
printf("%d", n);
}
If get(6) function is being called in main() then how many times will the get() function be invoked
before returning to the main()?
A. 15
B. 25
C. 35
D. 45
gate2015-3 algorithms recurrence normal
Answer
The given diagram shows the flowchart for a recursive function A(n). Assume that all statements,
except for the recursive calls, have O(1) time complexity. If the worst case time complexity of this
function is O(nα ), then the least possible value (accurate up to two decimal positions) of α is
________.
Answer
2T (√−
n ) + 1, n>2
T (n) = {
2, 0<n≤2
Then T (n) in terms of θ notation is
A. θ(log log n)
B. θ(log n)
C. θ(√−n)
D. θ(n)
Answer
T ( nk ) + T ( 3n
4 )+n if n ≥ 2
T (n) = {
1 if n = 1
Which of the following statements is FALSE?
Answer
2T (⌊√−
n ⌋) + log n if n ≥ 2
T (n) = {
1 if n = 1
Which of the following statements is TRUE?
Answer
Let T (a, b) be the function with two arguments (both nonnegative integral powers of 2) defined by
the following reccurence:
T (a, 1) = T ( a2 , 1) if a ≥ 2 ;
T (1, b) = T (1, 2b ) if b ≥ 2 ;
T (1, 1) = 1.
What is T (2r , 2s ) ?
A. rs
B. r+s
2r + 2s
C. ( )
2r
r+s
D. ( )
r
E. 2r−s if r ≥ s, otherwise 2s−r
tifr2017 algorithms recurrence
Answer
Answers: Recurrence
Selected Answer
T (n) = T (n − 1) + n
= T (n − 2) + (n − 1) + n
= T (n − 3) + (n − 2) + (n − 1) + n
.
.
.
= T (n − k) + [(n − k + 1) + (n − k + 2) + … + (n − 1) + n]
Recurrence stops at,
n−k=1
k=n−1
n(n+1)
∴ T (n) = T (1) + [2 + 3 + … + n] = 1 + 2 + 3 + … + n = 2
PS: Unless explicitly asked for asymptotic bound, we should always try to get the exact answer.
Selected Answer
T (n) = T (n/2) + 1
= T (n/4) + 2
= T (n/8) + 3
= T (n/2k ) + k.
When 2k = n, k = lg n
So, T (n) = T (1) + lg n = 1 + lg n
PS: Unless explicitly asked for asymptotic bound, we should give exact answers for solutions of
recurrence equations.
O(n^1/2)
Selected Answer
T (n) = n T (n − 1)
n+1
+1 → (1)
T (n − 1) = n−1 T (n − 2)
n
+1 → (2)
T (n − 2) = n−2 T (n − 3)
n−1
+1 → (3)
⟹ T (n) = n+1
n ∗ n−1 T (n − 2)
n
+ n+1
n +1
⟹ T (n) = n−1 T (n − 2)
n+1
+ n+1
n +1
⟹ T (n) = n+1
n−1 ∗ n−2 T (n − 3)
n−1
+ n+1
n−1 + n+1
n +1
⟹ T (n) = n+1
T (n − 3) + n+1
+ n+1
+1
© Copyright GATE Overflow. All rights reserved.
146 1 Algorithms (323)
⟹ T (n) = n−2 T (n − 3)
n+1
+ n+1
n−1 + n+1
n +1
⋮
so on
T (n) = n+1
n−k+1
T (n − k) + n+1
n + n+1
n−1 +…+ n+1
n−k+2
+1
T (n) = n+1
n−k+1
T (n − k) + (n + 1) ∗ ( n1 + 1
n−1 +…+ 1
n−k+2
) +1
⟹ T (n) = n+1
n−(n−1)+1
T (1) + (n + 1) ∗ ( n1 + 1
n−1 +…+ 1
n−(n−1)+2
)+1
⟹ T (n) = n+1
2 + (n + 1) × ( n1 + 1
n−1 + … + 13 ) + 1
1
⟹ T (n) = n+1
2 + (n + 1) × (Hn − 2 − 1) + 1
⟹ T (n) = n+1
2 + (n + 1) × Hn − n+1
2 − (n + 1) + 1
⟹ T(n) = (n + 1) × Hn − n
Now, Hn ≈ log n + γ
where γ is the Euler-Mascheroni constant.
T(n) = O(n log n)
15 votes -- Digvijaysingh Gautam (9k points)
Selected Answer
1. The function F(n) is NOT a recursive function. You can't have a recurrence relation for it in the
first place!
2. F(n) calculates (n − 1)n .
The equivalent C++ code is as follows: (You can try it out here: [Link]
long F(long n) {
long F1 = 1;
if(n==1) { return 3; }
else {
for(long i = 1; i <= n; i++) {
long C = 0;
// Note: the belore For loop only has one line
for(long j = 1; j <= n-1; j++) { C = C+1; }
// At the end of this for loop, C will be = (n-1)
F1 = F1 * C;
}
}
return F1;
}
It is clear that the inner for loop can be replaced by a single statement as follows:
long F(long n) {
long F1 = 1;
if(n==1) { return 3; }
else {
for(long i = 1; i <= n; i++)
F1 = F1 * (n-1);
}
return F1;
}
Selected Answer
Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3 //if (n==1) then return 3
else
For i = 1 to n do
begin
C ← 0
For j = 1 to n – 1 do //inner loop runs n-1 times outer loop runs for n times
begin C ← C + 1 end //means C=n-1
F1 = F1 * C //means n-1 is getting multiplied n times so ans is (n-1)^n for n>=2
end
F = F1
end
Selected Answer
Selected Answer
It is B. searching for only one half of the list. leading to T (n/2)+ constant time in comparing and
finding mid element.
Selected Answer
Answer: A
Selected Answer
Answer is B.
using master method (case 1)
where a = 2, b = 2
Selected Answer
T (n) = 2T (n − 1) − 1
= 2(2T (n − 2) − 1) − 1
= 22 T (n − 2) − 2 − 1
2
= (2T (n − 3) − 1) − 2 − 1
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 149
= 22 (2T (n − 3) − 1) − 2 − 1
= 23 T (n − 3) − 22 − 2 − 1
…
= 2n−1 T (n − (n − 1)) − (2n−2 + 2n−3 + ⋯ + 22 + 2 + 1)
a.(rn −1)
= 2n−1 × 2 − 2 2−1−1 ∵ T (1) = 2, Sn = r−1
n−1
= 2n − (2n−1 − 1)
= 2n−1 + 1
20 votes -- srestha (87k points)
Selected Answer
Let x = 2k
T (x) = 3T ( x2 ) + 1
We can apply Master's theorem case 1 with a = 3 and b = 2 as f(x) = 1 = O (xlog2 3−ϵ ) , ϵ > 0
log2 3
T (x) = Θ (xlog2 3 ) = Θ (2k ) = Θ (2log2 3 ) = Θ (3k )
k
So,
T (x) = 3T ( x2 ) + 1
= 9T ( x4 ) + 1 + 3
⋮
= 3log2 2 + (1 + 3 + 9 + ⋯ + 3log2 2 −1 )
k k
= 3.32−1
k
= 3 2−1
k+1
OR
T (2k ) = 3T (2k−1 ) + 1
= 32 T (2k−2 ) + 1 + 3
⋮
© Copyright GATE Overflow. All rights reserved.
150 1 Algorithms (323)
⋮
= 3k T (2k−k ) + (1 + 3 + 9 + ⋯ + 3k−1 )
(recursion depth is k)
= 3k + 33−1
k−1
= 3.32−1
k
3k+1 −1
= 2
Selected Answer
The complexity will be the number of times the recursion happens which is equal to the number of
times we can take square root of n recursively, till n becomes 2.
T (n) = T (⌈√−
n ⌉) + 1
T (2) = 1
T (22 ) = T (2) + 1 = 2
T (22 ) = T (4) + 1 = 3
2
T (22 ) = T (16) + 1 = 4
3
Selected Answer
−−−−
T (m2 ) = T (m2 − 1) + ⌊√(m2 )⌋
−−−−−−− −−−−
= T (m2 − 2) + ⌊√(m2 − 1) ⌋ + ⌊√(m2 )⌋
−−−−−−− −−−−−−− −−−−
= T (m2 − 3) + ⌊√(m2 − 2) ⌋ + ⌊√(m2 − 1) ⌋ + ⌊√(m2 )⌋
⋮
−−
− −−
− −−−−
= T (1) + ⌊√(2)⌋ + ⌊√(3)⌋ + … + ⌊√(m2 )⌋
= 3 × 1 + 5 × 2 + … + (2m − 1) × (m − 1) + m
(We are taking floor of square root of numbers, and between successive square roots number of
numbers are in the series 3, 5, 7 … like 3 numbers from 1..4, 5 numbers from 5 − 9 and so on).
Put m = 5, T (25) = 3 × 1 + 5 × 2 + 7 × 3 + 9 × 4 + 5 = 75
A. 59
B. 75
C. non-integer
D. 297.5
T (m2 ) = 3 × 1 + 5 × 2 + ⋯ + (2m − 1) × (m − 1) + m
= m + ∑i = 1m−1 (2i + 1). (i)
= m + ∑i = 1m−1 2i2 + i
(m−1).m.(2m−1) (m−1)m
=m+ 3 + 2
= m6 (6 + 4m2 − 2m − 4m + 2 + 3m − 3)
= m6 (4m2 − 3m + 5)
n.(n+1)
[Sum of the first n natural numbers = 2 .
n.(n+1).(2n+1)
Sum of the squares of first n natural numbers = 6 .]
Selected Answer
Option is D.
T (n) = 2T (n − 1) + a → (1)
T (n − 1) = 2T (n − 2) + a
T (n − 2) = 2T (n − 3) + a
We can re-write Equation (1) as
T (n) = 2[2T (n − 2) + a] + a = 4T (n − 2) + 3a
= 2[2T (n − 3) + a] + 3a = 8T (n − 3) + 7a
→ (2)
⋮
= 2 T (n − k) + (2k − 1)a
k
Selected Answer
T (n) = 2T (n − 1) + n, n ⩾ 2, T (1) = 1
= 2n+1 − n − 2
37 votes -- suraj (5.6k points)
T(1) = 1
T(2) = 4
T(3) = 11
T(4) = 26
T(5) = 57
T(6) = 120
T(7) = 247
So,
T (n) = 2n+1 − n − 2
Answer is B.
Selected Answer
f(n) = √−
1
n = n2 .
1
So, f(n) = O (nlogb a−ϵ ) is true for any real ϵ, 0 < ϵ < 2 . Hence Master theorem Case 1
satisfied,
Selected Answer
T (n) = 2T (n 2 ) + 1
1
1
= 2 (2T (n 22 ) + 1) + 1
1
= 4 × T (n 22 ) + 5
1
= 8 × T (n 23 ) + 13 ⋯
1
n 2k = 2(Putting 2 so that we can take [Link] more step of recurrence can't change the complex
Selected Answer
0 1−2
01 10 11 − 3
010 011 101 110 111 − 5
0101 0110 0111 1010 1011 1101 1110 1111 − 8
So, xn = xn−1 + xn−2 (For all the strings ending in 1, we get two new strings and for all strings
ending in 0, we get a new string. So, the new set of strings for n + 1, will have exactly n strings
ending in 1)
x5 = 8 + 5 = 13
19 votes -- Arjun Suresh (350k points)
Selected Answer
Number of binary strings of length n that contain no consecutive 0s, following will be the required
recurrence relation:
T (n) = T (n − 1) + T (n − 2) n > 2
base conditionT (1) = 2 and T (2) = 3
T (1) = 2 There will be 2 strings of length 1, i.e 0 & 1
T (2) = 3 There will be 3 strings of length 2, i.e. 01, 10, 11
T (3) = T (1) + T (2) = 2 + 3 = 5
T (4) = T (3) + T (2) = 5 + 3 = 8
T (5) = T (4) + T (3) = 8 + 5 = 13
Hence, answer is 13, but no option matches!
Selected Answer
T (n) = √(2)T ( n2 ) + √−
n
–2 – −−
= √2 T ( 2n2 ) + √2√ n2 + √−
n
⋮
–lg n
= √2 T (1) + lg n√−
n
= √−
n + lg n√−n
= √−
n (lg n + 1)
If we use Master theorem we get option B. But one must know that Master theorem is used to find
the asymptotic bound and not an EXACT value. And in the question here it explicitly says
"evaluates to".
Selected Answer
a = 1, b = 3, logb a = 0
So nlogb a = n0 = 1
f(n) = n
So, f(n) = Ω(1)
To, check Master theorem case 3, we need c > 0,
f(n/3) ≤ cf(n)
c=1
So using case three of master theorem
Selected Answer
T (1) = 1
T (n) = 2T (n − 1) + 1
So Answer should be (D)
Selected Answer
f(n) = log n
a = 2, b = 2 ⟹ nlogb a = n
So, f(n) = log n = O (n1−ϵ ), we can take any ϵ from 0-1 for example 0.5 which gives
log n = O(√(n)), whose proof is given
here: [Link]
Alternate way:
Selected Answer
Counting the number of bit strings NOT containing two consecutive 1's. (It is easy to derive a
recurrence relation for the NOT case as shown below)
0 1
00 01 10 − 3 (append both 0 and 1 to any string ending in 0, and append 0 to any string
ending in 1)
000 001 010 100 101 − 5 (all strings ending in 0 give two strings and those ending in 1
give 1 string)
0000 0001 0010 0100 0101 1000 1001 1010 − 8
⋮
a′n = a′n−1 + a′n−2 (where an denote the number of bit strings of length n containing two
consecutive 1s)
Selected Answer
Answer : Option B
T(n) = T(n-1) + T(n-3) + 2, here T(n) denotes the number of times a recursive call is made
for input n. 2 denotes the two direct recursive calls.
T(n ≤ 0) = 0
T(1) = 2
T(2) = 4
T(3) = 6
T(4) = 10
T(5) = 16
T(6) = 24
So, answer is 24 + 1 call from main = 25.
Selected Answer
nlog2 5
Thus value of alpha will be 2.32
51 votes -- Shashank Chavan (3.3k points)
Selected Answer
T (n) = 2T (√−
n) + 1
Put, n = 2m
T (2m ) = 2T (2m/2 ) + 1
put, T (2m ) = s(m)
s(m) = 2s(m/2) + 1
Using case 1 of master method ,
= Θ(m) = Θ(log n)
[Link]
Although partial answer is achieved but do not know how part (a) and (e) could be investigated.
Some people are taking about Akra-Bazzi method. Some ex. of this method is mentioned in
following PDF.
[Link]
[Link]
Selected Answer
Let n = 2k
T (2k ) = 2T (2k/2 ) + k
S(k) = 2S(k/2) + k
This gives S(k) = Θ(k log k) (Master theorem case 2)
= Θ(log n log log n)
So ans is b
Value of T (2r , 2s ) is nothing but the number of leaf nodes in its recursion tree. The reason for this
is that there is only one base condition T (1, 1) which returns 1 which are all ultimately added.
Here is an example recursion tree for T (22 , 23 ).
We will try to use some combinatorial technique to count the number of leaf nodes. One way of
counting the number of leaf nodes in the recurrence tree is by counting all possible paths that one
can take from the root to the leaf node. The reason for doing this would be clear in a moment. This
idea would be used to establish a link with a very common combinatorial problem.
Claim: If we consider a grid of size r × s then the possible paths from (r, s) to (0, 0) in that grid
such that we can either move backwards or downward is nothing but all possible paths in
recurrence tree from the root node to leaf node.
This happens to be true because arguments of recurrence relation are in powers of two, and at
each level of recurrence tree, the power of one of the arguments get reduced by one.
The number of valid paths possible in this grid will give us the count of the number of leaf nodes in
the recurrence tree. Interestingly this problem, when interpreted exactly in opposite way, happens
to be a very well known problem of combinatory.
In a grid of size r × s, count the number of possible paths from (0, 0) to (r, s) such that we can
either move forward(F) or upward(U).
Video:
r+s
T (2r , 2s ) = ( )
r
Video:
Consider the following program that attempts to locate an element x in an array a[] using binary
search. Assume N > 1 . The program is erroneous. Under what conditions does the program fail?
if (a[k] = x) then
writeln ('x is in the array')
else
writeln ('x is not in the array')
end;
Answer
The average number of key comparisons required for a successful search for sequential search on n
items is
A. n
2
n−1
B. 2
n+1
C. 2
D. None of the above
Answer
Consider the following algorithm for searching for a given number x in an unsorted array A[1..n]
having n distinct values:
Assuming that x is present in A, what is the expected number of comparisons made by the
algorithm before it terminates?
A. n
B. n − 1
C. 2n
D. n
2
Answer
Consider the following C program that attempts to locate an element x in an array Y [ ] using binary
search. The program is erroneous.
C. Y is [2 2 2 2 2 2 2 2 2 2]and x > 2
D. Y is [2 4 6 8 10 12 14 16 18 20]and 2 < x < 20 and x is even
Answer
Consider the following C program that attempts to locate an element x in an array Y [ ] using binary
search. The program is erroneous.
Answer
Let A be an array of 31 numbers consisting of a sequence of 0's followed by a sequence of 1's. The
problem is to find the smallest index i such that A [i] is 1 by probing the minimum number of
locations in A. The worst case number of probes performed by an optimal algorithm is
____________.
Answer
A. Sort the array using quick-sort and then use binary search.
B. Merge the sorted lists and perform binary search.
C. Perform a single binary search on the entire array.
D. Perform separate binary searches on the odd positions and the even positions.
E. Search sequentially from the end of the array.
tifr2010 searching
Answer
Consider the following three version of the binary search program. Assume that the elements of type
T can be compared with each other; also assume that the array is sorted.
i, j, k : integer;
a : array [1....N] of T;
x : T;
Program 1 : 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)
Program 2 : i := 1; j := N;
repeat
k := (i + j) div 2;
if x < a[k] then j := k - 1;
if a[k] < x then i := k + 1;
until i > j
Program 3 := i := 1; j := N
repeat
k := (i + j) div 2;
if x < a[k] then j := k else i := k + 1
until i > j
A binary search program is called correct provided it terminates with a[k] = x whenever such an
element exists, or it terminates with a [k] ≠ x if there exists no array element with value x. Which
of the following statements is correct?
Answer
Answers: Searching
Selected Answer
k=(i+j) / 2;
if (a[k] < x) then i = k;
else j = k;
k=(i+j) / 2;
if (a[k] < x) then i = k + 1;
else j = k - 1;
Initially i = 1, j = 10 ;
first time k = (i + j)/2 = 11/2 = 5.5 = 5 (because of integer type) =i
second time = k = (i + j)/2 = 15/2 = 7.5 = 7 = i
third time = k = (i + j)/2 = 17/2 = 8.5 = 8 = i
fourth time = k = (i + j)/2 = 18/2 = 9 = i
fifth time = k = (i + j)/2 = 19/2 = 9.5 = 9 = i
sixth time = k = (i + j)/2 = 19/2 = 9.5 = 9 = i
seventh time = k = (i + j)/2 = 19/2 = 9.5 = 9 = i
Selected Answer
( )
n×(n+1)
2
= n
= n+1
2
56 votes -- Arjun Suresh (350k points)
Selected Answer
(E) = 1×
© Copyright GATE Overflow. All rights reserved.
164 1 Algorithms (323)
1 (n−1)2
=1× n +2× n−1
n2
+3× n3
+…
1/n (n−1)/n2
= n−1 + 2 (Sum to infinity of aritmetico-geometric series with a = n1 , r = n−1
n and
1− n (1− n−1
)
n
Reference: [Link]
1 (n−1)2
E=1× n +2× n−1
n2
+3× n3
+…
(n−1)2 (n−1)3
n =
E n−1 n−1
n2
+2× n3
+3× n4
+…
1 (n−1)2
E − E n−1
n = n + n−1
n2
+ n3
+…
1 (1/n) 1
E. n = = 1 (Sum to infinity of GP with a = n and r = n−1
n ) ⟹ E=n
1− n−1
n
Selected Answer
for Q.84
Selected Answer
Answer should be A.
if given element that we are searching is greater then searching will be continued upper half of
array
otherwise
j = k − 1;
lower half.
Selected Answer
Here, since 0s are followed by 1s so we have a sorted sequence and we can apply binary search.
(low+high) th
At each stage we compare with 2 element index and if it is 1 we check left and if it is 0
we check right.
#include <bits/stdc++.h>
using namespace std;
#define N 100
void display(bool a[]) {
int i=0;
while(i<31) printf("%2d ",a[i++]);
}
void assign(bool a[],int zeros) {
for(int i=0;i<31;i++)
(i<zeros)?a[i] = 0:a[i] = 1;
}
int main() {
srand(time(NULL));
bool a[31];
// header
for(int i=0;i<31;i++) printf("%2d ",i);
printf("\n\n");
int max_probes = 0;
for(int iteration = 1;iteration <= N;iteration++) {
int zeros = rand()%32;
assign(a,zeros);
sort(a,a+31);
int low,high,mid,ans;
std::vector<int> seq;
low = 0;
high = 31;
while(low < high) {
mid = low + floor((high - low) / 2);
seq.push_back(mid);
if(a[mid] == 0) {
low = mid + 1;
ans = low;
if(a[mid + 1] == 1) break;
} else {
high = mid;
ans = high;
if(mid > 0)
if(a[mid - 1] == 0) break;
}
}
display(a);
printf(" | probes=%d ",[Link]());
for(auto e:seq) printf("%d ",e);
printf(" | at = %dth\n",ans);
//if(ans == 15) printf("\nHHH=-------------\n");
max_probes = max(max_probes,(int)([Link]()));
[Link]();
}
printf("%d\n",max_probes);
}
Selected Answer
We can simply use clever indexing to binary search the element in the odd positions, and in the
even positions separately.
This will take O(log n) time and O(1) space in the worst case.
A: Sorting using Quicksort will take O(n2 ) time.
B: Merging will take O(n) time and O(n) space.
C: Binary search only works on a sorted array.
E: Sequential search will take O(n) time.
Selected Answer
First program wont work if array has elements same..it may go into infinite loop .To make it work
it properly we have to do following changes j = k − 1 and i = k + 1
Consider a plate stacked with several disks, each of a different diameter (they could all be, for
instance, dosas or chapatis of different sizes). We want to sort these disks in decreasing order
according to their diameter so that the widest disk is at the bottom of the pile. The only operation
available for manipulating the disks is to pick up a stack of them from the top of the pile and invert
that stack. (This corresponds to lifting up a stack dosas or chapatis between two big spoons and
flipping the stack.)
Answer
You have n lists, each consisting of m integers sorted in ascending order. Merging these lists into a
single sorted list will take time:
A. O(nm log m)
B. O(mn log n)
C. O(m + n)
D. O(mn)
Answer
A stable sort preserves the order of values that are equal with respect to the comparison function.
We have a list of three dimensional points
We sort these in ascending order by the second coordinate. Which of the following corresponds to a
stable sort of this input?
Answer
Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken
by the program for the inputs [1 2 3 4] and [5 4 3 2 1], respectively. Which of the following holds?
A. t1 = t2
B. t1 > t2
C. t1 < t2
D. t1 = t2 + 5 log 5
Answer
Answer
Answer
Give an optimal algorithm in pseudo-code for sorting a sequence of n numbers which has only k
distinct numbers (k is not known a Priori). Give a brief analysis for the time-complexity of your
algorithm.
gate1991 sorting time-complexity algorithms difficult
Answer
Choose the correct alternatives (more than one may be correct) and write the corresponding letters
only:
Answer
Assume that the last element of the set is used as partition element in Quicksort. If n distinct
elements from the set [1 … n] are to be sorted, give an input for which Quicksort takes maximum
time.
gate1992 algorithms sorting easy
Answer
A. Dynamic programming
B. Backtracking
D. Greedy method
Answer
For merging two sorted lists of sizes m and n into a sorted list of size m + n, we require
comparisons of
A. O(m)
B. O(n)
C. O(m + n)
D. O(log m + log n)
Answer
B. Backtracking approach
C. Heuristic search
D. Greedy approach
Answer
Use bubblesort to arrange the sequence in ascending order. Give the sequence at the end of each of
the first five passes.
gate1995 algorithms sorting easy
Answer
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.
Answer
Quick-sort 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 C1 and C2 be the number of comparisons made for the inputs (i) and (ii) respectively. Then,
A. C1 < C2
B. C1 > C2
C. C1 = C2
D. we cannot say anything for arbitrary n
gate1996 algorithms sorting normal
Answer
(A) O
(P) Selection sort
(log n)
(B) O
(n (Q) Insertion sort
)
(C) O
(R) Binary search
(n log n)
(D) O
(S) Merge sort
(n2 )
A. A-R B-P C-Q D-S
B. A-R B-P C-S D-Q
C. A-P B-R C-S D-Q
D. A-P B-S C-R D-Q
gate1998 algorithms sorting easy
Answer
Answer
If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:
Answer
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 1st, 2nd and 3rd smallest elements in minimum
number of comparisons.
Answer
An array contains four occurrences of 0, five occurrences of 1, and three occurrences of 2 in any
order. The array is to be sorted using swap operations (elements that are swapped need to be
adjacent).
a. What is the minimum number of swaps needed to sort such an array in the worst case?
b. Give an ordering of elements in the above array so that the minimum number of swaps needed
to sort the array is maximum.
Answer
Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the
worst case complexity of sorting n numbers using Randomized quicksort?
A. O(n)
B. O(n log n)
C. O(n2 )
D. O(n!)
Answer
The unusual Θ(n2 ) implementation of Insertion Sort to sort an array uses linear search to identify
the position where an element is to be inserted into the already sorted part of the array. If, instead,
we use binary search to identify the position, the worst case running time will
A. remain Θ(n2 )
B. become Θ(n(log n)2 )
C. become Θ(n log n)
D. become Θ(n)
Answer
In a permutation a1 . . . an , of n distinct integers, an inversion is a pair (ai , aj ) such that i<j and
ai > aj .
If all permutations are equally likely, what is the expected number of inversions in a randomly
chosen permutation of 1.. . n?
n(n−1)
A. 2
n(n−1)
B. 4
n(n+1)
C. 4
D. 2n[log2 n]
Answer
In a permutation a1 . . . an , of n distinct integers, an inversion is a pair (ai , aj ) such that i<j and
ai > aj .
What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are
restricted to permutations of 1.. . n with at most n inversions?
A. Θ(n2 )
B. Θ(n log n)
C. Θ(n1.5 )
D. Θ(n)
Answer
The tightest lower bound on the number of comparisons, in the worst case, for comparison-based
sorting is of the order of
A. n
B. n2
C. n log n
D. n log2 n
Answer
Suppose there are ⌈log n⌉ sorted lists of ⌊n/ log n⌋ elements each. The time complexity of
producing a sorted list of all these elements is: (Hint:Use a heap data structure)
C. Ω(n log n)
D. Ω (n3/2 )
Answer
Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a
sorted array containing 2n integers obtained by merging the two arrays a and b. Assuming the
arrays are indexed starting from 0, consider the following four statements
A. only I and II
B. only I and IV
C. only II and III
D. only III and IV
Answer
Which one of the following in place sorting algorithms needs the minimum number of swaps?
A. Quick sort
B. Insertion sort
C. Selection sort
D. Heap sort
Answer
The median of n elements can be found in O(n) time. Which one of the following is correct about
the complexity of quick sort, in which median is selected as pivot?
A. Θ(n)
B. Θ(n log n)
C. Θ(n2 )
D. Θ(n3 )
Answer
Which of the following sorting algorithms has the lowest worse-case complexity?
A. Merge sort
B. Bubble sort
C. Quick sort
D. Selection sort
Answer
Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which
splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let T (n) be
the number of comparisons required to sort n elements. Then
A. T (n) ≤ 2T (n/5) + n
B. T (n) ≤ T (n/5) + T (4n/5) + n
C. T (n) ≤ 2T (4n/5) + n
D. T (n) ≤ 2T (n/2) + n
Answer
If we use Radix Sort to sort n integers in the range (nk/2 , nk ], for some k>0 which is
independent of n, the time taken would be?
A. Θ(n)
B. Θ(kn)
C. Θ(n log n)
D. Θ(n2 )
Answer
What is the number of swaps required to sort n elements using selection sort, in the worst case?
A. Θ(n)
B. Θ(n log n)
C. Θ(n2 )
D. Θ(n2 log n)
Answer
th
In quick-sort, for sorting n elements, the (n/4) smallest element is selected as pivot using an
O(n) time algorithm. What is the worst case time complexity of the quick sort?
A. Θ(n)
B. Θ(n log n)
C. Θ(n2 )
D. Θ(n2 log n)
Answer
A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort
algorithm. The worst case running time of this computation is
A. O(n log n)
B. O(n2 log n)
C. O(n2 + log n)
D. O(n2 )
Answer
The number of elements that can be sorted in Θ(log n) time using heap sort is
A. Θ(1)
−−
−
B. Θ(√logn)
C. Θ( logloglogn n )
D. Θ(log n)
Answer
Which one of the following is the tightest upper bound that represents the number of swaps required
to sort n numbers using selection sort?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n2 )
Answer
Let P be quicksort program to sort numbers in ascending order using the first element as the pivot.
Let t1 and t2 be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2]
respectively. Which one of the following holds?
A. t1 =5
B. t1 < t2
C. t1 > t2
D. t1 = t2
gate2014-1 algorithms sorting easy
Answer
Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They
are to be merged into a single sequence by merging together two sequences at a time. The number
of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
gate2014-2 algorithms sorting normal numerical-answers
Answer
You have an array of n elements. Suppose you implement quicksort by always choosing the central
element of the array as the pivot. Then the tightest upper bound for the worst case performance is
A. O(n2 )
B. O(n log n)
C. Θ(n log n)
D. O(n3 )
Answer
Which one of the following is the recurrence equation for the worst case time complexity of the quick
sort algorithm for sorting n ( ≥ 2) numbers? In the recurrence equations given in the options below,
c is a constant.
A. T (n) = 2T (n/2) + cn
B. T (n) = T (n − 1) + T (1) + cn
C. T (n) = 2T (n − 1) + cn
D. T (n) = T (n/2) + cn
Answer
Suppose you are provided with the following function declaration in the C programming language.
The function treats the first element of a[ ] as a pivot and rearranges the array so that all elements
less than or equal to the pivot is in the left part of the array, and all elements greater than the pivot
is in the right part. In addition, it moves the pivot so that the pivot is the last element of the left
part. The return value is the number of elements in the left part.
The following partially given function in the C programming language is used to find the kth smallest
element in an array a[ ] of size n using the partition function. We assume k ≤ n .
Answer
Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64.
Which of the following most closely approximates the maximum input size of a problem that can be
solved in 6 minutes?
A. 256
B. 512
C. 1024
D. 2018
gate2015-3 algorithms sorting
Answer
The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are:
Answer
Assume that the algorithms considered here sort the input sequences in ascending order. If the
input is already in the ascending order, which of the following are TRUE?
A. I and II only
B. I and III only
C. II and IV only
D. I and IV only
Answer
Give a strategy to sort four given distinct integers a, b, c, d in increasing order that minimizes the
number of pairwise comparisons needed to sort any permutation of a, b, c, d.
descriptive isi2011 algorithms sorting
Answer
Suppose you are given n numbers and you sort them in descending order as follows:
First find the maximum. Remove this element from the list and find the maximum of the remaining
elements, remove this element, and so on, until all elements are exhausted. How many comparisons
does this method require in the worst case?
A. Linear in n.
B. O (n2 ) but not better.
C. O (n log n)
D. Same as heap sort.
E. O (n1.5 ) but not better.
Answer
Consider the Insertion Sort procedure given below, which sorts an array L of size n (≥ 2) in
ascending order:
begin
for xindex:= 2 to n do
x := L [xindex];
j:= xindex - 1;
while j > 0 and L[j] > x do
L[j + 1]:= L[j];
j:= j - 1;
end {while}
L [j + 1]:=X;
end{for}
end
It is known that insertion sort makes at most n(n − 1)/2 comparisons. Which of the following is
true?
Answer
LetS = {x1 , . . . . , xn } be a set of n numbers. Consider the problem of storing the elements of S in
an array A [1...n] such that the following min-heap property is maintained for all
2 ≤ i ≤ n : A[⌊i/2⌋] ≤ A[i]. (Note that ⌊x⌋ is the largest integer that is at most x). Which of the
following statements is TRUE?
Answer
Given a set of n = 2k distinct numbers, we would like to determine the smallest and the second
smallest using comparisons. Which of the following statements is TRUE?
Answer
The first n cells of an array L contain positive integers sorted in decreasing order, and the
remaining m − n cells all contain 0. Then, given an integer x, in how many comparisons can one
find the position of x in L?
Answer
An array A contains n integers. We wish to sort A in ascending order. We are told that initially no
element of A is more than a distance k away from its final position in the sorted list. Assume that n
and k are large and k is much smaller than n. Which of the following is true for the worst case
complexity of sorting A?
A. A can be sorted with constant . kn comparison but not with fewer comparisons.
B. A cannot be sorted with less than constant . n log n comparisons.
C. A can be sorted with constant . n comparisons.
D. A can be sorted with constant . n log k comparisons but not with fewer comparisons.
E. A can be sorted with constant . k2 n comparisons but not fewer.
tifr2012 algorithms sorting
Answer
Consider the quick sort algorithm on a set of n numbers, where in every recursive subroutine of the
algorithm, the algorithm chooses the median of that set as the pivot. Then which of the following
statements is TRUE?
Answer
Suppose n processors are connected in a linear array as shown below. Each processor has a
number. The processors need to exchange numbers so that the numbers eventually appear in
ascending order (the processor P1 should have the minimum value and the the processor Pn should
have the maximum value).
The algorithm to be employed is the following. Odd numbered processors and even numbered
processors are activated alternate steps; assume that in the first step all the even numbered
processors are activated. When a processor is activated, the number it holds is compared with the
number held by its right-hand neighbour (if one exists) and the smaller of the two numbers is
retained by the activated processor and the bigger stored in its right hand neighbour.
How long does it take for the processors to sort the values?
A. n log n steps
B. n2 steps
C. n steps
D. n1.5 steps
E. The algorithm is not guaranteed to sort
Answer
An array of n distinct elements is said to be un-sorted if for every index i such that 2 ≤ i ≤ n − 1 ,
either A[i] > max{A[i − 1], A[i + 1]}, or A[i] < min{A[i − 1], A[i + 1]}. What is the time-
complexity of the fastest algorithm that takes as input a sorted array A with n distinct elements,
and un-sorts A?
Answer
Answers: Sorting
Selected Answer
0,5,1,4,3,2
What I will do is, I will take all plates from 5 to 2 (5, 1, 4, 3, 2) I hold them in my hand, rotated
my hand 180 degree & put it back.
0, 2, 3, 4, 1, 5
Now I will rotate all.
5, 1, 4, 3, 2, 0
5, 4 |, 3, 2, 0, 1
Now 4 is at its right place.
Next maximum is 3, it is at its right place, so we may add one more line in the code to reduce
steps...
Otherwise, the same algo will also keep 3 at it's right place.
The same algo will sort them at last.
Selected Answer
n/2k = 1 ..
k = log2 n .
So, total cost will be log n ∗ (nm)
Selected Answer
A stable sort preserves the order of values that are equal with respect to the comparison
function.
That is whenever we compare two keys(values) for sorting and if they are equal, the order in which
they will appear in the sorted list is same as they appeared in the original list. That is, if we have
x1 and x2 in our list, such that x1 = x2 (they are equal when compared) and x1 appeared before
x2 in the list (our list is something like: . . . , x1 , . . . , x2 , . . . ).
Then the sorted list will be like: . . . , x1 , x2 , . . . and NOT like: . . . , x2 , x1 , . . . . That is, in the
sorted list x1 comes before x2 . Then such a sort is known to be stable.
[Link]
it-important
[(7, 1, 8), (3, 5, 7), (6, 1, 4), (6, 5, 9), (0, 2, 5), (9, 0, 9)]
is sorted in ascending order by the second coordinate. We have to compare second coordinate to
get the ordering.
(c)
[(9, 0, 9), (7, 1, 8), (6, 1, 4), (0, 2, 5), (3, 5, 7), (6, 5, 9)]
Notice here that when compared, (7, 1, 8) is equal to (6, 1, 4) (compare second coordinates). So,
in the sorted list (7, 1, 8) comes before (6, 1, 4), same order as in original list.
Selected Answer
ACTUALLY IN BOTH THE CASES IT WILL TAKE O(n2 ) TIME (O(n) TIME FOR PARTITION
ALGORITHM AND T (n − 1) TIME FOR SUB PROBLEM. AS n IS THE NUMBER OF INPUTS AND IN
THE 2ND CASE INPUTS ARE 5(GREATER THAN 1ST ONE THAT IS 4) I THINK t1 < t2
Selected Answer
Answer is LESS.
As worst case time for Quicksort is O(n2 ) and worst case for heap sort is O(n log n).
Selected Answer
Answer is 7.
Selected Answer
[Link]
Selected Answer
For example, for decimal system, b is 10. What is the value of d? If k is the maximum possible
value, then d would be O(logb (k)). So overall time complexity is O((n + b) ∗ logb (k)). Which
looks more than the time complexity of comparison based sorting algorithms for a large k. Let us
first limit k. Let k ⩽ nc where c is a constant. In that case, the complexity becomes
O(n logb (n)). But it still does not beat comparison based sorting algorithms.
What if we make value of b larger?. What should be the value of b to make the time complexity
linear? If we set b as n then we will get the time complexity as O(n).
In other words, we can sort an array of integers with range from 1 to nc , If the numbers are
represented in base n (or every digit takes log2 (n) bits).
Reference: [Link]
Selected Answer
Selected Answer
Answer: Option C.
Selected Answer
Answer: Option C.
The number of moves are however always m + n so that we can term it as Θ(m + n). But the
number of comparisons vary as per the input. In the best case the comparisons are Min(m, n)
and in worst case they are m + n − 1 .
Selected Answer
Answer: Option C.
Selected Answer
1st Pass: 37 52 12 11 25 92
2nd Pass: 37 12 11 25 52 92
3rd Pass: 12 11 25 37 52 92
4th Pass: 11 12 25 37 52 92
5th Pass: 11 12 25 37 52 92
Selected Answer
i=1;j=1; a[i][j]=x;
while ((x>a[i+1][j]) || (x>a[i][j+1]))
{
if((a[i+1][j] < x) && (a[i+1][j] <a[i][j+1]))
{
a[i][j]=a[i+1][j];
i=i+1;
}
else
{
a[i][j]=a[i][j+1];
j=j+1;
}
}
a[i][j]=x;
Selected Answer
C.
both are the worst cases of quick sort. (assuming pivot is either first or last element)
Selected Answer
Note: if we use O(n2 ) for Insertion sort, we will not be having any suitable choice to fill selection
sort. So, we can assume that the question is asking for best case time complexities.
Selected Answer
Selected Answer
20 47 15 8 9 4 40 30 12 17
\ / \ / \ / \ / \ /
20 47 8 15 49 30 40 12 17 after 1st pass
\ / \ / \ /
\ / \ / \/
8, 15, 20, 47 4, 9, 30, 40 12, 17 after 2nd pass
Answer is B.
Selected Answer
Selected Answer
Since swaps are needed to be of adjacent elements only, the algorithm is actually Bubble sort.
In bubble sort, all smaller elements to right of an element are required to be swapped. So, if have
ordering
[2, 2, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0], then we need total 47 swaps, and this will be the worst case.
So, it answers actually both parts.
Selected Answer
1. When all elements are same in the input array, Partition algo will divide input array in two sub-
array, one with n − 1 elements and second with 0 element. There is an assumption here that,
we are using the same partition algorithm without any modification.
2. If the randomised pivot selector happens to select e.g. the smallest element N times in a row,
we will get the worst possible performance. Though the probability of this particular case is
1
about n! "
PS:- If the partitioning is unbalanced, Quick Sort algorithm runs asymptotically as slow as
Insertion Sort i.e O(n2 )
Selected Answer
(worst case) n comparisons for searching the right position, and n swaps to make room to place
the element.
(worst case) log n comparisons for searching the right position, and n swaps to make room to
place the element.
Hence for n elements, a total of n × (log n + n) ; n for search and n for swaps.
= Θ(n × log n + n2 ) = Θ(n2 )
Hence, answer is A.
Selected Answer
They are asking the average number of inversion. basically what i learned about averages from
dbms indexing is.
Aaverage apart from the standard definition can be calculated as (best case + worst case)/2
and inversion is like 9, 5.
So, best case will be sorted array −1, 2, 3, 4, 5 no inversion .= zero
worst case = 9, 5, 4, 3, 2, 1 . here total number of inversion will be n(n − 1)/2 as . 9 can be
paired with any 5 elements (5, 4, 3, 2, 1) will form a inversion pair. similarly 5 with [Link] .
So, expected average number of inversion = (n(n − 1)/2 + zero(best case))/2 = n(n − 1)/4
So, option is B.
Second question.
we all know that insertion sort has complexity due to swapping and movements, if we have n n
inversion pair then the movements and comparison will be restricted to n only . like if inversion is
1 , then array must be sorted and only the inversion should exist at the end, like 1, 2, 3, 5, 4.
Selected Answer
ANSWER: D. Θ(n)
REASON:
Count of number of times the inner loop of insertion sort executes is actually equal to number of
inversions in input permutation a1 , a2 , … an . Since for each value of i = 1...n, j take the value
1...i − 1, which means for every j < i it checks if a[j] > a[i].
In any given permutation, maximum number of inversions possible is n(n − 1)/2 which is O(n2 ).
It is the case where the array is sorted in reverse order. Therefore, to resolve all inversions i.e.,
worst case time complexity of insertion sort is Θ(n2 ).
However, as per the question the number of inversion in input array is restricted to n. The worst
case time complexity of insertion sort reduces to Θ(n).
Selected Answer
For comparison-based sorting the asymptotically tight bound for worst case is given by
Θ(n log n), which means it is the tightest upper bound (big O) as well as the tightest lower bound
(big omega). So, answer is n log n.
Tightest lower bound of sorting (say S(n)) is n log n means there is no function f which has an
order of growth larger than n log n and f(n) = Ω(S(n)) holds.
A usual mistake is to think worst case changes with lower and upper bounds, but that is not the
case. Worst case is defined for the algorithm and it is always the input which causes the algorithm
the maximum complexity.
Selected Answer
Since we have log n lists we can make a min-heap of log n elements by taking the first element
from each of the log n sorted lists. Now, we start deleting the min-element from the heap and put
the next element from the sorted list from which that element was added to the heap. (This
identity can be done by making a structure of two values, one for the number and one for
identifying the origin sorted list of that number and storing this structure in the heap). In this way
O(log log n)
© Copyright GATE Overflow. All rights reserved.
192 1 Algorithms (323)
each delete and the corresponding insert will take O(log log n) time as delete in heap of size n is
O(log n) and inserting an element on a heap of size n is also O(log n). (here, heap size is log n).
Now, we have a total of log n × logn n = n elements. So, total time will be O(n log log n).
Selected Answer
a[i] ≥ b[i]
Since both a and b are sorted in the beginning, there are i elements smaller than or equal to a[i](i
starts from 0), and similarly i elements smaller than or equal to b[i]. So, a[i] ≥ b[i] means there
are 2i elements smaller than or equal to a[i], and hence in the merged array a[i] will come after
these 2i elements (its index will be > 2i). So, c[2i] ≤ a[i] (equality takes care of the "equal to"
case which comes when array contains repeated elements).
Similarly, a[i] ≥ b[i] says for b that, there are not more than 2i elements smaller than b[i] in the
sorted array (i elements from b, and maximum another i elements from a). So, b[i] ≤ c[2i]
Selected Answer
Selection sort.
Because in selection the maximum swaps which can take place are O(n)
Because we pick up an element an find the minimum (in case of forward sorting) from the next
index till the end of array and than perform the swap
Hence, O(n) whereas in all other algos the swaps are greater ( considering Worst-Case scenario )
19 votes -- ANKUR MAHIWAL (411 points)
Selected Answer
As we choose the pivot a median element ... so, every time we are going to have good splits
guaranteed so the best case O(n log n).
Selected Answer
A.
Irrespective of the input, merge sort always have a time complexity of Θ(n log n).
Selected Answer
Selected Answer
Answer: C
The complexity of Radix Sort is O(wn), for n keys which are integers of word size w.
Here, w = log2 (nk ) = k × log2 (n)
So, the complexity is O(wn) = O(k × log2 (n) × n), which leads to option C.
Selected Answer
The answer is A.
we have 1 swap in each loop and hence n swaps at max for 1 to n. Therefore the worst case
number of swaps is Θ(n)
Selected Answer
Answer is B.
Selected Answer
you are given the first character of each n strings to sort it will take O(n log n) time..in the worst
case we may have to do the above process 2 times,3 times,........,n times so
n ∗ O(n log n) = O(n2 log n) please correct me if my approach is wrong...
39 votes -- Bhagirathi Nayak (14.1k points)
Selected Answer
log n
To sort k elements in a heap, complexity is Θ(k log k). Lets assume there are log log n
elements in
the heap.
Selected Answer
In selection max you can do is n swaps..selecting the smallest element from all the elements and
replacing it correct position so O(n)
Selected Answer
it would be t1 > t2 , because the first case is the worst case of quicksort i.e. minimum number is
chosen as pivot. Hence in the worst case the comparisons are high.
[123][45]
[1][23][4][5]
[2][3]
Number of recursive calls remain the same, but in second case the number of elements passed for
the recursive call is less and hence the number of comparisons also less.
Selected Answer
The optimal algorithm always chooses the smallest sequences for merging.
20 24 − 44, 43 comparisons
30 35 − 65, 64 comparisons
44 50 − 94, 93 comparisons
65 94 − 159, 158 comparisons
so, totally 43 + 64 + 93 + 158 = 358 comparisons.
PS: In merge operation we do a comparison of two elements and put one element in the sorted
output array. So, every comparison produces one output element. But for the last element we
won't need a comparison and we simply insert it to the output array. So for n output elements we
need (n − 1) comparisons.
Selected Answer
(A) O(n2 ) is the answer. When we choose the first element as the pivot, the worst case of quick
sort comes if the input is sorted- either in ascending or descending order. Now, when we choose
the middle element as pivot, sorted input no longer gives worst case behavior. But, there will be
some permutation of the input numbers which will be giving the same worst case behavior. For
example,
1234567
This array gives worst case behavior for quick sort when the first element is pivot.
6421357
This array gives the worst case behavior of O(n2 ) if we take middle element as the pivot- each
split will be 1 element on one side and n − 1 elements on other side. Similarly, for any input, we
can have a permutation where the behavior is like this. So, whichever element we take as pivot it
gives worst case complexity of O(n2 ) as long as pivot is from a fixed position (not random position
as in randomized quick sort).
Selected Answer
B.
Worst case for quick sort happens when 1 element is on one list and n − 1 elements on another
list.
Selected Answer
First of all, here the return value is the number of elements less than the pivot
So, in STEP 1 and STEP 2 'else' condition satisfying, and STEP 3 and STEP 4 'if ' condition satisfying
Selected Answer
The worst case time complexity of Mergesort is k × n log n for an input of size n.
For an input of size 64, the algorithm takes 30s. Therefore,
k × 64 log2 64 = 30s
k × 384 = 30s
⟹ k = 0.078125s
Let the size of the problem that can be solved in 6 minutes be x. Then,
k × x log2 x = 360s
360s
x log2 x =
0.078125s
⟹ x = 512
Selected Answer
Answer is D.
Selected Answer
III. Mergesort never takes more than Q(N log N) This is false
IV. This is true. Insertion sort will finish in Q(N) time in case of sorted input.
a, b, c, d
1 + 1 comparisons for lowest step
+3 comparisons for upper one
So, total 5 comparisons
Selected Answer
The given procedure resembles something like Bubble sort or Selection Sort.
Every time, for every input it will take O(n2 ) so, B is the answer.
If you are thinking about heap sort, where in the procedure, it is talked about building a heap?
You can do extract_max only on a heap. Right ? The procedure is nearly same as bubble sort or
selection sort.
Read qsn again: "First find the maximum. Remove this element from the list and find the
maximum of the remaining elements, remove this element, and so on, until all elements are
exhausted."
Just follow the steps. Find max, take it to right side of array. Shift.
So n − 1 comparisons & n − 1 shifts in the worst case.
Total n − 1 + n − 2 + n − 3+. . . . +1 + n − 1 + n − 2 + n − 3+. . +1 which is O(n2 )
Only number of comparisons is asked... which is also O(n2 )
Selected Answer
In worst case Insertion sort will have n(n − 1)/2 comparisons i.e. when input is sorted in
descending order.
50 40 30 20 10 … n
pass 1: 50 40 30 20 10 … n 0 comparison
pass 2: 40 50 30 20 10 … n 1 comparison
.
.
.
.
pass n: n … 10 20 30 40 50 n − 1 comparisons
Total 1 + 2 + 3 + … + n − 1 = n(n − 1)/2 comparisons
Selected Answer
store the elements in an array and then call build_heap(A). the build_heap takes O(n) time.
but, if we try building heap by inserting each element one by one, the total complexity will be then
O(n log n). cause insertion takes O(log n) and inserting 'n' elements will take O(n log n).
Selected Answer
it is solution to the problem known for ages, and it has to do with tennis tournaments. The
question was, knowing the outcome of the tennis tournament, how can we tell which player
was the second best? The defeated finalist is a good candidate, but there are other players
that were defeated directly by the tournament winner and any of them could also be a good
candidate for the second best. So the solution to the problem is quite simple: Once the
tournament finishes, pick up the log N competitors that were beaten by the tournament
winner and hold a mini-tournament to find which one is the best among them. If we imagine
that better players correspond with smaller numbers, the algorithm now goes like this. Hold
the tournament to find the smallest number (requires N − 1 comparisons). During this step,
for each number construct the list of numbers it was smaller than. Finally, pick the list of
numbers associated with the smallest number and find their minimum in log N − 1 steps.
This algorithm requires N + log N − 2 comparisons to complete, but unfortunately it
requires additional space proportional to N (each element except the winner will ultimately
be added to someone’s list); it also requires more time per step because of the relatively
complex enlisting logic involved in each comparison. When this optimized algorithm is
applied to example array, we get the following figure.
Tournament held among numbers promotes value 1 as the smallest number. That operation,
performed on an array with nine numbers, requires exactly eight comparisons. While
promoting the smallest number, this operation has also flagged four numbers that were
removed from competition by direct comparison with the future winner: 6, 2, 3 and 8 in that
order. Another sequence of three comparisons is required to promote number 2 as the
second-smallest number in the array. This totals 11 comparisons, while naive algorithm
requires 17 comparisons to come up with the same result.
All in all, this algorithm that minimizes number of comparisons looks to be good only for real
tournaments, while number cracking algorithms should keep with the simple logic explained
above. Implementation of simple algorithm may look like this:
Selected Answer
(d)
O(log n) comparisons suffice.
O(n)
© Copyright GATE Overflow. All rights reserved.
202 1 Algorithms (323)
Since it is possible that m ⋙ n, we need to restrict ourselves to the first O(n) elements to
perform the binary search.
We start with the first element (index i = 1), and check if it is equal to 0. If not, we double the
value of i, and check again. We repeat this process until we hit a 0.
i = 1;
while(arr[i] != 0)
i *= 2;
Once we hit a 0, the largest possible value (worst case) of i can be 2n − 2. This will happen if
n = 2k + 1 for some k. Then, our 2nd last value of i will be 2k , and then we get 2k+1 , which is
equal to 2n − 2.
Now that we've hit a 0, and the array contains positive numbers in decreasing order, if x is present
in L, it must be in the first i elements.
Since the largest possible value of i = 2n − 2 , our algorithm takes O(log(2n − 2)) = O(log n)
comparisons.
Selected Answer
Let Array element be {4, 3, 2, 1, 7, 5, 6, 9, 10, 8} and K be 3 here no element is more than 3
distance away from its final position
So if we take
arr(1 to 6) and sort then surely first three element will be sorted in its final position
{12345769108} O(6 log 6)
then sort arr(3 to 9) then 3 to 6 will be sorted {12345679108} O(6 log 6)
then at last arr(6 to 9) less than O(6 log 6) {12345678910}
in general
Sort arr(0 to 2k)
Now we know that arr[0 to k) are in their final sorted positions
and arr(k to 2k) may be not sorted.
Selected Answer
Median at
( n2 −1) (n− n2 )
2 th
n
elements elements
location
= Θ(n log n)
Answer: C.
Selected Answer
A pairwise swap will make the sorted array unsorted. Hence, the option (B) is correct.
Choose the correct alternatives (more than one may be correct) and write the corresponding letters
only:
Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and
m edges has the time complexity of:
A. O(n2 )
B. O(mn)
C. O(m + n)
D. O(m log n)
E. O(m2 )
Answer
Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph
containing n vertices and m edges if the edges are sorted is _______
gate1992 spanning-tree algorithms time-complexity easy
Answer
How many minimum spanning trees does the following graph have? Draw them. (Weights are
assigned to edges).
Answer
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
Answer
Consider a graph whose vertices are points in the plane with integer co-ordinates (x, y) such that
1 ≤ x ≤ n and 1 ≤ y ≤ n, where n ≥ 2 is an integer. Two vertices (x1 , y1 ) and (x2 , y2 ) are
adjacent iff ∣x1 − x2 ∣≤ 1 and ∣ y1 – y2 ∣≤ 1 . The weight of an edge
−−−−−−−−−−−−−−−−
{(x1 , y1 ), (x2 , y2 )} is √(x1 – x2 )2 + (y1 – y2 )2
A. What is the weight of a minimum weight-spanning tree in this graph? Write only the answer
without any explanations.
B. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer
without any explanations.
Answer
Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with
maximum weight and emin the edge with minimum weight. Which of the following statements is
false?
Answer
Consider a weighted undirected graph with vertex set V = {n1, n2, n3, n4, n5, n6} and edge set
E = {(n1, n2, 2), (n1, n3, 8), (n1, n6, 3), (n2, n4, 4), (n2, n5, 12), (n3, n4, 7), (n4, n5, 9), (n4, n
© Copyright GATE Overflow. All rights reserved.
206 1 Algorithms (323)
E = {(n1, n2, 2), (n1, n3, 8), (n1, n6, 3), (n2, n4, 4), (n2, n5, 12), (n3, n4, 7), (n4, n5, 9), (n4, n
The third value in each tuple represents the weight of the edge specified in the tuple.
Answer
A. 29
B. 31
C. 38
D. 41
gate2003 algorithms spanning-tree normal
Answer
An undirected graph G has n nodes. its adjacency matrix is given by an n × n square matrix whose
(i) diagonal elements are 0’s and (ii) non-diagonal elements are 1’s. Which one of the following is
TRUE?
Answer
Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there
is a minimum weight spanning tree in G containing the edge e. Which of the following statements is
always TRUE?
Answer
Consider a weighted complete graph G on the vertex set {v1 , v2 , . . . . . vn } such that the weight of
the edge (vi , vj ) is 2|i − j| . The weight of a minimum spanning tree of G is:
A. n−1
B. 2n − 2
( )
n
C.
2
2
D. n
gate2006 algorithms spanning-tree normal
Answer
Which one of the following cannot be the sequence of edges added, in that order, to a minimum
spanning tree using Kruskal’s algorithm?
Answer
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a
specific edge of weight w. Which of the following is FALSE?
Answer
For the undirected, weighted graph given below, which of the following sequences of edges
represents a correct execution of Prim's algorithm to construct a Minimum Spanning Tree?
A. (a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)
B. (c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)
C. (d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)
D. (h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)
Answer
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using
Kruskal’s algorithm?
Answer
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W
below is the weight of the edge {i, j}
⎛0 1 8 1 4⎞
⎜1 0 9⎟
⎜ ⎟
12 4
W =⎜
⎜ 3⎟
⎟
⎜ ⎟
8 12 0 7
⎜1 4 7 0 2⎟
⎝4 9 3 2 0⎠
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf
node in the tree T ?
A. 7
B. 8
C. 9
D. 10
gate2010 algorithms spanning-tree normal
Answer
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W
below is the weight of the edge {i, j}
⎛0 1 8 1 4⎞
⎜1 0 9⎟
⎜ ⎟
12 4
W =⎜
⎜ 3⎟
⎟
⎜ ⎟
8 12 0 7
⎜1 4 7 0 2⎟
⎝4 9 3 2 0⎠
What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that
P contains at most 3 edges?
A. 7
B. 8
C. 9
D. 10
gate2010 normal algorithms spanning-tree
Answer
What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?
1
A. 12 (11n2 − 5n)
B. n2 − n + 1
C. 6n − 11
D. 2n + 1
Answer
The length of the path from v5 to v6 in the MST of previous question with n = 10 is
A. 11
B. 25
C. 31
D. 41
gate2011 algorithms graph-algorithms spanning-tree normal
Answer
Let G be a weighted graph with edge weights greater than one and G′ be the graph constructed
by squaring the weights of edges in G. Let T and T ′ be the minimum spanning trees of G and
G′ , respectively, with total weights t and t′ . Which of the following statements is TRUE?
A. T ′ = T with total weight t′ = t2
B. T ′ = T with total weight t′ < t2
C. T ′ ≠ T but total weight t′ = t2
D. None of the above
Answer
The number of distinct minimum spanning trees for the weighted graph below is _____
Answer
The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree
(MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The
edge weights of only those edges which are in the MST are given in the figure shown below. The
minimum possible sum of weights of all 8 edges of this graph is_______________.
Answer
Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum
spanning tree of G is 500. When the weight of each edge of G is increased by five, the weight of a
minimum spanning tree becomes ______.
gate2015-3 algorithms spanning-tree easy numerical-answers
Answer
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge
weight is increased by the same value, then which of the following statements is/are TRUE?
Answer
Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5,
a n d 6. The maximum possible weight that a minimum weight spanning tree of G can have is
__________
gate2016-1 algorithms spanning-tree normal numerical-answers
Answer
G = (V , E) is an undirected simple graph in which each edge has a distinct weight, and e is a
particular edge of G. Which of the following statements about the minimum spanning trees
(MST s) of G is/are TRUE?
I. If e is the lightest edge of some cycle in G, then every MST of G includes e.
II. If e is the heaviest edge of some cycle in G, then every MST of G excludes e.
A. I only.
B. II only.
C. Both I and II.
D. Neither I nor II.
Answer
Let G be a connected simple graph (no self-loops or parallel edges) on n ≥ 3 vertices, with distinct
edge weights. Let e1 , e2 , . . . , em be an ordering of the edges in decreasing order of weight. Which
of the following statements is FALSE?
Answer
In a connected weighted graph with n vertices, all the edges have distinct positive integer
weights. Then, the maximum number of minimum weight spanning trees in the graph is
a. 1
b. n
c. equal to number of edges in the graph.
d. equal to maximum weight of an edge of the graph.
e. nn−2
tifr2013 spanning-tree
Answer
Consider the following undirected graph with some edge costs missing.
Suppose the wavy edges form a Minimum Cost Spanning Tree for G. Then, which of the following
inequalities NEED NOT hold?
a. cost(a, b) ≥ 6.
b. cost(b, e) ≥ 5.
c. cost(e, f) ≥ 5.
d. cost(a, d) ≥ 4.
e. cost(b, c) ≥ 4.
Answer
Let G = (V , E) be an undirected connected simple (i.e., no parallel edges or self-loops) graph with
the weight function w : E → R on its edge set. Let w(e1 ) < w(e2 ) < ⋅ ⋅ ⋅ < w(em ) , where
E = {e1 , e2 , . . . , em } . Suppose T is a minimum spanning tree of G. Which of the following
statements is FALSE?
Answer
Consider the following undirected connected graph G with weights on its edges as given in the figure
below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is
one with largest weight. A second best minimum spanning tree whose weight is the smallest among
all spanning trees that are not minimum spanning trees in G.
Which of the following statements is TRUE in the above graph? (Note that all the edge weights are
distinct in the above graph)
A. There is more than one minimum spanning tree and similarly, there is more than one maximum
spanning tree here.
B. There is a unique minimum spanning tree, however there is more than one maximum spanning
tree here.
C. There is more than one minimum spanning tree, however there is a unique maximum spanning
tree here.
D. There is more than one minimum spanning tree and similarly, there is more than one second-
best minimum spanning tree here.
E. There is unique minimum spanning tree, however there is more than one second-best minimum
spanning tree here.
Answer
Selected Answer
Answer: D, B, E.
When Union- Find algorithm is used to detect cycle while constructing the MST time complexity is
O(m log n) where m is the number of edges, and n is the number of vertices. Since n = O (m2 )
in a graph, options B and E are also correct as big-O specifies asymptotic upper bound only.
Reference: [Link]
tree-mst/
Selected Answer
If all edges are already sorted then this problem will reduced to union-find problem on a graph with
E edges and V vertices.
for each edge (u,v) in E
if(FIND-SET(u) != FIND-SET(v))
UNION(u,v)
Selected Answer
2 only.
{AB, BC, AE, BD} and {AB, BC, AE, CD}.
Selected Answer
(A).
(B).
Selected Answer
The cost of the edge between the vertices (2, 3) and (2, 2) = 1 and the cost of the edge
between the vertices (2, 2) and (2, 1) = 1.
There is no problem with minimum spanning tree. We have n2 vertices so, the minimum spanning
tree contains n2 − 1 edges of cost 1. So, the cost of the minimum spanning tree is n2 − 1 .
–
In this maximum spanning tree of n2 −1 edges n2 −2 edges is of cost √2 and 1 edge is of cost
1.
–
So, the answer is √2 (n2 − 2) + 1 .
This pattern continues for high values of n.
For n = 4, the maximum spanning tree is:
(one of possibilities)
For n = 4, 16 vertices are there and the maximum spanning tree requires 15 edges. Out of 15
– –
edges, 14 edges are of cost √2 and 1 edge is of cost 1. Thus satisfying the formula √2 (n2 − 2)
+1.
The cost of Minimum spanning tree is: n2 − 1 .
–
The cost of Maximum spanning tree is: (n2 − 1) √2 + 1 .
Selected Answer
D will always be true as per the question saying that the graph has distinct weights.
Selected Answer
b) no of distinct minimum spanning tree: 2 (2nd with the different edge of weight 4)
c) yes
d) yes
Selected Answer
add all the weights in the given figure which would be equal to 31.
Selected Answer
Selected Answer
Option A is correct.
Questions says the MST of graph G contain an edge e which is a maximum weight edge in G.
Need to choose the answer which is always true to follow the above constraint.
Case 1:
Option B says tht if edge e ia in MST then for sure there is a cycle having all edges of
maximum weight. But it is not true always because when there is only n-1 edges( but no
cycle) in graph then also maximum edge has to be taken for MST.
Case 2:
Option C says otherwise. That if e is in MST then it cannot be in any cycle that is wrong as if there
is a cycle with all maximum edges then also e will be in MST
Option D says all edges should be of same weight same explanation if there are n − 1 distinct
edges( but no cycle) in G then have to take all edges including maximum weight edge.
And at last option A says if e is in MST then for sure there is a cut-set ( minimum edge set
whose removal disconnects the graph) in G having all edges of maximum weight. And it
is true.
For eg. If there are n − 1 edges (but no cycle) then if edge e is not taken in the MST then MST will
not be connected.
Selected Answer
2(n − 1) the spanning tree will traverse adjacent edges since they contain the least weight.
22 votes -- anshu (3.3k points)
Selected Answer
In kruskal's algo the edges are added in non decreasing order of their weight. But in Option D edge
d − e with weight 3 is added before edge d − c with weight [Link], option D is wrong option.
Selected Answer
A minimum spanning tree must have the edge with the smallest weight (In Kruskal's algorithm we
start from the smallest weight edge). So, C is TRUE.
If e is not part of a minimum spanning tree, then all edges which are part of a cycle with e, must
have weight ≤ e, as otherwise we can interchange that edge with e and get another minimum
spanning tree of lower weight. So, B and A are also TRUE.
Selected Answer
Prim's algorithm starts with from any vertex and expands the MST by adding one vertex in each
step which is close to the Intermediate MST(made till previous step).
(A): (d, f) is chosen but neither d nor f vertices are part of the previous MST(MST made till
previous step).
(B): (g, h) is chosen but neither g or h vertices are part of the previous MST(MST made till
previous step).
(D): (f, c) is chosen but at that point (f, d) is close to the intermediate MST.
Selected Answer
In Option D b-c with weight, 4 is added before a-c with weight 3 is added. In Kruskal's algorithm,
edges should be added in non-decreasing order of weight.
Selected Answer
Answer is (D) 10. The edges of the spanning tree are: 0 − 1, 1 − 3, 3 − 4, 4 − 2 . Total Weight
= 10
Selected Answer
Selected Answer
Q 54. Answer is B.
For n=4 (1 + 2 + 3 + 4) + (1 + 2)
For n=5 (1 + 2 + 3 + 4 + 5) + (1 + 2 + 3)
These can be obtained by drawing graphs for these graphs.
2
∴ Total weight of MST is ∑ni=1 i + ∑n−2
i=1 i = n − n + 1
Selected Answer
Selected Answer
When the edge weights are squared the minimum spanning tree won't change.
t′ < t2 , because sum of squares is always less than the square of the sums except for a single
element case.
Hence, B is the general answer and A is also true for a single edge graph. Hence, in GATE 2012,
marks were given to all.
Selected Answer
6 is the answer.
2 × 3 = 6 possibilities
Selected Answer
Consider the cycle ABC. AC and AB are part of minimum spanning tree. So, AB should be
greater than max(AC, BC) (greater and not equal as edge weights are given to be distinct), as
otherwise we could add AB to the minimum spanning tree and removed the greater of AC, BC
and we could have got another minimum spanning tree. So, AB > 9.
= 33 + 36 = 69
51 votes -- Arjun Suresh (350k points)
Selected Answer
Selected Answer
Statement P is true.
The shortest path from A to C is A-C = 200, (A-B-C = 101 + 102 = 203)
Hence, option A is correct.
Selected Answer
Selected Answer
See counter example :- Here in below Graph G in (cycle 3, 4, 5) 3 is the lightest edge and still it is
not included in MST.
G 1−2−3
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 225
Statement 2: True by[ Cycle property of MST] : (in above Graph G 1 − 2 − 3 is a cycle and 3 is
the heaviest edge) If heaviest edge is in cycle then we will always exclude that bcz Cycle is their
means we can have other choice of low cost edges.
[Link]
1. For an edge to be INCLUDED in the MST,it must satisfy the CUT PROPERTY which states that
Assume that all edge costs are distinct. Let S be any subset of nodes that is neither empty nor
equal to all of V, and let edge e = (v, w) be the minimum cost edge with one end in S and the
other in V − S. Then every minimum spanning tree contains the edge e.
Now,in the given problem, e is the lightest edge of some cycle in G,but it may not be the lightest
edge connecting S and V - S. See the below image for clarification.
Here, e is the lightest edge of cycle [Link] are three edges e,e',e" connecting S and V - S.
e is obviously minimal weighted than e' since e' is part of the cycle C,but e MAY NOT be minimal
weighted than e" .
2. For an edge to be EXCLUDED from the MST, it must satisfy the CYCLE PROPERTY which states
that
Assume that all edge costs are distinct. Let C be any cycle in G, and let edge e = (v, w) be the
most expensive edge belonging to C. Then e does not belong to the minimum spanning tree of G.
ANSWER is B.
NOTE: For proofs of the above two properties, one can refer to the source of this answer:
Algorithm Design by Jon Kleinberg and Eva Tardos
Selected Answer
a) & c) are trivially true. Edge with max value e1 must be present in Maximum spanning tree &
same with minimum.
e) This is true, because all edge weights are distinct. maximum spanning tree is unique.
b) e1 & e2 must be present in Maximum spanning tree. I'll prove it using Kruskal Algorithm.
We will first insert weight with biggest value, e1 . Then we insert e2 (second highest) . 2 edges do
not create cycle. Then we can go on from there inserting edges according to edge weights. As they
have just asked for top 2 edges, using Kruskal Algo we can say that top 2 edges must be in
Maximum spanning tree.
d) This is false. There are chances that this em weight edge is cut edge(Bridge) Then it must be
inserted to from any spanning tree.
D is answer.
We can not say the same for Top 3 as they can create cycle & They we can not take a3 to make
spanning tree.
Selected Answer
There will be unique min weight spanning tree since all weights are distinct.
Option is A.
Selected Answer
Now check this diagram, this is forest obtained from above given graph using Kruskal's algorithm
for MST.
So, according to the question edge d − e has weight 5 and it is included in the formation of MST.
Now if edges b − e and e − f has weight greater than 5 than it is not a problem for our MST
because still we will get the given tree as Kruskal's algorithm takes the smallest weighted edge
without forming a cycle.
Cost of edge b − c ≥ 4 may also lead us to the same tree as above though Kruskal's algorithm will
have choice between c − f and b − c .
Now if the edge weight of a − d becomes 4, it is guaranteed that Kruskal's algorithm will not select
edge d − e because its edge cost is 5, and hence the tree structure will change. But there can be
the case where edge weight is greater than 4 and we still get the same tree (happens when
a − d ≥ 5 ). Because in the question they asked to point out an unnecessary condition this case is
not the answer as we need a − d ≥ 5 which implies a − d ≥ 4.
Now notice option A. Put a − b = 5. The given MST would not change. So, this condition is not
always necessary and hence is the answer.
Selected Answer
Answer is E. The catch here is edge-weights belongs to real number. Therefore, edge weight can
be negative. In that case the minimum spanning tree may be different.
e1= −5
e2 = 1
e3 = 2
T is:
e1 = 25
e2 = 1
e3 = 4
EDIT:
Option B is True. If we apply Kruskal's algorithm then it will also choose e2 , and 2 edges can not
form a cycle. (e3 is not guaranteed in MST, as it may form a cycle)
Option C is also true. If we apply Prims algorithm also on any vertex (say u), it chooses minimum
Selected Answer
In the graph we have all edge weights are distinct so we will get unique minimum and maximum
spanning tree.
Each Cycle must exclude maximum weight edge in minimum spanning tree.
Here, we have two cycle of 3 edges, a − d − e and c − g − k.
For second best minimum spanning tree, exclude a − e edge and include d − e edge
Other way for second best minimum spanning tree: exclude c − g edge and include g − k edge.
So, e should be the answer.
The number of times the test A[i] > A[position] is executed is:
A. 100
B. 5050
C. 10000
A
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 229
D. Depends on contents of A
cmi2013 algorithms time-complexity
Answer
How many times is the comparison i >= n performed in the following program?
int i=85, n=5;
main() {
while (i >= n) {
i=i-1;
n=n+1;
}
}
A. 40
B. 41
C. 42
D. 43
cmi2015 algorithms time-complexity
Answer
Consider the following function that takes as input a sequence A of integers with n elements,
A[A1], [A2] , … , [An]and an integer k and returns an integer value. The function length(S)
returns the length of sequence S. Comments start with //.
Answer
(A) O
(p) Heapsort
(log n)
(B) O
(n (q) Depth-first search
)
(C) O
(r) Binary search
(n log n)
(D) O
(s) Selection of the kth smallest element in a set of n elements.
(n2 )
gate1989 match-the-following algorithms time-complexity
Answer
A. O(n)
B. O(n2 )
C. O(n3 )
D. O(3n2 )
E. O(1.5n2 )
Answer
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
A. n − 1
B. n
C. n + 1
D. None of the above
Answer
A. log2 n
−
B. √n
C. n−1
D. n
gate1999 algorithms time-complexity normal
Answer
Consider the following algorithms. Assume, procedure A and procedure B take O(1) and O(1/n)
unit of time respectively. Derive the time complexity of the algorithm in O-notation.
Answer
L e t S be a sorted array of n integers. Let T (n) denote the time taken for the most efficient
algorithm to determined if there are two elements with sum less than 1000 in S. Which of the
following statement is true?
A. T (n) is O(1)
B. n ≤ T (n) ≤ n log2 n
C. n log2 n ≤ T (n) < n2
D. T (n) = ( n2 )
Answer
The cube root of a natural number n is defined as the largest natural number m such that
(m3 ≤ n) . The complexity of computing the cube root of n (n is represented by binary notation)
is
Answer
Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored
either in row-major or column-major order in contiguous memory locations. The time complexity of
an algorithm to compute M1 × M2 will be
Answer
Let A[1, … n] be an array storing a bit (1 or 0) at each location, and f(m) is a function whose time
complexity is Θ(m). Consider the following program fragment written in a C like language:
counter = 0;
for (i=1; i<=n; i++)
{ if a[i] == 1) counter++;
else {f (counter); counter = 0;}
}
A. Ω(n2 )
B. Ω(n log n) and O(n2 )
C. Θ(n)
D. o(n)
Answer
Consider the following C-program fragment in which i, j and n are integer variables.
for( i = n, j = 0; i > 0; i /= 2, j +=i );
Let val(j) denote the value stored in the variable j after termination of the for loop. Which one of
the following is true?
A. val(j) = Θ(log n)
B. val(j) = Θ(√−n)
C. val(j) = Θ(n)
D. val(j) = Θ(n log n)
Answer
[Link]
int j, n;
j = 1;
while (j <= n)
j = j * 2;
The number of comparisons made in the execution of the loop for any n > 0 is:
A. ⌈log2 n⌉ + 1
B. n
C. ⌈log2 n⌉
D. ⌊log2 n⌋ + 1
Answer
A. Θ(log2 n)
B. Ω(n)
C. Θ(log2 log2 n)
D. Θ(√−n)
Answer
A. Θ(n2 )
B. Θ(n log2 n)
C. Θ(log2 n)
D. Θ(log2 log2 n)
Answer
An array of n numbers is given, where n is an even number. The maximum as well as the minimum
of these n numbers needs to be determined. Which of the following is TRUE about the number of
comparisons needed?
Answer
Let T (n) denote number of times the for loop is executed by the program on input n. Which of the
following is TRUE?
Answer
Exponentiation is a heavily used operation in public key cryptography. Which of the following options
is the tightest upper bound on the number of multiplications required to compute
bn mod m, 0 ≤ b, n ≤ m ?
A. O(log n)
B. O(√−n)
C. O( logn n )
D. O(n)
Answer
Let P1 , P2 , … , Pn be n points in the xy-plane such that no three of them are collinear. For every
pair of points Pi and Pj , let Lij be the line passing through them. Let Lab be the line with the
steepest gradient among all n(n − 1)/2 lines.
A. Θ (n)
B. Θ (n log n)
C. Θ (n log2 n)
D. Θ (n2 )
Answer
The minimum number of comparisons required to determine if an integer appears more than n
2
times in a sorted array of n integers is
A. Θ(n)
B. Θ(log n)
C. Θ(log∗ n)
D. Θ(1)
Answer
We have a binary heap on n elements and wish to insert n more elements (not necessarily one after
another) into this heap. The total time required for this is
A. Θ(log n)
B. Θ(n)
C. Θ(n log n)
D. Θ(n2 )
Answer
int f1 (int n)
{
if(n == 0 || n == 1)
return n;
else
return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i-1] + Z[i-2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}
Answer
int f1 (int n)
{
if(n == 0 || n == 1)
return n;
else
return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i-1] + Z[i-2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}
Answer
Two alternative packages A and B are available for processing a database having 10k records.
Package A requires 0.0001n2 time units and package B requires 10n log10 n time units to process
n records. What is the smallest value of k for which package B will be preferred over A?
A. 12
B. 10
C. 6
D. 5
gate2010 algorithms time-complexity easy
Answer
Consider the following pseudo code. What is the total number of multiplications to be performed?
D = 2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D = D * 3
Answer
1 1
An algorithm performs (log N) 2 find operations , N insert operations, (log N) 2 delete operations,
1
a n d (log N) decrease-key operations on a set of data items with keys drawn from a linearly
2
ordered set . For a delete operation, a pointer is provided to the record that must be deleted . For
the decrease-key operation, a pointer is provided to the record that has its key decreased. Which
one of the following data structures is the most suited for the algorithm to use, if the goal is to
achieve the best total asymptotic complexity considering all the operations?
A. Unsorted array
B. Min - heap
C. Sorted array
D. Sorted doubly linked list
Answer
An unordered list contains n distinct elements. The number of comparisons to find an element in this
list that is neither maximum nor minimum is
A. Θ(n log n)
B. Θ(n)
C. Θ(log n)
D. Θ(1)
Answer
Answer
int fun(int n) {
int I, j;
for(i=1; i<=n; i++) {
for (j=1; j<n; j+=i) {
printf("%d %d", I, j);
}
}
}
Answer
It takes O(n) time to find the median in a list of n elements, which are not necessarily in sorted
order while it takes only O(1) time to find the median in a list of n sorted elements. How much time
does it take to find the median of 2n elements which are given as two lists of n sorted elements
each?
A. O(1)
B. O (log n) but not O(1)
C. O(√− n ) but not O (log n)
D. O(n) but not O(√− n)
E. O (n log n) but not O(n)
Answer
Let S be a set of numbers. For x ∈ S , the rank of x is the number of elements in S that are
less than or equal to x. The procedure Select(S, r) takes a set S of numbers and a rank
r (1 ≤ r ≤ |S|) and returns the element in S of rank r. The procedure MultiSelect(S, R) takes a
set of numbers S and a list of ranks R = {r1 < r2 < … < rk } , and returns the list
{x1 < x2 <. . . < xk } of elements of S, such that the rank of xi is ri . Suppose there is an
implementation for Select(S, r) that uses at most ‘‘ constant ·|S| " binary comparisons between
elements of S. The minimum number of comparisons needed to implement MultiSelect(S, R) is
Answer
Answer
Consider the following code fragment in the C programming language when run on a non-negative
integer n.
int f (int n)
{
if (n==0 || n==1)
return 1;
else
return f (n - 1) + f(n - 2);
}
Assuming a typical implementation of the language, what is the running time of this algorithm and
how does it compare to the optimal running time for this problem?
A. This algorithm runs in polynomial time in n but the optimal running time is exponential in n.
B. This algorithm runs in exponential time in n and the optimal running time is exponential in n.
C. This algorithm runs in exponential time in n but the optimal running time is polynomial in n.
D. This algorithm runs in polynomial time in n and the optimal running time is polynomial in n.
E. The algorithm does not terminate.
tifr2015 time-complexity
Answer
Selected Answer
Selected Answer
Selected Answer
a. Function computes kth smallest element (if k<number of elements in the array, else it returns
max element).
O(k n)
© Copyright GATE Overflow. All rights reserved.
1 Algorithms (323) 241
Selected Answer
(A)
O (r) Binary Search
(log n)
(B)
O
(n (s) Selection of the kth smallest element in a set of n elements.(Worst case)
)
(C)
O (p) Heap sort
(n log n)
(q) Depth-first search
(D) (It will beO(n if the graph is given in the form of adjacency list but if the
O
+ m)
(n2 graph is in the form of adjacency matrix then the complexity is O(n , as we
)
× n)
have to traverse through the whole row until we find an edge.)
PS: kth smallest element can be found in O(n) time using partition algorithm.
T (n) = T (n/2) + n (For finding kth smallest element)
Selected Answer
In fact B = D = E this three options are same. and N 3 is always upper bound of N2. So O(N 3 ) is
also true.
-------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------
PS: ∑(K = 1 to n) O(K) is never equal to n functions. It is always equal to one single
function.
It can be written as c.1 + c.2 + c.3 and so on which results in O(N 2 ) (source Cormen)
Selected Answer
We just require n/2 swaps in the worst case. The algorithm is as given below:
Find positive number from left side and negative number from right side and do exchange. Since,
at least one of them must be less than or equal to n/2, there cannot be more than n/2
exchanges. An implementation is given below:
[Link]
Selected Answer
a. log n
n
an = (a2 ) 2 .
T (n) = T (n/2) + 1.
This gives T (n) = log2 n
For n = 8, we can do
b =a×a
b =b×b
b =b×b and we get b = a8
24 votes -- Arjun Suresh (350k points)
Selected Answer
1
T (n) = T (n − 1) + n + c (O(1/n) replaced with 1/n and so our answer will also be in O only
and not Θ)
1
T (n) = T (n − 2) + n−1 + n1 + 2c
= T (1) + 12 + 13 + ⋯ + n1 + (n − 1)c
= A(1) + 12 + 13 ⋯ + n1 + nc
= 1 + 12 + 13 … + n1 + nc
= log n + nc
(Sum of the first n terms in harmonic series is Θ(log n))
So, our time complexity will be O(n).
24 votes -- Arjun Suresh (350k points)
Selected Answer
Answer: Option A. Because array is always sorted just check the 1st two elements.
Selected Answer
We can simply do a binary search in the array of natural numbers from 1..n and check if the cube
of the number matches n (i.e., check if a[i] ∗ a[i] ∗ a[i] == n). This check takes O(log n) time
and in the worst case we need to do the search O(log n) times. So, in this way we can find the
cube root in O(log2 n). So, options (A) and (B) are wrong.
Now, a number is represented in binary using log n bit. Since each bit is important in finding the
cube root, any cube root finding algorithm must examine each bit at least once. This ensures that
complexity of cube root finding algorithm cannot be lower than log n. (It must be Ω (log n)). So,
(D) is also false and (C) is the correct answer.
Selected Answer
D is correct
Here time complexity is asked, for each access of array element it will be constant,
So the time complexity will not depend upon storage. If at all program execution time is asked
a is true
Selected Answer
The key part in the code is "counter = 0" in the else part as we can see below.
Lets take the best case. This happens when a[i] = 1 for all i, and then the loop executes with time
complexity Θ(1) for each iteration and hence overall time complexity of Θ(n) and we can say
time complexity of the code fragment is Ω(n) and hence options A and B are false.
Now, consider the worst case. This happens when a[i] = 0 or when else part is executed. Here,
the time complexity of each iteration will be Θ(counter) and after each else, counter is reset to 0.
Let k iterations go to the else part during the worst case. Then the worst case time complexity will
be Θ(x1 ) + Θ(x2 ) + ⋯ + Θ(xk ) + Θ(n − k) , where xi is the value of the counter when,
A[i] = 0 and f(counter) is called. But due to counter = 0 after each call to f(), we have,
x1 + x2 + ⋯ + xk = n . So,
Θ(x1 ) + Θ(x2 ) + ⋯ + Θ(xk ) + Θ(n − k) = Θ(n) + Θ(n − k) = Θ(n) .
Since the time complexity is Ω(n) and Θ(n) we can say it is Θ(n) - Option (C). (Option D is false
because the small o needs the growth rate to be STRICTLY lower and not equal to or lower as the
case for big 0)
If counter = 0 was not there in else part, then time complexity would be Ω(n) and O(n2 ) as in
worst case we can have equal number of 0's and 1's in array a giving time complexity
Θ(1) + Θ(2) + ⋯ + Θ(n/2) + Θ(n/2) would give O(n2 ).
Selected Answer
= n [ n−1
n ]
= n − 1 = Θ(n)
26 votes -- rahulkr (805 points)
[Link]
Selected Answer
Worst case will arise when both n and m are consecutive Fibonacci numbers.
gcd(Fn , Fn−1 ) = gcd(Fn−1 , Fn−2 ) = ⋯ = gcd(F1 , F0 ) = 1
and nth Fibonacci number is 1.618n , where 1.618 is the Golden ratio.
So, to find gcd(n, m), number of recursive calls will be Θ(log n).
Selected Answer
We are asked the time complexity which will be the number of recursive calls in the function as in
each call we perform a constant no. of operations and a recursive call. The recurrence relation for
this is (considering constant time "c" as 1)
T (n) = T (√−
n) + 1
= T (n1/4 ) + 2
= T (n1/8 ) + 3
Going like this we will eventually reach T (3) or T (2). For asymptotic case this doesn't matter and
T (2) T (1)
© Copyright GATE Overflow. All rights reserved.
246 1 Algorithms (323)
we can assume we reach T (2) and in next step reach T (1). So, all we want to know is how many
steps it takes to reach T (1) which will be 1+no. of steps to reach T (2).
( 1
)
From the recurrence relation we know that T (2) happens when n 2k = 2.
Taking log and equating,
1
log n = 1
2k
⟹ 2k = log n
⟹ k = log log n.
So, T (1) happens in log log n + 1 calls, but for asymptotic complexity we can write as
Θ (log log n)
Alternatively,
Substituting values
T (1) = 1
T (2) = 1
T (3) = T (1) + 1 = 2
⋮
T (8) = T (2) + 1 = 2
T (9) = T (3) + 1 = 3
⋮
2 2
T (((22 ) ) ) = T ((22 ) ) + 1
2
= T (22 ) + 2
= T (2) + 3 = 1 + 3 = 4,
log log n = 3 as n = 256.
⎛ ⎞
2
2 2
T ((((2 ) ) ) )
2 2
⎝ ⎠
= 6,
T (2(2 ) ) = T (2512 ) + 1
10
= T (2256 ) + 2
= T (2128 ) + 3
= T (264 ) + 4
= T (232 ) + 5
= T (216 ) + 6
= T (28 ) + 7
= T (24 ) + 8
= T (22 ) + 9
= T (2) + 10 = 11,
log log n = 10
So, answer is D.
[Link]
n-complexity
Selected Answer
Selected Answer
Answer is option B.
Worst Case :
Best Case : When is an even number body of loop is executed only time (due to "
" inside if) which is irrespective of . ∴
Selected Answer
Answer is (A)
We need to divide
recursively and compute like following:
Recurrence relation:
Selected Answer
Answer: B
Gradient
For gradient to be maximum should be minimum. So, sort the points (in time)
according to coordinate and find the minimum difference between them (in time).
[Link]
[Link]
Selected Answer
Answer is option B.
whenever there exists an element which is present in the array : more than times, then
definitely it will be present at the middle index position; in addition to that it will also be present at
anyone of the neighbourhood indices namely and
No matter how we push that stream of More than times of elements of same value around the
Sorted Array, it is bound to be present at the middle index atleast anyone of its neighbourhood
once we got the element which should have occurred more that times we count its total
occurrences in time.
Selected Answer
An insert operation on a binary heap takes time, but an alternative approach we can use.
which requires us to insert elements in heap without any computation i.e. in constant time. after
which we can apply Heapify operation(this operation creates heap in linear time) on the array of
those element and Hence obtain a Heap in time.
Here "not necessarily one after another" should mean that we can insert elements at once and
not necesaairly have to wait for first insert to be completed before doing second.
Selected Answer
Q. = option B
Q. = option C
Time complexity of is as here all recursive calls are avoided by saving the results in an
array (dynamic programming).
Selected Answer
Both and are calculating the same function in recursive and iterative fashion respectively.
and
So,
and
Or we can do it manually
Selected Answer
Selected Answer
Selected Answer
find decrease-
delete
insert
key
Unsorted
Array
Min-heap
Sorted Array
Sorted doubly
linked-list
The operations given can be performed in any order. So, for Min-heap we cannot do the usual
BuildHeap method.
Delete in unsorted array is as we can just swap the deleted element with the last element in
the array and delete the last element.
For sorted-doubly linked-list we cannot do binary search as this would require another array to
maintain the pointers to the nodes.
Selected Answer
Ans: , because all elements are distinct, select any three numbers and output nd largest
from them.
Selected Answer
Selected Answer
Inner for loop is dependent on , so for each we have to check no of times inner loop operating..
It ll be something like
Selected Answer
[Link]
Reason: Sort the set. Initialize a counter to 1. Keep a parallel pointer to the sorted list of needed
ranks. Keep incrementing the counter as you traverse the sorted set. As soon as counter matches
the first needed rank, add this to the required output. Increment the parallel pointer.
Selected Answer
1.
2.
3.
Here, If we consider as a term (which is common in all 3), first 1 is a log function, second
one is sqrt function and third one is linear function of . Order of growth of these functions are
well known and is the slowest growing followed by sqrt and then linear. So, option A is the
correct answer here.
PS: After taking is we arrive at functions distinguished by some constant terms only, then we
can not conclude the order of grpwth of the original functions using the function. Examples are
.
Selected Answer
Answer: C.
It is fibanacci series generation. it takes exponential time if we won't use dynamic programming.
The tester now tests the program on all input strings of length five consisting of characters ‘ ’, ‘ ’, ‘
’, ‘ ’ and ‘ ’ with duplicates allowed. If the tester carries out this testing with the four test cases
given above, how many test cases will be able to capture the flaw?
A. Only one
B. Only two
C. Only three
D. All four
Answer
The procedure given below is required to find and replace certain characters inside an input
character string supplied in array . The characters to be replaced are supplied in array , while
their respective replacement characters are supplied in array . Array has a fixed length of
five characters, while arrays and contain three characters each. However, the procedure
is flawed.
1.
2.
3.
4.
If array is made to hold the string “ ”, which of the above four test cases will be successful
in exposing the flaw in this procedure?
A. None
B. only
C. and only
D. only
Answer
Consider the C function given below. Assume that the array contains elements, sorted
in ascending order.