Algorithms Searching and Sorting Page 1 of 54

Chapter 1 Searching and Sorting

1.1 Searching
Q 1. Consider the C function given below. Assume that the array listA contain n(> 0) elements, sorted in 2014Set3
ascending order.
int ProcessArray ( int * listA , int x , int n )
{
int i , j , k ;
i = 0;
j = n -1;
do {
k = ( i + j )/2;
if ( x <= listA [ k ]) j = k -1;
if ( listA [ k ] <= x ) i = k +1;
} while ( i <= j );

if ( listA [ k ] == x )
return ( k );
else
return -1;
}

Which one of the following statements about the function ProcessArray is CORRECT?
A. It will run into an infinite loop when x is not in listA.
B. It is an implementation of binary search.
C. It will always find the maximum element in listA.
D. It will return -1 even when x is present in listA.
Q 2. Consider the following C program that attempts to locate an element x in an array Y [ ] using binary 2008
search. The program is erroneous.
1 f ( int Y [10] , int x ) {
2 int u , j , k ;
3 i = 0; j = 9;
4 do {
5 k = ( i + j ) / 2;
6 if ( Y [ k ] < x ) i = k ; else j = k ;
7 } while ( Y [ k ] != x ) && ( i < j )) ;
8
9 if ( Y [ k ] == x )
10 printf ( " x is in the array " ) ;
11 else
12 printf ( " x is not in the array " ) ;
13 }

(i) On which of the following contents of Y and x does the program fail?
A. Y is [1 2 3 4 5 6 7 8 9 10] and x < 10
B. Y is [1 3 5 7 9 11 13 15 17 19] and x < 1
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
(ii) The correction needed in the program to make it work properly is
A. Change line 6 to: if (Y [k] < x) i = k + 1; else j = k − 1;
B. Change line 6 to: if (Y [k] < x) i = k − 1; else j = k + 1;

1
 Algorithms Searching and Sorting Page 2 of 54

C. Change line 6 to: if (Y [k] < x) i = k; else j = k;

D. Change line 7 to: } while ((Y [k] == x) && (i < j));

Q 3. The recurrence relation that arises in relation to the complexity of binary search is 1994

n n



A. T (n) = 2T 2 + k, k is a constant C. T (n) = T 2 + log n
n n



B. T (n) = T 2 + k, k is a constant D. T (n) = T 2 +n

Q 4. Let F (n) denote the maximum number of comparisons made while searching for an entry in a sorted 2024DA
array of size n using binary search.
Which ONE of the following options is TRUE?

A. F (n) = F (⌊n/2⌋) + 1 C. F (n) = F (⌊n/2⌋)

B. F (n) = F (⌊n/2⌋) + F (⌈n/2⌉) D. F (n) = F (n − 1) + 1

Q 5. For which of the following inputs does binary search take time O(log n) in the worst case? 2025DA

A. An array of n integers in any order C. An array of n integers in increasing order

B. A linked list of n integers in any order D. A linked list of n integers in increasing order

Q 6. What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted 2021Set2
array of size n?
√
A. Θ( n) B. Θ(log2 (n)) C. Θ(n2 ) D. Θ(n)

Q 7. An unordered list contains n distinct elements. The number of comparisons to find an element in this 2015Set2
list that is neither maximum nor minimum is
A. Θ(n log n) B. Θ(n) C. Θ(log n) D. Θ(1)

Q 8. Consider the following algorithm for searching a given number x in an unsorted array A[1 . . . n] having 2002
n distinct values:

1. Choose an i at random from 1 . . . n

2. If A[i] = x, then Stop else Goto 1;
Assuming that x is present in A, what is the expected number of comparisons made by the algorithm
before it terminates?
n
A. n B. n − 1 C. 2n D. 2

Q 9. The minimum number of comparisons required to determine if an integer appears more than n/2 times 2008
in a sorted array of n integers is
A. Θ(n) B. Θ(log n) C. Θ(log∗ n) D. Θ(1)

Q 10. Let A be an array of 31 numbers consisting of a sequence of 0’s followed by a sequence of 1’s. The 2017Set1
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 .
Q 11. The average number of key comparisons done in successful sequential search in a list of length n is 1996
n−1 n n+1
A. log n B. 2 C. 2 D. 2

Q 12. Consider an unordered list of N distinct integers. What is the minimum number of element comparisons 2025Set2
required to find an integer in the list that is NOT the largest in the list?
A. 1 B. N − 1 C. N D. 2N − 1

2
 Algorithms Searching and Sorting Page 3 of 54

1.2 Sorting

1.2.1 Heap Sort

Q 13. Consider an array representation of an n element binary heap where the elements are stored from index 2001
1 to n of the array. For the element stored at index i of the array (i ≤ n), the index of the parent is
(i+1)
A. i − 1 B. ⌊ 2i ⌋ C. ⌈ 2i ⌉ D. 2

Q 14. Which of the following sequences of array elements forms a heap? 2006IT

A. {23, 17, 14, 6, 13, 10, 1, 12, 7, 5} C. {23, 17, 14, 7, 13, 10, 1, 5, 6, 12}
B. {23, 17, 14, 6, 13, 10, 1, 5, 7, 12} D. {23, 17, 14, 7, 13, 10, 1, 12, 5, 7}

Q 15. A max-heap is a heap where the value of each parent is greater than or equal to the value of its children. 2011
Which of the following is a max-heap?

C.
A.

B. D.

Q 16. Draw the min-heap that results from insertion of the following elements in order into an initially empty 1999
min-heap: 7, 6, 5, 4, 2, 3, 1. Show the result after the deletion of the root of this heap.
Q 17. The minimum number of interchanges needed to convert the array 1996
89, 19, 40, 17, 12, 10, 2, 5, 7, 11, 6, 9, 70
into a heap with the maximum element at the root node is
A. 0 B. 1 C. 2 D. 3
Q 18. The elements 32, 15, 20, 30, 12, 25, 16 are inserted one by one in the given order into a max heap. The 2004
resultant max heap is

A. B.

3
 Algorithms Searching and Sorting Page 4 of 54

C. D.

Q 19. A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal 2005
of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The
level-order traversal of the heap after the insertion of the elements is:
A. 10,8,7,5,3,2,1 B. 10,8,7,2,3,1,5 C. 10,8,7,1,2,3,5 D. 10,8,7,3,2,1,5

Q 20. Consider a binary max-heap implemented using an array. 2009

(i) Which one of the following array represents a binary max-heap?

A. {25, 12, 16, 13, 10, 8, 14} C. {25, 14, 16, 13, 10, 8, 12}
B. {25, 14, 13, 16, 10, 8, 12} D. {25, 14, 12, 13, 10, 8, 16}

(ii) What is the content of the array after two delete operations on {25, 14, 16, 13, 10, 8, 12}

A. {14, 13, 12, 10, 8} C. {14, 13, 8, 12, 10}

B. {14, 12, 13, 8, 10} D. {14, 13, 12, 8, 10}

Q 21. A priority queue is implemented as a Max-Heap. Initially, it has 5 elements. The level-order traversal 2014Set2
of the heap is: 10, 8, 5, 3, 2. Two new elements 1 and 7 are inserted into the heap in that order. The
level-order traversal of the heap after the insertion of the elements is:
A. 10, 8, 7, 3, 2, 1, 5 B. 10, 8, 7, 2, 3, 1, 5 C. 10, 8, 7, 1, 2, 3, 5 D. 10, 8, 7, 5, 3, 2, 1

Q 22. Consider a max heap, represented by the array: 40, 30, 20, 10, 15, 16, 17, 8, 4 2015Set1
Array index 1 2 3 4 5 6 7 8 9
Value 40 30 20 10 15 16 17 8 4
Now consider that a value 35 is inserted into this heap. After insertion, the new heap is

A. 40, 30, 20, 10, 15, 16, 17, 8, 4, 35 C. 40, 30, 20, 10, 35, 16, 17, 8, 4, 15
B. 40, 35, 20, 10, 30, 16, 17, 8, 4, 15 D. 40, 35, 20, 10, 15, 16, 17, 8, 4, 30

Q 23. Consider the following array of elements. 2015Set3

⟨89, 19, 50, 17, 12, 15, 2, 5, 7, 11, 6, 9, 100⟩
The minimum number of interchanges needed to convert it into a max-heap is
A. 4 B. 5 C. 2 D. 3
Q 24. Which one of the following sequences when stored in an array at locations A[1], . . . , A[10] forms a 2023
max-heap?

A. 23, 17, 10, 6, 13, 14, 1, 5, 7, 12 C. 23, 17, 14, 6, 13, 10, 1, 5, 7, 15
B. 23, 17, 14, 7, 13, 10, 1, 5, 6, 12 D. 23, 14, 17, 1, 10, 13, 16, 12, 7, 5

Q 25. An array [82, 101, 90, 11, 111, 75, 33, 131, 44, 93] is heapified. Which one of the following options 2024Set1
represents the first three elements in the heapified array?
A. 82, 90, 101 B. 82, 11, 93 C. 131, 11, 93 D. 131, 111, 90

4
 Algorithms Searching and Sorting Page 5 of 54

Q 26. Consider a binary min-heap containing 105 distinct elements. Let k be the index (in the underlying 2024Set1
array) of the maximum element stored in the heap. The number of possible values of k is
A. 53 B. 52 C. 27 D. 1

Q 27. The number of possible min-heaps containing each value from {1, 2, 3, 4, 5, 6, 7} exactly once is 2018
.
Q 28. The height of any rooted tree is defined as the maximum number of edges in the path from the root 2025Set1
node to any leaf node. Suppose a Min-Heap T stores 32 keys. The height of T is .
(Answer in integer)

Q 29. An array X of n distinct integers is interpreted as a complete binary tree. The index of the first element 2006IT
of the array is 0.
(i) The index of the parent of element X[i], i ̸= 0, is?
       
i i−1 i i
A. B. C. D. −1
2 2 2 2
(ii) If only the root node does not satisfy the heap property, the algorithm to convert the complete
binary tree into a heap has the best asymptotic time complexity of
A. O(n) B. O(log n) C. O(n log n) D. P (n log log n)
(iii) If the root node is at level 0, the level of element X[i], i ̸= 0, is?
A. ⌊log2 i⌋ B. ⌈log2 (i + 1)⌉ C. ⌊log2 (i + 1)⌋ D. ⌈log2 i⌉

Q 30. A complete binary min-heap is made by including each integer in [1,1023] exactly once. The depth of a 2016Set2
node in the heap is the length of the path from the root of the heap to that node. Thus, the root is at
depth 0. The maximum depth at which integer 9 can appear is .
Q 31. Consider the array representation of a binary min-heap containing 1023 elements. The minimum number 2020
of comparisons required to find the maximum in the heap is .

Q 32. An array of integers of size n can be converted into a heap by adjusting the heaps rooted at each internal 2004IT
node of the complete binary tree starting at the node ⌊(n − 1)/2⌋, and doing this adjustment up to the
root node (root node is at index 0) in the order ⌊(n − 1)/2⌋, ⌊(n − 3)/2⌋ , . . . , 0. The time required to
construct a heap in this manner is
A. O(log n) B. O(n) C. O(n log log n) D. O(n log n)

Q 33. We have a binary heap on n elements and wish to insert n more elements (not necessarily one after 2008
another) into this heap. The total time required for this is
A. Θ(log n) B. Θ(n) C. Θ(n log n) D. Θ(n2 )

Q 34. In heap with n elements with the smallest element at the root, the 7th smallest element can be found 2003
in time
A. Θ(n log n) B. Θ(n) C. Θ(log n) D. Θ(1)

Q 35. In a binary max heap containing n numbers, the smallest element can be found in time 2006
A. O(n) B. O(log n) C. O(log log n) D. O(1)

Q 36. The number of elements that can be sorted in Θ(log n) time using heap sort is 2013
√
A. Θ(1) B. Θ( logn) C. Θ( logloglogn n ) D. Θ(log n)

Q 37. Consider a complete binary tree where the left and right subtrees of the root are max-heaps. The lower 2015Set2
bound for the number of operations to convert the tree to a heap is
A. Ω(log n) B. Ω(n) C. Ω(n log n) D. Ω(n2 )

Q 38. Consider the following statements: 2019

5
 Algorithms Searching and Sorting Page 6 of 54

I. The smallest element in a max-heap is always at a leaf node

II. The second largest element in a max-heap is always a child of a root node
III. A max-heap can be constructed from a binary search tree in Θ(n) time
IV. A binary search tree can be constructed from a max-heap in Θ(n) time
Which of the above statements are TRUE?
A. I, II and III B. I, II and IV C. I, III and IV D. II, III and IV
Q 39. Suppose there are ⌈log n⌉ sorted lists of ⌊n/ log n⌋ elements each. The time complexity of producing a 2005
sorted list of all these elements is: (Hint: Use a heap data structure)


A. O(n log log n) B. Θ(n log n) C. Ω(n log n) D. Ω n3/2

Q 40. Consider the process of inserting an element into a MaxHeap, where the MaxHeap is represented by an 2007
array. Suppose we perform a binary search on the path from the new leaf to the root to find the position
for the newly inserted element, the number of comparisons performed is:
A. Θ(log2 n) B. Θ(log2 log2 n) C. Θ(n) D. Θ(n log2 n)

Q 41. An operator delete(i) for a binary heap data structure is to be designed to delete the item in the i-th 2016Set1
node. Assume that the heap is implemented in an array and i refers to the i-th index of the array. If
the heap tree has depth d (number of edges on the path from the root to the farthest leaf), then what
is the time complexity to re-fix the heap efficiently after the removal of the element?
A. O(1) B. O(d) but not O(1) C. O(2d ) but not O(d) D. O(d2d ) but not O(2d )

Q 42. A priority queue Q is used to implement a stack S that stores characters. P U SH(C) is implemented 1997
as IN SERT (Q, C, K) where K is an appropriate integer key chosen by the implementation. P OP is
implemented as DELET EM IN (Q). For a sequence of operations, the keys chosen are in

A. non-increasing order C. strictly increasing order

B. non-decreasing order D. strictly decreasing order

Q 43. Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap 2023
data structure. The operation EXTRACT-MAX(A) extracts and deletes the maximum element from
A. The operation INSERT(A, key) inserts a new element key in A. The properties of a max-heap are
preserved at the end of each of these operations. When A contains n elements, which one of the following
statements about the worst case running time of these two operations is TRUE?
A. Both EXTRACT-MAX(A) and INSERT(A, key) run in O(1).
B. Both EXTRACT-MAX(A) and INSERT(A, key) run in O(log(n)).
C. EXTRACT-MAX(A) runs in O(1) whereas INSERT(A, key) runs in O(n).
D. EXTRACT-MAX(A) runs in O(1) whereas INSERT(A, key) runs in O(log(n)).

1.2.2 Merge Sort

Q 44. Merge sort uses: 1995

A. Divide-and-conquer strategy C. Heuristic search

B. Backtracking approach D. Greedy approach

Q 45. The worst-case time complexity of mergesort for sorting n elements is 1991
2 2
A. (n ) B. (n log n) C. (n log n) D. (log n)

Q 46. If one uses straight two-ways merge sort algorithm to sort the following elements in ascending order 1999
20, 47, 15, 8, 9, 4, 40, 30, 12, 17
then the order of these elements after the second pass of the algorithm is:

6
 Algorithms Searching and Sorting Page 7 of 54

A. 8, 9, 15, 20, 47, 4, 12, 17, 30, 40 C. 15, 20, 47, 4, 8, 9, 12, 30, 40, 17
B. 8, 15, 20, 47, 4, 9, 30, 40, 12, 17 D. 15, 20, 47, 4, 8, 9, 12, 30, 40, 17

Q 47. Let a and b be two sorted arrays containing n integers each, in non-decreasing order. Let c be a sorted 2005IT
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

I. a[i] ≥ b[i] ⇒ c[2i] ≥ a[i] III. a[i] ≥ b[i] ⇒ c[2i] ≤ a[i]

II. a[i] ≥ b[i] ⇒ c[2i] ≥ b[i] IV. a[i] ≥ b[i] ⇒ c[2i] ≤ b[i]

Which of the following is TRUE?

A. only I and II B. only I and IV C. only II and III D. only III and IV
Q 48. For merging two sorted lists of size m and n into a sorted list of size m + n, we require comparisons of 1995
A. O(m) B. O(n) C. O(m + n) D. O(log m + log n)

Q 49. Assume that a mergesort algorithm in the worst case takes 30 seconds for an input of size 64. Which 2015Set3
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. 2048
Q 50. A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. 2012
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 )

Q 51. Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be 2014Set2
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 .

1.2.3 Quick Sort

Q 52. Consider sorting the following array of integers in ascending order using an in-place Quicksort algorithm 2024DA
that uses the last element as the pivot.

60 70 80 90 100

The minimum number of swaps performed during this Quicksort is .

Q 53. The average case complexity of quick sort algorithm for sorting n elements is 1990
2 2
A. (n log log n) B. (n ) C. (n log n) D. (n log n)

Q 54. Which of the following algorithm design techniques is used in the quicksort algorithm? 1994
A. Dynamic programming B. Backtracking C. Divide and conquer D. Greedy method
Q 55. Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits 2008
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 C. T (n) ≤ 2T (4n/5) + n

B. T (n) ≤ T (n/5) + T (4n/5) + n D. T (n) ≤ 2T (n/2) + n

Q 56. Which one of the following is the recurrence equation for the worst case time complexity of the quick 2015Set1
sort algorithm for sorting n (≥ 2) numbers? In the recurrence equations given in the options below, c is
a constant.

7
 Algorithms Searching and Sorting Page 8 of 54

A. T (n) = 2T (n/2) + cn C. T (n) = 2T (n − 1) + cn

B. T (n) = T (n − 1) + T (1) + cn D. T (n) = T (n/2) + cn

Q 57. Assume that the last element of the set is used as partition element in Quick sort. If n distinct elements 1992
from the set [1 . . . n] are to be sorted, give an input for which Quick sort takes maximum time.

Q 58. Let P be a quicksort program to sort numbers in ascending order. Let t1 and t2 be the time taken by 1987
the program for the inputs [1 2 3 4 5] 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

Q 59. Let P be quicksort program to sort numbers in ascending order using the first element as the pivot. Let 2014Set1
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
Q 60. Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot 1996
1. 1, 2, 3, . . . n
2. n, n − 1, n − 2, . . . , 2, 1

Let C1 and C2 be the number of comparisons made for the inputs 1 and 2 respectively. Then,
A. C1 < C2 B. C1 > C2 C. C1 = C2 D. we cannot say anything for arbitrary n
Q 61. In quick-sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) 2009
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)

Q 62. You have an array of n elements. Suppose you implement quicksort by always choosing the central 2014Set3
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 )

Q 63. An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen 2019
uniformly at random. The probability that the pivot element gets placed in the worst possible location
in the first round of partitioning (rounded off to 2 decimal places) is .

Q 64. Randomized quick sort is an extension of quick sort where the pivot is chosen randomly. What is the 2001
worst-case complexity of sorting n numbers using randomized quick sort?
A. O(n) B. O(n log n) C. O(n2 ) D. O(n!)

Q 65. The median of n elements can be found in O(n) time. Which one of the following is correct about the 2006
complexity of quick sort, in which median is selected as pivot?
A. Θ(n) B. Θ(n log n) C. Θ(n2 ) D. Θ(n3 )

1.2.4 Selection Sort

Q 66. What is the number of swaps required to sort n elements using selection sort, in the worst case? 2009
2 2
A. Θ(n) B. Θ(n log n) C. Θ(n ) D. Θ(n log n)

Q 67. Which one of the following is the tightest upper bound that represents the number of swaps required to 2013
sort n numbers using selection sort?
A. O(log n) B. O(n) C. O(n log n) D. O(n2 )

8
 Algorithms Searching and Sorting Page 9 of 54

1.2.5 Insertion Sort

Q 68. Suppose that insertion sort is applied to the array [1, 3, 5, 7, 9, 11, x, 15, 13] and it takes exactly two swaps 2025DA
to sort the array. Select all possible values of x.
A. 10 B. 12 C. 14 D. 16

Q 69. The usual implementation of insertion sort to sort an array uses linear search to identify the position 2003
where an element is to be inserted into already sorted part of the array. If, instead, we use binary search
to find the position, the worst-case running time will
A. remains Θ(n2 ) B. become Θ(n(log n)2 ) C. become Θ(n log n) D. become Θ(n)

Q 70. In a permutation a1 . . . an of n distinct integers, an inversion is a pair (ai , aj ) such that i < j and 2003
ai > aj .
(i) If all permutations are equally likely, what is the expected number of inversions in a randomly
chosen permutation of 1 . . . n?
n(n−1) n(n−1) n(n+1)
A. 2 B. 4 C. 4 D. 2n[log2 n]
(ii) 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)

1.2.6 Comparison Based Sorting

Q 71. The complexity of comparison based sorting algorithm is: 1990

2
√
A. θ(n log n) B. θ(n) C. θ(n ) D. θ(n n)

Q 72. The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting 2004
is of the order of
A. n B. n2 C. n log n D. n log2 n

Q 73. Consider the following array. 2021Set1

23 32 45 69 72 73 89 97
Which algorithm out of the following options uses the least number of comparisons (among the array
elements) to sort the above array in ascending order?

A. Selection sort C. Insertion sort

B. Mergesort D. Quicksort using the last element as pivot

Q 74. Consider the following sorting algorithms: 2024DA

(i) Bubble sort (ii) Insertion sort (iii) Selection sort

Which ONE among the following choices of sorting algorithms sorts the numbers in the array [4, 3, 2,
1, 5] in increasing order after exactly two passes over the array?
A. (i) only B. (iii) only C. (i) and (iii) only D. (ii) and (iii) only

Q 75. Given an integer array of size N , we want to check if the array is sorted (in either ascending or descending 2024Set1
order). An algorithm solves this problem by making a single pass through the array and comparing each
element of the array only with its adjacent elements. The worst-case time complexity of this algorithm
is

9
 Algorithms Searching and Sorting Page 10 of 54

A. both O(N ) and Ω(N ) C. Ω(N ) but not O(N )

B. O(N ) but not Ω(N ) D. neither O(N ) nor Ω(N )

Q 76. An array of n numbers is given, where n is an even number. The maximum as well as the minimum 2007
of these n numbers needs to be determined. Which of the following is TRUE about the number of
comparisons needed?
A. At least 2n − c comparisons, for some constant c are needed.
B. At most 1.5n − 2 comparisons are needed.
C. At least n log2 n comparisons are needed.
D. None of the above

Q 77. The minimum number of comparisons required to find the minimum and the maximum of 100 numbers 2014Set1
is .
Q 78. Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons 2021Set1
of the array elements, required to find the minimum and maximum values in an arbitrary array of n
elements. Which one of the following choices is correct?

A. t > 2n − 2 C. t > n and t ≤ 3⌈ n2 ⌉

B. t > 3⌈ n2 ⌉ and t ≤ 2n − 2 D. t > ⌈log2 (n)⌉ and t ≤ n

Q 79. The pseudocode of a function fun() is given below: 2025Set1

fun ( int A [0 ,.... , n -1]) {
for i =0 to n -2
for j =0 to n -i -2
if ( A [ j ] > A [ j +1])
then swap A [ j ] and A [ j +1]
}

Let A[0, . . . , 29] be an array storing 30 distinct integers in descending order. The number of swap
operations that will be performed, if the function fun () is called with A[0, . . . , 29] as argument, is
. (Answer in integer)

Q 80. An array A of length n with distinct elements is said to be bitonic if there is an index 1 ≤ i ≤ n such 2025Set2
that A[1 . . . i] is sorted in the non-decreasing order and A[i + 1 . . . n] is sorted in the non-increasing order.
Which ONE of the following represents the best possible asymptotic bound for the worst-case number
of comparisons by an algorithm that searches for an element in a bitonic array A?
A. Θ(n) B. Θ(1) C. Θ(log2 n) D. Θ(log n)

1.2.7 No Comparison Based Sorting

Q 81. Following algorithm(s) can be used to sort n integers in the range [1 . . . n3 ] in O(n) time 1992
A. Heapsort B. Quicksort C. Mergesort D. Radixsort

Q 82. If we use Radix Sort to sort n integers in the range nk/2 , nk , for some k > 0 which is independent of 2008IT
n, the time taken would be?
A. Θ(n) B. Θ(kn) C. Θ(n log n) D. Θ(n2 )

10
 Algorithms Searching and Sorting Page 11 of 54

1.2.8 Summary

Q 83. A sorting technique is called stable if 1999

A. It takes O(nlog n) time
B. It maintains the relative order of occurrence of non-distinct elements
C. It uses divide and conquer paradigm
D. It takes O(n) space

Q 84. Linked lists are not suitable for data structures for which one of the following problems? 1994
A. Insertion sort B. Binary Search C. Radix Sort D. Polynomial manipulation
Q 85. Which one of the following in place sorting algorithms needs the minimum number of swaps? 2006
A. Queue sort B. Insertion sort C. Selection sort D. Heap sort
Q 86. Which of the following sorting algorithms has the lowest worst-case complexity? 2007
A. Merge sort B. Bubble sort C. Quick sort D. Selection sort

Q 87. The worst case running times of Insertion sort, Merge sort and Quick sort, respectively are: 2016Set1

A. Θ(n log n), Θ(n log n) and Θ(n2 ) C. Θ(n2 ), Θ(n log n) and Θ(n log n)
B. Θ(n2 ), Θ(n2 ) and Θ(n log n) D. Θ(n2 ), Θ(n log n) and Θ(n2 )

Q 88. Assume that the algorithms considered here sort the input sequences in ascending order. If the input is 2016Set2
already in the ascending order, which of the following are TRUE?

I. Quicksort runs in Θ(n2 ) time III. Mergesort runs in Θ(n) time

2
II. Bubblesort runs in Θ(n ) time IV. Insertion sort runs in Θ(n) time

A. I and II only B. I and III only C. II and IV only D. I and IV only

Q 89. Let A be an array containing integer values. The distance of A is defined as the minimum number 2024Set2
of elements in A that must be replaced with another integer so that the resulting array is sorted in
non-decreasing order. The distance of the array [2, 5, 3, 1, 4, 2, 6] is .

Q 90. Suppose you are provided with the following function declaration in the C programming language. 2015Set2
int partition(int a[], int n);
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 k th smallest
element in an array a[ ] of size n using the partition function. We assume k ≤ n.
int kth_smallest ( int a [] , int n , int k )
{
int left_end = partition (a , n );
if ( left_end +1== k ) {
return a [ left_end ];
}
if ( left_end +1 > k ) {
return kth_smallest ( ___________ );
} else {
return kth_smallest ( ___________ );
}
}

11
 Algorithms Searching and Sorting Page 12 of 54

The missing arguments lists are respectively

A. (a, left_end, k) and (a + left_end+1, n-left_end-1, k-left_end-1)
B. (a, left_end, k) and (a, n-left_end-1, k-left_end-1)
C. (a + left_end+1, n-left_end-1, k-left_end-1) and (a, left_end, k)
D. (a, n-left_end-1, k-left_end-1) and (a, left_end, k)
Q 91. There are n unsorted arrays: A1 , A2 , . . . , An . Assume that n is odd. Each of A1 , A2 , . . . , An contains 2019
n distinct elements. There are no common elements between any two arrays. The worst-case time
complexity of computing the median of the medians of A1 , A2 , . . . , An is
A. O(n) B. O(n log n) C. O(n2 ) D. Ω(n2 log n)

1.3 More Questions

Q 92. Suppose you are given n numbers and you sort them in descending order as follows: First find the TIFR’10
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. D. Same as heap sort.

B. O n2 but not better.


C. O (n log n) E. O n1.5 but not better.

Q 93. Consider the Insertion Sort procedure given below, which sorts an array L of size n (≥ 2) in ascending TIFR’10
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?
A. There is no input on which insertion Sort makes n(n − 1)/2 comparisons.
B. Insertion Sort makes n(n − 1)/2 comparisons when the input is already sorted in ascending order.
C. Insertion Sort makes n(n − 1)/2 comparisons only when the input is sorted in descending order.
D. There are more than one input orderings where insertion sort makes n(n − 1)/2 comparisons.
E. Insertion Sort makes n(n − 1)/2 comparisons whenever all the elements of L are not distinct.

Q 94. Suppose you are given an array A with 2n numbers. The numbers in odd positions are sorted in TIFR’10
ascending order, that is, A[1] ≤ A[3] ≤ . . . ≤ A[2n − 1]. The numbers in even positions are sorted in
descending order, that is, A[2] ≥ A[4] ≥ . . . ≥ A[2n]. What is the method you would recommend for
determining if a given number is in the array?
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.

12
 Algorithms Searching and Sorting Page 13 of 54

D. Perform separate binary searches on the odd positions and the even positions.
E. Search sequentially from the end of the array.

Q 95. You are given k sorted lists, each containing m integers in ascending order. Assume that (i) the lists ISI’11
are stored as singly-linked lists with one integer in each node, and (ii) the head pointers of these lists
are stored in an array.
1. Write an efficient algorithm that merges these k sorted lists into a single sorted list using θ(k)
additional storage.
2. How would you modify your algorithm if you were permitted to use only constant additional storage?
Analyse the time complexity of your algorithm for each of the above two cases.

Q 96. There are n students of a class standing in a line. The students have to arrange themselves in ascending ISI’11
order on the basis of their roll numbers. This rearrangement of the line must be accomplished only by
successively swapping pairs of adjacent students.
1. Design an algorithm for this purpose that minimizes the number of swaps required.
2. Derive an expression for the number of swaps needed by your algorithm in the worst case.

Q 97. Given a set of n = 2k distinct numbers, we would like to determine the smallest and the second smallest TIFR’11
using comparisons. Which of the following statements is TRUE?
A. Both these elements can be determined using 2k comparisons.
B. Both these elements can be determined using n − 2 comparisons.
C. Both these elements can be determined using n + k − 2 comparisons.
D. 2n − 3 comparisons are necessary to determine these two elements.
E. nk comparisons are necessary to determine these two elements.

Q 98. Suppose you have the following three subroutines: ISI’12

• max(A, i, j): returns the index of the maximum among the set of consecutive elements A[i, . . . , j]
of the array A.
• min(A, i, j): returns the index of the minimum among the set of consecutive elements A[i, . . . , j] of
the array A.
• swap(A, i, j): swaps the two elements A[i] and A[j] in the array A.
Design an O(n log n) time algorithm which can use only these three subroutines to sort a given array
A = {A[i] | i = 1, 2, . . . , n} of distinct integers. Assume that the time complexity of the first two
subroutines is O(k), where k = j − i, and that for the third subroutine is O(1).

Q 99. An array A contains n integers. We wish to sort A in ascending order. We are told that initially no TIFR’12
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 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 · k 2 n comparisons but not fewer.

Q 100. Consider the quick sort algorithm on a set of n numbers, where in every recursive subroutine of the TIFR’12
algorithm, the algorithm chooses the median of that set as the pivot. Then which of the following
statements is TRUE?
A. The running time of the algorithm is Θ(n).

13
 Algorithms Searching and Sorting Page 14 of 54

B. The running time of the algorithm is Θ(n log n).

C. The running time of the algorithm is Θ(n1.5 ).
D. The running time of the algorithm is Θ(n2 ).
E. None of the above.
Q 101. It takes O(n) time to find the median in a list of n elements, which are not necessarily in sorted order TIFR’13
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) D. O(n) but not O( n)
B. O(log n) but not O(1)
√
C. O( n) but not O(log n) E. O (n log n) but not O(n)

Q 102. Let H1 and H2 be two complete binary trees that are heaps as well. Assume H1 and H2 are max-heaps, ISI’14
each of size n. Design and analyze an efficient algorithm to merge H1 and H2 to a new max-heap H of
size 2n.
Q 103. An array of n distinct elements is said to be un-sorted if for every index i such that 2 ≤ i ≤ n − 1, TIFR’17
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?
√ √
A. O(n log n) but not O(n) B. O(n) but not O( n) C. O( n) but not O(log n)
D. O(log n) but not O(1) E. O(1)

Q 104. Consider a max-heap of n distinct integers, n ≥ 4, stored in an array A[1...n]. The second minimum ISI’18
of A is the integer that is less than all integers in A except the minimum of A. Find all possible array
indices of A in which the second minimum can occur. Justify your answer.

Q 105. Consider the recursive quicksort algorithm with ”random pivoting”. That is, in each recursive call, a TIFR’18
pivot is chosen uniformly at random from the sub-array being sorted. When this randomized algorithm
is applied to an array of size n all whose elements are distinct, what is the probability that the smallest
and the largest elements in the array are compared during a run of the algorithm?
     
1 1 1
A. n1 B. n2 C. Θ D. O E. Θ
n log n n2 n log2 n

Q 106. You are given two sorted arrays X[ ] and Y [ ] of positive integers. The array sizes are not given. ISI’20
Accessing any index beyond the last element of the arrays returns -1. The elements in each array are
distinct but the two arrays may have common elements. An intersection point between the two arrays
is an element common to both the arrays, i.e., p(p > 0) be an intersection point if there exist i, j such
that X[i] = Y [j] = p.
Given a positive integer q, design an algorithm (in pseudocode) to check if q is an intersection point
between X and Y . No marks will be awarded if the time complexity of your algorithm is linear (or
higher) in the maximum size of X and Y .

Q 107. Let A [i] : i = 0, 1, 2, . . . , n − 1 be an array of n distinct integers. We wish to sort A in ascending order. TIFR’21
We are given that each element in the array is at a position that is at most k away from its position in the
sorted array, that is, we are given that A[i] will move to a position in {i − k, i − k + 1, . . . , i, . . . , i + k − 1, i + k}
after the array is sorted in ascending order. Suppose insertion sort is used to sort this array: that is, in
the ith iteration, A[i] is compared with the elements in positions A[i − 1], A[i − 2], . . . until one that is
smaller is found and A[i] is inserted after that element. Note that elements can be moved back when later
insertions are made before them. Let t(n) be the worst-case number of comparisons made by insertion
sort for such inputs. Then,


A. t (n) = Θ n2 B. t (n) = Θ (n log2 n) C. t (n) = Θ (nk log k) D. t (n) = Θ (n log2 k)
E. t (n) = Θ (nk)

Q 108. Consider the problem of sorting n single digit integers (base 10). This problem can be solved in time TIFR’22

14
 Algorithms Searching and Sorting Page 15 of 54

A. O(n log n) but not O(n log log n)

B. O(n log log n) but not O(n)
C. O(n) but not O(n/ log log n)
D. O(n/ log log n)
E. None of the above
Q 109. There is an unsorted list of n integers. You are given 3 distinct integers and you have to check if TIFR’22
all 3 integers are present in the list or not. The only operation that you are allowed to perform is a
comparison. Let A be an algorithm for this task that performs the least number of comparisons. Let c
be the number of comparisons done by A. Then,
A. c = 3n B. c = 2n + 5 C. c ≥ 3n − 1 D. c ≤ n E. c ≤ 2n + 3
Q 110. Consider the following function count that takes as input a an array of integers, and N, the size of the TIFR’22
array.
int count ( int a [] , int N ) {
int i , j , count_FN ;
count_FN = 0;
for ( i =1 ; i < N ; i ++) {
j =i -1 ;
while ( a [ j ] > a [ i ]) {
count_FN ++;
j - -;
}
}
return count_FN ;
}

Further, let count IS be the number of comparisons made by the insertion sort algorithm on the array a.
Which of the following statements is TRUE for some constant c?
A. For all N ≥ c, there exists an array of size N for which count IS ≥ N2 /c, while count FN ≤ cN
B. For all N ≥ c, there exists an array of size N for which count FN ≥ N2 /c, while count IS ≤ cN
C. For all N ≥ c, for all arrays of size N, count FN ≤ count IS ≤ c × count FN
D. For all N ≥ c, for all arrays of size N, count FN ≥ N2 /c
E. None of the above.
Q 111. In the following code, A is an array indexed from 0, and for two integers a, b the expression a//b returns CMI’24
⌊a/b⌋, the largest integer which is not larger than a/b.
foo (A , first , last )
1 if first ≥ last
2 then return A [ first ]
3 else
4 mid ←( first + last )//2
5 l ← foo (A , first , mid )
6 r ←foo (A , mid + 1 , last )
7 return l + r

If A = [1, 2, 3, 4, 5, 6], what will foo(A,0,5) return?

A. 3 B. 7 C. 15 D. 21
Q 112. Recall the insertion sort algorithm: TIFR’25

15
Algorithms Searching and Sorting Page 16 of 54

procedure InsertionSort ( A )
for i ← 1 to A . length -1 do
key ← A [ i ]
j ← i -1
while j ≥ 0 and A [ j ] > key do
A [ j + 1] ← A [ j ]
j ← j -1
end while
A [ j + 1] ← key
end for
end procedure

Suppose for some parameter k (possibly a function of the length of the array n), we are guaranteed that
the array has k inversions, i.e., there are exactly k pairs (i, j) such that A[i] > A[j] and i < j. Then,
the running time of insertion sort for A is:

A. Θ(n + k) D. Θ(k log n)

B. Θ(n log n + k)
C. Θ(n2 + k) E. Θ(n log k)

16
 Algorithms Graphs - Basics and Traversals Page 17 of 54

Chapter 2 Graphs - Basics and Traversals

Q 1. Write the adjacency matrix representation of the graph given in below figure. 1998

2.1 Breadth First Search

Q 2. The Breadth First Search algorithm has been implemented using the queue data structure. One possible 2008
order of visiting the nodes of the following graph is

A. MNOPQR
B. NQMPOR
C. QMNPRO

D. QMNPOR

Q 3. The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which 2017Set2
one of the following is a possible order of visiting the nodes in the graph below?

A. MNOPQR

B. NQMPOR
C. QMNROP
D. POQNMR

Q 4. Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex 2016Set2
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 .
Q 5. Consider the tree arcs of a BFS traversal from a source node W in an unweighted, connected, undirected 2014Set2
graph. The tree T formed by the tree arcs is a data structure for computing
A. the shortest path between every pair of vertices.
B. the shortest path from W to every vertex in the graph.
C. the shortest paths from W to only those nodes that are leaves of T .
D. the longest path in the graph.
Q 6. Consider an undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a 2001
node r. Let d(r, u) and d(r, v) be the lengths of the shortest paths from r to u and v respectively in G.
If u is visited before v during the breadth-first traversal, which of the following is correct?
A. d(r, u) < d(r, v) B. d(r, u) > d(r, v) C. d(r, u) ≤ d(r, v) D. None of the above

17
 Algorithms Graphs - Basics and Traversals Page 18 of 54

Q 7. Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For 2015Set1
x ∈ V , let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is 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
Q 8. Consider the following algorithm someAlgo that takes an undirected graph G as input. 2025Set2

someAlgo(G )
1. Let v be any vertex in G. Run BFS on G starting at v. Let u be a vertex in G at
maximum distance from v as given by the BFS.
2. Run BFS on G again with u as the starting vertex. Let z be the vertex at maximum
distance from u as given by the BFS.
3. Output the distance between u and z in G.
The output of someAlgo(T ) for the tree shown in the given figure is . (Answer in
integer)

2.2 Depth First Search

Q 9. Consider the following graph: 2003

Among the following sequences:

I. abeghf III. abfhge

II. abfehg IV. afghbe

Which are the depth-first traversals of the above graph?

A. I, II and IV only C. II, III and IV only

B. I and IV only D. I, III and IV only

Q 10. Consider the following sequence of nodes for the undirected graph given below: 2008IT

1. a b e f d g c 3. a d g e b c f
2. a b e f c g d 4. a d b c g e f

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

18
 Algorithms Graphs - Basics and Traversals Page 19 of 54

A. 1 and 3 only
B. 2 and 3 only

C. 2, 3 and 4 only
D. 1, 2 and 3 only

Q 11. Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume 2014Set3
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 .

Q 12. Consider a directed graph G = (V, E) where V = {0, 1, 2, . . . , 100} and E = {(i, j) : 0 < j − i ≤ 2, for 2025DA
all i, j ∈ V }. Suppose the adjacency list of each vertex is in decreasing order of vertex number, and
depth-first search (DFS) is performed at vertex 0. The number of vertices that will be discovered after
vertex 50 is . (Answer in integer)

Q 13. Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time 2014Set1
of Depth First Search on G, when G is represented as an adjacency matrix?
A. Θ(n) B. Θ(n + m) C. Θ(n2 ) D. Θ(m2 )

Q 14. Let G be an undirected graph. Consider a depth first traversal G, and let T be the resulting depth first 2000
search tree. Let u be a vertex in G and v be the first new (unvisited) vertex visited after visiting u in
the traversal. Which of the following is always true?
A. {u, v} must be an edge in G, and u is descendent of v in T
B. {u, v} must be an edge in G, and v is descendent of u in T
C. If {u, v} is not an edge in G, then u is leaf in T
D. If {u, v} is not an edge in G, then u and v must have the same parent in T

Q 15. Consider performing depth-first search (DFS) on an undirected and unweighted graph G starting at 2024DA
vertex s. For any vertex u in G, d[u] is the length of the shortest path from s to u. Let (u, v) be an
edge in G such that d[u] < d[v]. If the edge (u, v) is explored first in the direction from u to v during
the above DFS, then (u, v) becomes a edge.
A. tree B. cross C. back D. gray
Q 16. Let T be a depth first search tree in an undirected graph G. Vertices u and v are leaves of this tree T . 2006
The degrees of both u and v in G are at least 2. Which one of the following statements is true?
A. There must exist a vertex w adjacent to both u and v in G
B. There must exist a vertex w whose removal disconnects u and v in G
C. There must exist a cycle in G containing u and v

19
 Algorithms Graphs - Basics and Traversals Page 20 of 54

D. There must exist a cycle in G containing u and all its neighbours in G

Q 17. A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex 2007IT
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?
A. d[u] < d[v] B. d[u] < f [v] C. f [u] < f [v] D. f [u] > f [v]

Q 18. (MSQ) An articulation point in a connected graph is a vertex such that removing the vertex and its 2021Set1
incident edges disconnects the graph into two or more connected components.
Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following
options is/are correct?
A. Root of T can never be an articulation point in G.
B. Root of T is an articulation point in G if and only if it has 2 or more children.
C. A leaf of T can be an articulation point in G.
D. If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in
T , then all paths from x to y in G must pass through u.

2.3 Connected Components

Q 19. Which of the following is the correct decomposition of the directed graph given below into its strongly 2006IT
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 }

Q 20. The number of edges present in the forest generated by the DFS traversal of an undirected graph G 2024Set1
with 100 vertices is 40. The number of connected components in G is .
Q 21. Let G be a graph with 100 vertices numbered 1 to 100. Two vertices i and j are adjacent iff |i − j| = 8 1997
or |i − j| = 12. The number of connected components in G is
A. 8 B. 4 C. 12 D. 25
Q 22. If G is the forest with n vertices and k connected components, how many edges does G have? 2014Set3
A. nk B. nk
   
C. n − k D. n − k + 1

Q 23. The most efficient algorithm for finding the number of connected components in an undirected graph 2008
on n vertices and m edges has time complexity
A. Θ(n) B. Θ(m) C. Θ(m + n) D. Θ(mn)

Q 24. In depth-first traversal of a graph G with n vertices, k edges are marked as tree edges. The number of 2005IT
connected components in G is
A. k B. k + 1 C. n − k − 1 D. n − k
Q 25. Let G be an arbitrary graph with n nodes and k components. If a vertex is removed from G, the number 2003
of components in the resultant graph must necessarily lie between
A. k and n B. k − 1 and k + 1 C. k − 1 and n − 1 D. k + 1 and n − k

20
 Algorithms Graphs - Basics and Traversals Page 21 of 54

Q 26. Consider the depth-first-search of an undirected graph with 3 vertices P , Q, and R. Let discovery time 2006IT
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 ) = 5 units f (P ) = 12 units

d(Q) = 6 units f (Q) = 10 units
d(R) = 14 unit f (R) = 18 units

Which one of the following statements is TRUE about the graph?

A. There is only one connected component
B. There are two connected components, and P and R are connected
C. There are two connected components, and Q and R are connected
D. There are two connected components, and P and Q are connected

Q 27. Let G = (V, E) be a directed graph where V is the set of vertices and E the set of edges. Then which 2014Set1
one of the following graphs has the same strongly connected components as G?
A. G1 = (V, E1 ) where E1 = {(u, v) | (u, v) ∈
/ E}
B. G2 = (V, E2 ) where E2 = {(u, v) | (v, u) ∈ E}
C. G3 = (V, E3 ) where E3 = {(u, v) | there is a path of length ≤ 2 from u to v in E}
D. G4 = (V4 , E) where V4 is the set of vertices in G which are not isolated

2.4 Topological Ordering

Q 28. Consider the DAG with V = {1, 2, 3, 4, 5, 6} shown below. 2007

Which of the following is not a topological ordering?

A. 1 2 3 4 5 6
B. 1 3 2 4 5 6

C. 1 3 2 4 6 5
D. 3 2 4 1 6 5

Q 29. Consider the directed graph below given. 2014Set1

Which one of the following is TRUE?

A. The graph does not have any topological ordering.

B. Both PQRS and SRQP are topological orderings.
C. Both PSRQ and SPRQ are topological orderings.
D. PSRQ is the only topological ordering.

Q 30. Consider the following directed graph: 2016Set1

21
 Algorithms Graphs - Basics and Traversals Page 22 of 54

The number of different topological

orderings of the vertices of the graph
is .

Q 31. Consider the directed acyclic graph (DAG) below: 2024DA

Which of the following is/are valid vertex orderings that can be

obtained from a topological sort of the DAG?

A. P Q R S T U V C. P Q R S V U T

B. P R Q V S U T D. P R Q S V T U

2.5 Graph Traversal

Q 32. Level order traversal of a rooted tree can be done by starting the root and performing 2004
A. Preorder traversal B. Inorder traversal C. Depth-first search D. Breadth-first search
Q 33. Which one of the following statements is false? 1994
A. Optimal binary search tree construction can be performed efficiently using dynamic programming.
B. Breadth-first search cannot be used to find connected components of a graph.
C. Given the prefix and postfix walks over a binary tree, the binary tree cannot be uniquely constructed.
D. Depth-first search cannot be used to find connected components of a graph.
Q 34. Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first 2018
search tree of G. Consider the following statements.
(I) No edge of G is a cross edge with respect to TD . (A cross edge in G is between two nodes neither
of which is an ancestor of the other in TD ).
(II) For every edge (u, v) of G, if u is at depth i and v is at depth j in TB , then | i − j |= 1
Which of the statements above must necessarily be true?
A. I only B. II only C. Both I and II D. Neither I nor II

Q 35. Consider a complete binary tree with 7 nodes. Let A denote the set of first 3 elements obtained by 2021Set2
performing Breadth-First Search (BFS) starting from the root. Let B denote the set of first 3 elements
obtained by performing Depth-First Search (DFS) starting from the root.
The value of | A − B | is .

22
 Algorithms Graphs - Basics and Traversals Page 23 of 54

Q 36. (MSQ) Consider the following directed graph: 2021Set2

Which of the following is/are correct about the graph?

A. The graph does not have a topological order.
B. A depth-first traversal starting at vertex S classifies three directed edges as back edges.
C. The graph does not have a strongly connected component.
D. For each pair of vertices u and v, there is a directed path from u to v.
Q 37. Let G be a directed graph and T a depth first search (DFS) spanning tree in G that is rooted at a 2024Set1
vertex v. Suppose T is also a breadth first search (BFS) tree in G, rooted at v. Which of the following
statements is/are TRUE for every such graph G and tree T ?
A. There are no back-edges in G with respect to the tree T
B. There are no cross-edges in G with respect to the tree T
C. There are no forward-edges in G with respect to the tree T
D. The only edges in G are the edges in T
Q 38. (MSQ) Which of the following statements regarding Breadth First Search (BFS) and Depth First 2025Set2
Search (DFS) on an undirected simple graph G is/are TRUE?
A. A DFS tree of G is a Shortest Path tree of G.
B. Every non-tree edge of G with respect to a DFS tree is a forward/back edge.
C. If (u, v) is a non-tree edge of G with respect to a BFS tree, then the distances from the source vertex
s to u and v in the BFS tree are within ±1 of each other.
D. Both BFS and DFS can be used to find the connected components of G.
Q 39. In an adjacency list representation of an undirected simple graph G = (V, E), each edge (u, v) has two 2016Set2
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

2.6 More Questions

Q 40. Consider the following directed graph. TIFR’14

23
 Algorithms Graphs - Basics and Traversals Page 24 of 54

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.

Q 41. Which data structure is commonly used to implement breadth first search in a graph? TIFR’22
A. A queue B. A stack C. A heap D. A hash table E. A splay tree

24
 Algorithms Minimum Spanning Trees Page 25 of 54

Chapter 3 Minimum Spanning Trees

Q 1. How many minimum spanning trees does the following graph have? Draw them (weights are assigned 1995
to the edges).

Q 2. What is the weight of a minimum spanning tree of the following graph? 2003

A. 29
B. 31

C. 38
D. 41

Q 3. The number of distinct minimum spanning trees for the weighted graph below is . 2014Set2

Q 4. Consider the following undirected graph with edge weights as shown: 2021Set1

The number of minimum-weight

spanning trees of the graph is
.

25
 Algorithms Minimum Spanning Trees Page 26 of 54

Q 5. The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is . 2024Set1

Q 6. The number of distinct minimum-weight spanning trees of the following graph is . 2024Set2

Q 7. The graph shown below has 8 edges with distinct integer edge weights. The minimum spanning tree 2015Set1
(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 .

Q 8. Let G be a connected undirected graph of 100 vertices and 300 edges. The weight of a minimum 2015Set3
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 .
Q 9. Let G be a complete undirected graph on 4 vertices, having 6 edges with weights being 1, 2, 3, 4, 5, and 6. 2016Set1
The maximum possible weight that a minimum weight spanning tree of G can have is .
Q 10. Consider the following undirected graph G: 2018

Choose a value for x that will maxi-

mize the number of minimum weight
spanning trees (MWSTs) of G. The
number of MWSTs of G for this value
of x is .

Q 11. The maximum value of x such that the edge between the nodes B and C is included in every minimum 2025Set1
spanning tree of the given graph is . (Answer in integer)

26
 Algorithms Minimum Spanning Trees Page 27 of 54

Q 12. Consider a weighted complete graph G on the vertex set {v1 , v2 , .....vn } such that the weight of the edge 2006
(vi , vj ) is 2|i − j|. The weight of a minimum spanning tree of G is:
 
n
A. n − 1 B. 2n − 2 C. D. n2
2

Q 13. Consider a graph G = (V, E), where V = {v1 , v2 , . . . , v100 }, E = {(vi , vj )|1 ≤ i < j ≤ 100}, and weight 2020
of the edge (vi , vj ) is |i − j| . The weight of minimum spanning tree of G is .

Q 14. A complete undirected, weighted graph G is given on the vertex set {0, 1, . . . , n − 1} for any fixed n. 1996
Draw the minimum spanning tree of G if
(i) The weight of the edge (u, v) is |u − v|
(ii) The weight of the edge (u, v) is u + v

Q 15. Consider a weighted undirected graph with vertex set V = {n1, n2, n3, n4, n5, n6} and edge set E = 2001
{(n1, n2, 2), (n1, n3, 8), (n1, n6, 3), (n2, n4, 4), (n2, n5, 12), (n3, n4, 7), (n4, n5, 9), (n4, n6, 4)}
The third value in each tuple represents the weight of the edge specified in the tuple.
(i) List the edges of a minimum spanning tree of the graph.
(ii) How many distinct minimum spanning trees does this graph have?
(iii) Is the minimum among the edge weights of a minimum spanning tree unique over all possible
minimum spanning trees of a graph?
(iv) Is the maximum among the edge weights of a minimum spanning tree unique over all possible
minimum spanning tree of a graph?
Q 16. An undirected graph G(V, E) contains n (n > 2) nodes named v1 , v2 , . . . , vn . Two nodes vi , vj are 2011
connected if and only if 0 <| i − j |≤ 2. Each edge (vi , vj ) is assigned a weight i + j. A sample graph
with n = 4 is shown below.

(i) 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
(ii) 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

3.1 Kruskal’s algorithm

Q 17. Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph G with n vertices and m 1991
edges has the time complexity of:
A. O(n2 ) B. O(mn) C. O(m + n) D. O(m log n) E. O(m2 )

Q 18. Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph con- 1992
taining n vertices and m edges if the edges are sorted is .

27
 Algorithms Minimum Spanning Trees Page 28 of 54

Q 19. Consider the following graph: 2006

Which one of the following cannot be

the sequence of edges added, in that
order, to a minimum spanning tree
using Kruskal’s algorithm?

A. (a−b), (d−f ), (b−f ), (d−c), (d−e)

B. (a−b), (d−f ), (d−c), (b−f ), (d−e)

C. (d−f ), (a−b), (d−c), (b−f ), (d−e)
D. (d−f ), (a−b), (b−f ), (d−e), (d−c)

Q 20. Consider the following graph: 2009

Which one of the following is NOT the sequence of edges added to the minimum spanning tree using
Kruskal’s algorithm?

A. (b, e) (e, f) (a, c) (b, c) (f, g) (c, d) C. (b, e) (a, c) (e, f) (b, c) (f, g) (c, d)
B. (b, e) (e, f) (a, c) (f, g) (b, c) (c, d) D. (b, e) (e, f) (b, c) (a, c) (f, g) (c, d)

3.2 Prim’s Algorithm

Q 21. Consider the undirected graph below. 2004IT

28
 Algorithms Minimum Spanning Trees Page 29 of 54

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) C. (A, B), (A, D), (D, F), (F, G), (G, E), (F, C)
B. (A, D), (A, B), (A, C), (C, F), (G, E), (F, G) D. (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)

Q 22. For the undirected, weighted graph given below, which of the following sequences of edges represents a 2008IT
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)

3.3 MST Concepts

Q 23. Let G be an undirected graph with distinct edge weights. Let emax be the edge with maximum weight 2000
and emin the edge with minimum weight. Which of the following is false?
A. Every minimum spanning tree of G must contain emin
B. If emax is in a minimum spanning tree, then its removal must disconnect G
C. No minimum spanning tree contains emax
D. G has a unique minimum spanning tree

Q 24. An undirected graph G has n nodes. Its adjacency matrix is given by an n × n square matrix whose (i) 2005
diagonal elements are 0s and (ii) non-diagonal elements are 1s. Which one of the following is TRUE?
A. Graph G has no minimum spanning tree (MST)
B. Graph G has a unique MST of cost n − 1
C. Graph G has multiple distinct MSTs, each of cost n − 1
D. Graph G has multiple minimum spanning trees of different costs.

Q 25. Let G be a weighted undirected graph and e be an edge with maximum weight in G. Suppose there 2005IT
is minimum weight spanning tree in G containing edge e. Which of the following statements is always
true?
A. There exists a cutset in G having all edges of maximum weight.
B. There exists a cycle in G having all edges of maximum weight.
C. Edge e cannot be contained in a cycle.
D. All edges in G have the same weight.
Q 26. Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a 2007
specific edge of weight w. Which of the following is FALSE?

29
 Algorithms Minimum Spanning Trees Page 30 of 54

A. There is a minimum spanning tree containing e

B. If e is not in a minimum spanning tree T , then in the cycle formed by adding e to T , all edges have
the same weight.
C. Every minimum spanning tree has an edge of weight w
D. e is present in every minimum spanning tree

Q 27. What is the largest integer m such that every simple connected graph with n vertices and n edges 2007IT
contains at least m different spanning trees ?
A. 1 B. 2 C. 3 D. n

Q 28. G is a graph on n vertices and 2n − 2 edges. The edges of G can be partitioned into two edge-disjoint 2008
spanning trees. Which of the following is NOT true for G?
A. For every subset of k vertices, the induced subgraph has at most 2n − 2 edges.
B. The minimum cut in G has at least 2 edges.
C. There are at least 2 edge-disjoint paths between every pair of vertices.
D. There are at least 2 vertex-disjoint paths between every pair of vertices.
Q 29. Let G be a weighted graph with edge weights greater than one and G′ be the graph constructed by 2012
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 C. T ′ ̸= T but total weight t′ = t2

B. T ′ = T with total weight t′ < t2 D. None of the above

Q 30. G = (V, E) is an undirected simple graph in which each edge has a distinct weight, and e is a particular 2016Set1
edge of G. Which of the following statements about the minimum spanning trees(MSTs) 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

Q 31. Let G be any connected, weighted, undirected graph. 2019
I. G has a unique minimum spanning tree, if no two edges of G have the same weight.
II. G has a unique minimum spanning tree, if, for every cut of G, there is a unique minimum-weight
edge crossing the cut.

Which of the following statements is/are TRUE?

A. I only B. II only C. Both I and II D. Neither I nor II
Q 32. Let G = (V, E) be a weighted undirected graph and let T be a Minimum Spanning Tree (MST) of G 2020
maintained using adjacency lists. Suppose a new weighed edge (u, v) ∈ V × V is added to G. The worst
case time complexity of determining if T is still an MST of the resultant graph is
A. Θ(| E | + | V |) B. Θ(| E || V |) C. Θ(| E | log | V |) D. Θ(| V |)

Q 33. Let G be a connected undirected weighted graph. Consider the following two statements. 2021Set2
S1 : There exists a minimum weight edge in G which is present in every minimum spanning tree of
G.
S2 : If every edge in G has distinct weight, then G has a unique minimum spanning tree.
Which one of the following options is correct?

30
 Algorithms Minimum Spanning Trees Page 31 of 54

A. Both S1 and S2 are true C. S1 is false and S2 is true

B. S1 is true and S2 is false D. Both S1 and S2 are false

Q 34. (MSQ) Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which 2022
of the following statements about the minimum spanning trees of G is/are TRUE?
A. The edge with the second smallest weight is always part of any minimum spanning tree of G.
B. One or both of the edges with the third smallest and the fourth smallest weights are part of any
minimum spanning tree of G.
C. Suppose S ⊆ V be such that S = ̸ ϕ and S ̸= V . Consider the edge with the minimum weight
such that one of its vertices is in S and the other in V /S. Such an edge will always be part of any
minimum spanning tree of G.
D. G can have multiple minimum spanning trees.
Q 35. Let G(V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed 2022
edges, as defined by the following adjacency matrix A.

1, 1 ≤ j ≤ i ≤ 5
A[i][j] =
0, otherwise
A[i][j] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at
r ∈ V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a
directed path from r to every other vertex in V . The number of such directed spanning trees rooted at
vertex 5 is .
Q 36. Let G be an undirected connected graph in which every edge has a positive integer weight. Suppose 2024Set2
that every spanning tree in G has even weight. Which of the following statements is/are TRUE for every
such graph G?
A. All edges in G have even weight
B. All edges in G have even weight OR all edges in G have odd weight
C. In each cycle C in G, all edges in C have even weight
D. In each cycle C in G, either all edges in C have even weight OR all edges in C have odd weight

3.4 More Questions

Q 37. Let G be a connected simple graph (no self-loops or parallel edges) on n ≥ 3 vertices, with distinct TIFR’11
edge weights. Let e1 , e2 , ..., em be an ordering of the edges in decreasing order of weight. Which of the
following statements is FALSE?
A. The edge e1 has to be present in every maximum weight spanning tree.
B. Both e1 and e2 have to be present in every maximum weight spanning tree.
C. The edge em has to be present in every minimum weight spanning tree.
D. The edge em is never present in any maximum weight spanning tree.
E. G has a unique maximum weight spanning tree.

Q 38. In a connected weighted graph with n vertices, all the edges have distinct positive integer weights. Then, TIFR’13
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

31
 Algorithms Minimum Spanning Trees Page 32 of 54

Q 39. Let G = (V, E) be an undirected weighted graph with all edge weights being positive. Design an efficient ISI’14
algorithm to find the maximum spanning tree of G.

Q 40. Consider the following undirected graph with some edge costs missing. TIFR’14

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.

Q 41. Let G = (V, E) be an undirected connected simple (i.e., no parallel edges or self-loops) graph with TIFR’14
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?
A. The tree T has to contain the edge e1 .
B. The tree T has to contain the edge e2 .
C. The minimum weight edge incident on each vertex has to be present in T .
D. T is the unique minimum spanning tree in G.
E. If we replace each edge weight wi = w(ei ) by its square wi2 , then T must still be a minimum spanning
tree of this new instance.
Q 42. Consider the following undirected connected graph G with weights on its edges as given in the figure TIFR’15
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.

32
 Algorithms Minimum Spanning Trees Page 33 of 54

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.

Q 43. How many distinct minimum weight spanning trees does the following undirected, weighted graph have? TIFR’18

A. 1
B. 2
C. 4
D. 6

E. 8

Q 44. Let n ≥ 3, and let G be a simple, connected, undirected graph with the same number n of vertices TIFR’18
and edges. Each edge of G has a distinct real weight associated with it. Let T be the minimum weight
spanning tree of G. Which of the following statements is NOT ALWAYS TRUE ?
A. The minimum weight edge of G is in T .
B. The maximum weight edge of G is not in T .
C. G has a unique cycle C and the minimum weight edge of C is also in T .
D. G has a unique cycle C and the maximum weight edge of C is not in T.
E. T can be found in O(n) time from the adjacency list representation of G.

Q 45. How many distinct minimum weight spanning trees does the following undirected, weighted graph have TIFR’19
?

A. 8 B. 16 C. 32 D. 64 E. None of the above

Q 46. Let G be a connected bipartite simple graph (i.e., no parallel edges) with distinct edge weights. Which TIFR’21
of the following statements on MST (minimum spanning tree) need NOT be true?
A. G has a unique MST.
B. Every MST in G contains the lightest edge.
C. Every MST in G contains the second lightest edge.
D. Every MST in G contains the third lightest edge.
E. No MST in G contains the heaviest edge.

33
 Algorithms Minimum Spanning Trees Page 34 of 54

Q 47. Let G be an undirected connected graph with distinct edge weights. Let emax be the edge with maximum CMI’24
weight and emin the edge with minimum weight. What can you say about the following statements?
(I) Every minimum spanning tree of G must contain emin
(II) Every minimum spanning tree must exclude emax

A. I is True, but II is False C. Both I and II are False

B. I is False, but II is True D. Both I and II are True

Q 48. Let G = (V, E) be a weighted, undirected and connected graph, with weight 1 ≤ wtG (e) ≤ 99 for TIFR’25
edge e ∈ E. Suppose G′ is the graph with the same set of vertices and edges, but with edge weights
wtG′ (e) = 100 − wtG (e). Assume that |V | is an even number.
Consider the following statements.
(i) Any minimum-weight spanning-tree of G is also a maximum-weight spanning tree of G′ .
(ii) For any pair of vertices s, t ∈ V , any shortest path from s to t in G is also a longest path from s to
t in G′ .
(iii) Any minimum-weight perfect matching of G is also a maximum-weight perfect matching of G′ .
Which of the above statements ALWAYS TRUE for any such graphs G,G′ ?
A. Only (i) and (ii) B. Only (i) and (iii) C. Only (ii) and (iii) D. (i), (ii) and (iii) E. None of (i), (ii)
or (iii) is always true.

34
 Algorithms Graph Traversals Page 35 of 54

Chapter 4 Graph Traversals

Q 1. In an unweighted, undirected connected graph, the shortest path from a node S to every other node is 2007
computed most efficiently, in terms of time complexity, by

A. Dijkstra’s algorithm starting from S C. Performing a DFS starting from S

B. Warshall’s algorithm. D. Performing a BFS starting from S

Q 2. Let G be any undirected graph with positive edge weights, and T be a minimum spanning tree of G. 2025Set1
For any two vertices, u and v, let d1 (u, v) and d2 (u, v) be the shortest distances between u and v in G
and T , respectively. Which ONE of the options is CORRECT for all possible G, T , u and v?

A. d1 (u, v) = d2 (u, v) C. d1 (u, v) ≥ d2 (u, v)

B. d1 (u, v) ≤ d2 (u, v) D. d1 (u, v) ̸= d2 (u, v)

Q 3. Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant 2025Set2
α is added to the weight of every edge. Which ONE of the following statements is TRUE about the
minimum spanning trees (MSTs) and shortest paths (SPs) in G before and after the edge weight update?
A. Every MST remains an MST, and every SP remains an SP.
B. MSTs need not remain MSTs, and every SP remains an SP.
C. Every MST remains an MST, and SPs need not remain SPs.
D. MSTs need not remain MSTs, and SPs need not remain SPs.

4.1 Single Source Shortest Path

Q 4. Let G be a directed graph whose vertex set is the set of number from 1 to 100. There is an edge from a 2005IT
vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from
vertex 1 to 100 is:
A. 4 B. 7 C. 23 D. 99
Q 5. Consider a weighted, undirected graph with positive edge weights and let uv be an edge in the graph. It 2007IT
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 C. weight(u, v) ≥ 12
B. weight(u, v) = 12 D. weight(u, v) > 12

Q 6. Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below 2010
is the weight of the edge {i, j}
 
0 1 8 1 4
1 0 12 4 9
 
W = 8 12 0 7 3

1 4 7 0 2
4 9 3 2 0
(i) 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
(ii) 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

35
 Algorithms Graph Traversals Page 36 of 54

Q 7. Let G(V, E) be an undirected and unweighted graph with 100 vertices. Let d(u, v) denote the number 2025Set1
of edges in a shortest path between vertices u and v in V . Let the maximum value of d(u, v), u, v ∈ V
such that u ̸= v, be 30. Let T be any breadth first-search tree of G. Which ONE of the given options is
CORRECT for every such graph G?

A. The height of T is exactly 15. C. The height of T is at least 15.

B. The height of T is exactly 30. D. The height of T is at least 30.

Q 8. Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed 2004
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

Q 9. 2008
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
Q 10. Consider the directed graph shown in the figure below. There are multiple shortest paths between 2012
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

Q 11. To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, 2006
the data structure to be used is:

36
 Algorithms Graph Traversals Page 37 of 54

A. Queue B. Stack C. Heap D. B-Tree

Q 12. Let G(V, E) be an undirected graph with positive edge weights. Dijkstra’s single source shortest path 2005
algorithm can be implemented using 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 |)

Q 13. What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph 2013
of n vertices?
A. θ(n2 ) B. θ(n2 log n) C. θ(n3 ) D. θ(n3 log n)

Q 14. Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm? 2009
P: Always finds a negative weighted cycle, if one exists.
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
Q 15. Let G = (V, E) be an undirected graph with a subgraph G1 = (V1 , E1 ). Weights are assigned to edges 2003
of G as follows:
(
0, if e ∈ E1
w(e) =
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?
A. The number of edges in the shortest paths from v1 to all vertices of G
B. G1 is connected
C. V1 forms a clique in G
D. G1 is a tree

4.2 All Pairs Shortest Path

Q 16. Which of the following algorithm design techniques is used in finding all pairs of shortest distances in a 1998
graph?
A. Dynamic programming B. Backtracking C. Greedy D. Divide-and-Conquer

Q 17. The Floyd-Warshall algorithm for all-pair shortest paths computation is based on 2016Set2
A. Greedy paradigm.
B. Divide-and-Conquer paradigm.
C. Dynamic Programming paradigm.
D. neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

Q 18. Consider the weighted undirected graph with 4 vertices, where the weight of edge {i, j} is given by the 2016Set1
entry Wij in the matrix W .
 
0 2 8 5
2 0 5 8 
 
8 5 0 x
5 8 x 0
The largest possible integer value of x, for which at least one shortest path between some pair of vertices
will contain the edge with weight x is .
Q 19. Let s and t be two vertices in a undirected graph G = (V, E) having distinct positive edge weights. Let 2005
[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 .

37
 Algorithms Graph Traversals Page 38 of 54

(i) The edge e must definitely belong to:

A. the minimum weighted spanning tree of G
B. the weighted shortest path from s to t
C. each path from s to t
D. the weighted longest path from s to t
(ii) 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 congestion 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?
A. a path from s to t in the minimum weighted spanning tree
B. a weighted shortest path from s to t
C. an Euler walk from s to t
D. a Hamiltonian path from s to t

Q 20. Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge 2016Set1
weight is increased by the same value, then which of the following statements is/are TRUE?
P: Minimum spanning tree of G does not change.
Q: Shortest path between any pair of vertices does not change.
A. P only B. Q only C. Neither P nor Q D. Both P and Q

Q 21. Let G = (V, E) be any connected, undirected, edge-weighted graph. The weights of the edges in E are 2017Set1
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
Which of the above statements is/are necessarily true?
A. (I) only B. (II) only C. both (I) and (II) D. neither (I) nor (II)

Q 22. Let G = (V, E) be a directed, weighted graph with weight function w : E → R. For some function 2020
f : V → R, for each edge (u, v) ∈ E, define w′ (u, v) as w(u, v) + f (u) − f (v).
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in G under w are shortest paths under w′ too, ”.
A. for every f : V → R
B. if and only if ∀u ∈ V, f (u) is positive
C. if and only if ∀u ∈ V, f (u) is negative
D. if and only if f (u) is the distance from s to u in the graph obtained by adding a new vertex s to G
and edges of zero weight from s to every vertex of G

Q 23. In a directed acyclic graph with a source vertex s, the quality-score of a directed path is defined to be the 2021Set2
product of the weights of the edges on the path. Further, for a vertex v other than s, the quality-score of
v is defined to be the maximum among the quality-scores of all the paths from s to v. The quality-score
of s is assumed to be 1.

38
 Algorithms Graph Traversals Page 39 of 54

The sum of the quality-scores of all vertices on the graph shown above is .

Q 24. Let G be a simple, unweighted, and undirected graph. A subset of the vertices and edges of G are shown 2025DA
below.

It is given that a − b − c − d is a shortest path between a and d ; e − f − g − h is a shortest path between

e and h; a − f − c − h is a shortest path between a and h. Which of the following is/are NOT the edges
of G?
A. (b, d) B. (b, g) C. (b, h) D. (e, g)

Q 25. Fill in the blanks in the following template of an algorithm to compute all pairs of shortest path lengths 2002
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.
INITIALIZATION : for i = 1 ... n
{ for j = 1 ... n
{ if a [i , j ] = 0 then P [i , j ] = _______ else P [i , j ] = _______ ;}
}

ALGORITHM : for i = 1 ... n

{ for j = 1 ... n
{ for k = 1 ... n
{ P [ __ , __ ] = min { _______ , ______ }; }
}
}

(i) Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
(ii) Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
(iii) Fill in the blank: The running time of the Algorithm is O( ).

Q 26. Let G = (V, E) be a directed graph with n vertices. A path from vi to vj in G is a sequence of vertices 2003
vi , vi+1 , . . . , vj such that (vk , vk+1 ) ∈ E for all k in i through j − 1. A simple path is a path in which no
vertex appears more than once.
Let A be an n × n array initialized as follows:
(
1, if (j, k) ∈ E
A[j, k] =
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

39
 Algorithms Graph Traversals Page 40 of 54

D. If there exists a path from j to k, every simple path from j to k contains at most A[j, k] edges

Q 27. Let G = (V, E) be an undirected unweighted connected graph. The diameter of G is defined as: 2021Set1

diam(G) = max {the length of shortest path between u and v}

u,v∈V

Let M be the adjacency matrix of G.

Define graph G2 on the same set of vertices with adjacency matrix N , where

1 if Mij > 0 or Pij > 0, where P = M 2


Nij =
0 otherwise

Which one of the following statements is true?

A. diam(G2 ) ≤ ⌈diam(G)/2⌉ C. diam(G2 ) = diam(G)

B. ⌈diam(G)/2⌉ < diam(G2 ) < diam(G) D. diam(G) < diam(G2 ) ≤ 2 diam(G)

4.3 More Questions

Q 28. Given a weighted directed graph with n vertices where edge weights are integers (positive, zero, or TIFR’13
negative), determining whether there are paths of arbitrarily large weight can be performed in time
A. O(n)
B. O(n. log(n)) but not O(n)
C. O(n1.5 ) but not O(n log n)
D. O(n3 ) but not O(n1.5 )
E. O(2n ) but not O(n3 )

Q 29. The figure below describes the network of streets in a city where Motabhai sells pakoras from his cart. TIFR’20
The number next to an edge is the time (in minutes) taken to traverse the corresponding street.

At present, the cart is required to start at point s and, after visiting each street at least once, reach
point t. For example, Motabhai can visit the streets in the following order
s−a−c−s−e−c−d−a−b−d−f −e−d−b−t−f −d−t
in order to go from s to t. Note that the streets {b, d} and {d, f } are both visited twice in this strategy.
The total time taken for this trip is 440 minutes [which is, 380 (the sum of traversal times of all streets
in the network) +60 (the sum of the traversal times of streets {b, d} and {d, f }].

40
 Algorithms Graph Traversals Page 41 of 54

Motabhai now wants the cart to return to s at the end of the trip. So the previous strategy is not valid,
and he must find a new strategy. How many minutes will Motabhai now take if he uses an optimal
strategy?
Hint: s, t, b and f are the only odd degree nodes in the figure above.
A. 430 B. 440 C. 460 D. 470 E. 480
Q 30. In a connected graph, any two paths of maximum length: CMI’23
A. have at least one vertex in common, but not necessarily an edge in common
B. have at least one edge in common
C. have at least two common vertices, but not necessarily an edge in common
D. have at least two edges in common
Q 31. Let G be a directed graph with distinct and nonnegative edge weights. Let s be a starting vertex and t CMI’24
a destination vertex. Assume that G has at least one s − t path. What can you say about the following
statements?
(I) Every shortest s − t path (minimum weight) must include the minimum-weight edge of G.
(II) Every shortest s − t path must exclude the maximum-weight edge of G.

A. I is True, but II is False C. Both I and II are False

B. I is False, but II is True D. Both I and II are True

Q 32. Given a directed graph G and an initial vertex s, we would like to explore the graph from s, that is, TIFR’25
starting from s see all vertices along a path.
For example, the graph on the left side below cannot be explored from s since there does not exist a path
along which we can visit all vertices starting from s while the graph on the right side can be explored
from s by following the path s → u → s → t.

Which of the following is TRUE?

A. There exists a polynomial time algorithm to explore the graph from s.
B. There exists an exponential time algorithm to explore the graph from s but there does not exist any
polynomial time algorithm.
C. There exists an algorithm to explore the graph from s but it is not known if it runs in exponential
time.
D. The decidability of the problem is open.
E. The halting problem of Turing machine can be reduced to checking if a graph can be explored from
s.
Q 33. Let G be an undirected graph. For any pair of vertices s, t in G, let MinCut(s, t) be the least number TIFR’25
of edges that have to be deleted from G so that there is no s − t path in the resulting graph. Let a, b, c
be three vertices in G such that MinCut(a, b) ≥ MinCut(b, c) ≥ MinCut(a, c). Consider the following
statements.
(i) MinCut(a, b) > MinCut(b, c) > MinCut(a, c).
(ii) MinCut(a, b) = MinCut(b, c) > MinCut(a, c).
(iii) MinCut(a, b) > MinCut(b, c) = MinCut(a, c).
(iv) MinCut(a, b) = MinCut(b, c) = MinCut(a, c).
Which of the above statements are possible?

41
Algorithms Graph Traversals Page 42 of 54

A. Only (i) and (ii) D. Only (ii), (iii), (iv)

B. Only (ii) and (iii)
C. Only (iii) and (iv) E. All of (i), (ii), (iii), (iv)

42
 Algorithms Greedy and Dynamic Programming Page 43 of 54

Chapter 5 Greedy and Dynamic Programming

Q 1. Two matrices M1 and M2 are to be stored in arrays A and B respectively. Each array can be stored 2004
either in row-major or column-major order in contiguous memory locations. The time complexity of an
algorithm to compute M1 × M2 will be:
A. Best if A is in row-major, and B is in column-major order
B. Best if both are in row-major order
C. Best if both are in column-major order
D. Independent of the storage scheme
Q 2. Four Matrices M1,M2,M3 and M4 of dimensions p×q, q×r, r×s and s×t respectively can be multiplied 2011
in several ways with different number of total scalar multiplications. For example when multiplied as
((M1×M2)×(M3×M4)), the total number of scalar multiplications is pqr+rst+prt. When multiplied as
(((M1×M2)×M3)×M4), the total number of scalar multiplications is pqr+prs+pst.
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
Q 3. Let A1 , A2 , A3 and A4 be four matrices of dimensions 10× 5, 5×20, 20×10 and 10×5, respectively. 2016Set2
The minimum number of scalar multiplications required to find the product A1 A2 A3 A4 using the basic
matrix multiplication method is .
Q 4. Assume that multiplying a matrix G1 of dimension p × q with another matrix G2 of dimension q × r 2018
requires pqr scalar multiplications. Computing the product of n matrices G1 G2 G3 . . . Gn can be done by
parenthesizing in different ways. Define Gi Gi+1 as an explicitly computed pair for a given paranthe-
sization if they are directly multiplied. For example, in the matrix multiplication chain G1 G2 G3 G4 G5 G6
using parenthesization (G1 (G2 G3 ))(G4 (G5 G6 )), G2 G3 and G5 G6 are only explicitly computed pairs.
Consider a matrix multiplication chain F1 F2 F3 F4 F5 , where matrices F1 , F2 , F3 , F4 and F5 are of dimen-
sions 2 × 25, 25 × 3, 3 × 16, 16 × 1 and 1 × 1000, respectively. In the parenthesization of F1 F2 F3 F4 F5 that
minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
A. F1 F2 and F3 F4 only B. F2 F3 only C. F3 F4 only D. F1 F2 and F4 F5 only

Q 5. Consider the weights and values of items listed below. Note that there is only one unit of each item. 2018
Item number Weight (in Kgs) Value (in rupees)
1 10 60
2 7 28
3 4 20
4 2 24
The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and
their total value is maximized. Moreover, no item may be split. The total value of items picked by an
optimal algorithm is denoted by Vopt . A greedy algorithm sorts the items by their value-to-weight ratios
in descending order and packs them greedily, starting from the first item in the ordered list. The total
value of items picked by the greedy algorithm is denoted by Vgreedy .
The value of Vopt − Vgreedy is .

Q 6. We are given 9 tasks T1 , T2 , . . . , T9 . The execution of each task requires one unit of time. We can execute 2005
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 dth i 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
(i) Are all tasks completed in the schedule that gives maximum profit?

43
 Algorithms Greedy and Dynamic Programming Page 44 of 54

A. All tasks are completed C. T1 and T8 are left out

B. T1 and T6 are left out D. T4 and T6 are left out

(ii) What is the maximum profit earned?

A. 147 B. 165 C. 167 D. 175
Q 7. Consider n jobs J1 , J2 . . . Jn such that job Ji has execution time ti P
and a non-negative integer weight wi . 2007IT
n
i=1 wi Ti
The weighted mean completion time of the jobs is defined to be P, where Ti is the completion
n
i=1 wi
time of job Ji . Assuming that there is only one processor available, in what order must the jobs be
executed in order to minimize the weighted mean completion time of the jobs?

A. Non-decreasing order of ti C. Non-increasing order of wi ti

B. Non-increasing order of wi D. Non-increasing order of wi /ti

Q 8. The subset-sum problem is defined as follows: Given a set S of n positive integers and a positive integer 2008
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
Q 9. The subset-sum problem is defined as follows. Given a set of n positive integers, S = {a1 , a2 , a3 , . . . , an }, 2008
and positive integer W , is there a subset of S whose elements sum to W ? A dynamic program for solving
this problem uses a 2-dimensional Boolean array, X, with n rows and W + 1 columns. X[i, j], 1 ≤ i ≤
n, 0 ≤ j ≤ W , is TRUE, if and only if there is a subset of {a1 , a2 , . . . , ai } whose elements sum to j.
(i) Which of the following is valid for 2 ≤ i ≤ n, and ai ≤ j ≤ W
A. X[i, j] = X[i − 1, j] ∨ X[i, j − ai ]
B. X[i, j] = X[i − 1, j] ∨ X[i − 1, j − ai ]
C. X[i, j] = X[i − 1, j] ∧ X[i, j − ai ]
D. X[i, j] = X[i − 1, j] ∧ X[i − 1, j − ai ]
(ii) 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]

Q 10. A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) 2009
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.
(i) 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]
Which one of the following options is correct?

A. expr1 = l(i-1, j) +1 C. expr2 = max(l(i-1,j),l(i,j-1))

B. expr1 = l(i,j-1) D. expr2 = max(l(i-1,j-1),l(i,j))

(ii) 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)?

44
 Algorithms Greedy and Dynamic Programming Page 45 of 54

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 < rorq < s.

Q 11. The weight of a sequence a0 , a1 , . . . , an−1 of real numbers is defined as a0 + a1 /2 + · · · + an−1 /2n−1 . A 2010
subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order
of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of
ao , a1 , . . . , an−1 and Y the maximum possible weight of a subsequence of a1 , a2 , . . . , an−1 . Then X is
equal to
A. max(Y, a0 + Y ) B. max(Y, a0 + Y /2) C. max(Y, a0 + 2Y ) D. a0 + Y /2

Q 12. An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array 2011
A[0 : n − 1] is given below.
Let Li , denote the length of the longest monotonically increasing sequence starting at index i in the
array.
Initialize Ln−1 = 1
For all i such that 0 ≤ i ≤ n − 2
(
1 + Li+1 if A[i] ¡ A[i+1]
Li =
1 Otherwise
Finally, the length of the longest monotonically increasing sequence is max (L0 , L1 , . . . , Ln−1 ).
Which of the following statements is TRUE?
A. The algorithm uses dynamic programming paradigm
B. The algorithm has a linear complexity and uses branch and bound paradigm
C. The algorithm has a non-linear polynomial complexity and uses branch and bound paradigm
D. The algorithm uses divide and conquer paradigm

Q 13. Consider two strings A=“qpqrr” and B=“pqprqrp”. Let x be the length of the longest common subse- 2014Set2
quence (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 = .

Q 14. Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a 2014Set3
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 .

Q 15. Consider a sequence of 14 elements: A = [−5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0]. The sequence 2019
sum S(i, j) = Σjk=i A[k]. Determine the maximum of S(i, j), where 0 ≤ i ≤ j < 14. (Divide and conquer
approach may be used.)
Answer: .
Q 16. Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of 2024Set2
array locations with consecutive indices.
The C code snippet given below has been written to compute the length of the longest subarray of X
that contains at most two distinct integers. The code has two missing expressions labelled (P) and (Q).
int first =0 , second =0 , len1 =0 , len2 =0 , maxlen =0;
for ( int i =0; i < n ; i ++) {
if ( X [ i ] == first ) {
len2 ++; len1 ++;

45
 Algorithms Greedy and Dynamic Programming Page 46 of 54

} else if ( X [ i ] == second ) {
len2 ++;
len1 = ( P );
second = first ;
} else {
len2 = ( Q );
len1 = 1; second = first ;
}
if ( len2 > maxlen ) {
maxlen = len2 ;
}
first = X [ i ];
}

Which one of the following options gives the CORRECT missing expressions?
(Hint: At the end of the i-th iteration, the value of len1 is the length of the longest subarray ending
with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with
X[i] that contains at most two distinct values.)

A. (P) len1 + 1 (Q) len2 + 1 C. (P) 1 (Q) len2 + 1

B. (P) 1 (Q) len1 + 1 D. (P) len2 + 1 (Q) len1 + 1

Q 17. (MSQ) Define Rn to be the maximum amount earned by cutting a rod of length n meters into one or 2021Set1
more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose
length is i meters. Consider the array of prices:

p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18

Which of the following statements is/are correct about R7 ?

A. R7 = 18
B. R7 = 19
C. R7 is achieved by three different solutions
D. R7 cannot be achieved by a solution consisting of three pieces

5.1 More Questions

Q 18. Consider the following inventory problem. You are running a company that sells lorries. Predictions tell CMI’22
you the quantity of sales to expect over the next n months. Let di denote the number of sales expected
in month i. We assume that sales happen on the first of the month, and that lorries not sold are stored
till the start of the next month. You can store at most C lorries, and it costs R to store each lorry for a
month. You receive lorries from the manufacturer in shipments, each of which has a transportation fee
of F (regardless of the number of lorries ordered). You start out with no lorries. Your aim is to place
orders (say li is the number of lorries ordered in month i ) so as to satisfy the following constraints:
• For each i, the number of lorries on hand at the start of month i (li + whatever is stored from the
previous month) is enough to meet the demand di .
• For each i, the number of lorries left over after meeting the demand di should not exceed the
storage capacity C. The aim is to determine the orders (l1 , . . . , ln ) that will minimize the overall
transportation fee and the overall storage cost. For example, if n = 4, and the demands for each
month is given by 10, 11, 8, 12, and if F = 50, while R = 2 and C = 10, then here are a few possible
scenarios.

46
Algorithms Greedy and Dynamic Programming Page 47 of 54

Month 1 2 3 4 Total
di 10 11 8 12
li 10 11 8 12
Cost 50 50 50 50 200
li 20 11 0 10
Cost 50 + 10 × 2 50 + 10 × 2 2×2 50 194
li 10 19 0 12
Cost 50 50 + 8 × 2 0 50 166

Let ci (S) denote the minimal cost of transportation and storage to meet demands from month i till
month n, given that we have S lorries left over at the start of month i, while satisfying the storage
requirements.
(i) Write an expression for cn (S).
(ii) Express ci (S) in terms of ci+1 (S ′ ) for appropriate values of S ′ .
(iii) Convert the above equations into a dynamic programming algorithm that computes c1 (0). Your
algorithm must run in time polynomial in n and C.

47
 Algorithms Combined Page 48 of 54

Chapter 6 Combined
Q 1. Match the pair in the following questions: 1989
(a) O(log n) (p) Heapsort
(b) O(n) (q) Depth-first search
(c) O(n log n) (r) Binary search
(d) O(n2 ) (s) Selection of the k th smallest element in a set of n elements

Q 2. Match the pairs in the following questions: 1990

(a) Strassen’s matrix multiplication algorithm (p) Greedy method
(b) Kruskal’s minimum spanning tree algorithm (q) Dynamic programming
(c) Biconnected components algorithm (r) Divide and Conquer
(d) Floyd’s shortest path algorithm (s) Depth-first search

Q 3. Match the pairs in the following questions: 1990

(a) A heap construction (p) Ω(n log10 n)
(b) Constructing Hashtable with linear probing (q) O(n)
(c) AVL tree construction (r) O(n2 )
(d) Digital trie construction (s) O(n log10 n)

Q 4. Match the pairs in the following questions by writing the corresponding letters only. 1991
n!
A. The number of distinct binary tree P. 2
with n nodes.
3n


B. The number of binary strings of the length Q. n
of 2n with an equal number of 0’s and 1’s
2n


C. The number of even permutation of n objects. R. n

1 2n


D. The number of binary strings of length 6n S. 1+n n
which are palindromes with 2n 0’s.

Q 5. Which of the following statements is true? 1995

1. As the number of entries in a hash table increases, the number of collision increases
2. Recursive programs are efficient
3. The worst-case complexity for quick sort is O(n2 )
4. Binary search using a linear linked list is efficient

A. 1 and 2 B. 2 and 3 C. 1 and 4 D. 1 and 3

Q 6. The correct matching for the following pairs is 1997
A. All pairs shortest path 1. Greedy
B. Quick Sort 2. Depth-First Search
C. Minimum weight spanning tree 3. Dynamic Programming
D. Connected Components 4. Divide and Conquer

Q 7. Give the correct matching for the following pairs. 1998

(A) O(log n) (P) Selection
(B) O(n) (Q) Insertion sort
(C) O(n log n) (R) Binary search
(D) O(n2 ) (S) Merge sort

48
 Algorithms Combined Page 49 of 54

A. A – R, B – P, C – Q, D – S C. A – P, B – R, C – S, D – Q
B. A – R, B – P, C – S, D – Q D. A – P, B – S, C – R, D – S

Q 8. The most appropriate matching for the following pairs 2000

X: depth first search 1: heap
Y: breadth first search 2: queue
Z: sorting 3: stack
A. X - 1, Y - 2, Z - 3 B. X - 3, Y - 1, Z - 2 C. X - 3, Y - 1, Z - 2 D. X - 2, Y - 3, Z - 1

Q 9. Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence 2004IT
relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.
Recursive Algorithm Recurrence Relation
P Binary search l. T (n) = T (n − k) + T (k) + cn
Q. Merge sort ll. T (n) = 2T (n − 1) + 1
R. Quick sort lll. T (n) = 2T (n/2) + cn
S. Tower of Hanoi lV. T (n) = T (n/2) + 1
Which of the following is the correct match between the algorithms and their recurrence relations?

A. P-II, Q-III, R-IV, S-I C. P-III, Q-II, R-IV, S-I

B. P-IV, Q-III, R-I, S-II D. P-IV, Q-II, R-I, S-III

Q 10. In the following table, the left column contains the names of standard graph algorithms and the right 2005IT
column contains the time complexities of the algorithms. Match each algorithm with its time complexity
1. Bellman-Ford algorithm A: O(m log n)
2. Kruskal’s algorithm B: O(n3 )
3. Floyd-Warshall algorithm C: O(nm)
4. Topological sorting D: O(n + m)
A. 1→ C, 2 → A, 3 → B, 4 → D C. 1→ C, 2 → D, 3 → A, 4 → B
B. 1→ B, 2 → D, 3 → C, 4 → A D. 1→ B, 2 → A, 3 → C, 4 → D

Q 11. Match the following: 2015Set1

P. Prim’s algorithm for minimum spanning tree i. Backtracking
Q. Floyd-Warshall algorithm for all pairs shortest path ii. Greedy method
R. Merge sort iii. Dynamic programming
S. Hamiltonian circuit iv. Divide and conquer
A. P-iii, Q-ii, R-iv, S-i B. P-i, Q-ii, R-iv, S-iii C. P-ii, Q-iii, R-iv, S-i D. P-ii, Q-i, R-iii, S-iv

Q 12. Given below are some algorithms, and some algorithm design paradigms. 2015Set2
1. Dijkstra’s Shortest Path i. Divide and Conquer
2. Floyd-Warshall algorithm to compute ii. Dynamic Programming
all pairs shortest path
3. Binary search on a sorted array iii. Greedy design
4. Backtracking search on a graph iv. Depth-first search
v. Breadth-first search
Match the above algorithms on the left to the corresponding design paradigm they follow.

A. 1-i, 2-iii, 3-i, 4-v C. 1-iii, 2-ii, 3-i, 4-iv

B. 1-iii, 2-iii, 3-i, 4-v D. 1-iii, 2-ii, 3-i, 4-v

49
 Algorithms Combined Page 50 of 54

Q 13. Consider the following table: 2017Set1

Algorithms Design Paradigms
P. Kruskal i. Divide and Conquer
Q. Quicksort ii. Greedy
R. Floyd-Warshall iii. Dynamic Programming
Match the algorithms to the design paradigms they are based on.

A. (P) ↔ (ii), (Q) ↔ (iii), (R) ↔ (i) C. (P) ↔ (ii), (Q) ↔ (i), (R) ↔ (iii)
B. (P) ↔ (iii), (Q) ↔ (i), (R) ↔ (ii) D. (P) ↔ (i), (Q) ↔ (ii), (R) ↔ (iii)

Q 14. Match the algorithms with their time complexities: 2017Set2

Algorithms Time Complexity
P. Tower of Hanoi with n disks i. Θ(n2 )
Q. Binary Search given n sorted numbers ii. Θ(n log n)
R. Heap sort given n numbers at the worst case iii. Θ(2n )
S. Addition of two n × n matrices iv. Θ(log n)

A. P→ (iii) Q→(iv) r →(i) S →(ii) C. P→ (iii) Q →(iv) r →(ii) S→(i)

B. P→ (iv) Q→(iii) r →(i) S→(ii) D. P→ (iv) Q →(iii) r →(ii) S→(i)

6.1 Extras

Q 15. How many substrings of different lengths (non-zero) can be formed from a character string of length n? 1998
2 n
A. n B. n C. 2 D. n(n + 1)/2

Q 16. If n is a power of 2, then the minimum number of multiplications needed to compute an is 1999
√
A. log2 n B. n C. n − 1 D. n

Q 17. A data structure is required for storing a set of integers such that each of the following operations can 2003
be done in O(log n) time, where n is the number of elements in the set
1. Deletion of the smallest element
2. Insertion of an element if it is not already present in the set

Which of the following data structures can be used for this purpose?
A. A heap can be used but not a balanced binary search tree
B. A balanced binary search tree can be used but not a heap
C. Both balanced binary search tree and heap can be used
D. Neither balanced search tree nor heap can be used
Q 18. The cube root of a natural number n is defined as the largest natural number m such that (m3 ≤ n). 2003
The complexity of computing the cube root of n (n is represented by binary notation) is
A. O(n) but not O(n0.5 )
B. O(n0.5 ) but not O((log n)k ) for any constant k > 0
C. O((log n)k ) for some constant k > 0, but not O((log log n)m ) for any constant m > 0
D. O((log log n)k ) for some constant k > 0.5, but not O((log log n)0.5 )

Q 19. The time complexity of computing the transitive closure of a binary relation on a set of n elements is 2005
known to be:  3

A. O(n) B. O(n log n) C. O n 2 D. O n3

50
 Algorithms Combined Page 51 of 54

Q 20. Given two arrays of numbers a1 , . . . , an and b1 , . . . , bn where each number is 0 or 1, the fastest algorithm 2006
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,
A. Takes O(3n ) and Ω(2n ) time if hashing is permitted
B. Takes O(n3 ) and Ω(n2.5 ) time in the key comparison mode
C. Takes Θ(n) time and space
√
D. Takes O( n) time only if the sum of the 2n elements is an even number
1 1
Q 21. An algorithm performs (log N ) 2 find operations, N insert operations, (log N ) 2 delete operations, 2015Set1
1
and (log N ) 2 decrease-key operations on a set of data items with keys drawn from a linearly 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

Q 22. A meld operation on two instances of a data structure combines them into one single instance of the 2025Set2
same data structure. Consider the following data structures:
P: Unsorted doubly linked list with pointers to the head node and tail node of the list.
Q: Min-heap implemented using an array.
R: Binary Search Tree.
Which ONE of the following options gives the worst-case time complexities for meld operation on in-
stances of size n of these data structures?

A. P: Θ(1), Q: Θ(n), R: Θ(n) C. P: Θ(n), Q: Θ(n log n), R: Θ(n2 )

B. P: Θ(1), Q: Θ(n log n), R: Θ(n) D. P: Θ(1), Q: Θ(n), R: Θ(n log n)

6.2 More Questions

Q 23. You are given two strings S and T , each of length α, consisting only of lower case English letters ISI’15
(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 YES; but
if S = trainee, T = retinaa, your algorithm should return NO.

Q 24. Write a complete ANSI C code using recursion to calculate the sum(s) of the digits of an integer number ISI’17
(i) consisting of maximum 5 digits. For example, (1) = if i = 12345, then your program should print
s = 15, (2) = if i = 457, then s = 16.

Q 25. Write a C program to find all permutations of a string (having at most 6 characters). For example, a ISI’17
string of 3 characters like ‘abc’ has 6 possible permutations: ‘abc’, ‘acb’, ‘bac’, ’‘bca’, ‘cab’, ‘cba’.

Q 26. Let A = (a1 , a2 , . . . , an ) be an array of n distinct numbers. The array may not be sorted. The first ISI’17
element a1 is said to be a blip if a1 > a2 . Similarly, the last element an is said to be a blip if an > an−1 .
Among the remaining elements, an element ai is said to be blip if ai > ai−1 and ai > ai+1 where
i ∈ {2, 3, . . . , n − 1}. Design an O(log n) time algorithm for finding a blip in A. Justify the complexity
of your algorithm.

51
 Algorithms Graph Theory Page 52 of 54

Chapter 7 Graph Theory

Q 1. A non-planer graph with minimum number of vertices has 1992
A. 9 edges, 6 vertices B. 6 edges, 4 vertices C. 10 edges, 5 vertices D. 9 edges, 5 vertices
Q 2. Consider a simple connected graph G with n vertices and n edges (n > 2). Then which of the following 1993
statements are true?
A. G has no cycles
B. The graph obtained by removing any edges from G is not considered connected
C. G has at least one cycle
D. The graph obtained by removing any two edges from G is not considered connected
E. None of the above
Q 3. The number of distinct simple graphs with up to three nodes is 1994
A. 15 B. 10 C. 7 D. 9
Q 4. How many undirected graphs (not necessarily connected) can be constructed out of a given set V = 2001
{v1 , v2 , . . . vn } of n vertices?
n(n−1) n(n−1)
A. 2 B. 2n C. n! D. 2 2

Q 5. The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way 2002
that no two adjacent nodes have the same colour is:
D. n − 2 n2 + 2
 
A. 2 B. 3 C. 4

Q 6. The maximum number of edges in a n-node undirected graph without self loops is 2002
2
A. n B. n(n − 1)/2 C. n − 1 D. (n + 1)(n)/2

Q 7. The minimum number of colours required to colour the following graph, such that no two adjacent 2004
vertices are assigned the same colour, is

A. 2 B. 3 C. 4 D. 5
Q 8. 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 2005IT
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 );

52
 Algorithms Graph Theory Page 53 of 54

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 " );

(i) Choose the correct expressions for E1 and E2:

A. E1 : A[i][j] and E2 : i = j C. E1 : !A[i][j] and E2 : i = j

B. E1 : !A[i][j] and E2 : i = j + 1 D. E1 : A[i][j] and E2 : i = j + 1

(ii) Choose the correct expression for E3:

A. (A[i][j] && !A[j][i]) C. (!A[i][j] || A[j][i])

B. (!A[i][j] && A[j][i]) D. (A[i][j] || !A[j][i])

Q 9. If all the edge weights of an undirected graph are positive, then any subset of edges that connects all 2006IT
the vertices and has minimum total weight is a
A. Hamiltonian cycle B. Grid C. Hypercube D. Tree
P
Q 10. Let G = (V, E) be a graph. Define ξ(G) = id ∗ d, where id is the number of vertices of degree d in G. 2010
d
If S and T are two different trees with ξ(S) = ξ(T ), then
A. |S| = 2|T | B. |S| = |T | − 1 C. |S| = |T | D. |S| = |T | + 1

Q 11. The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in 2010
decreasing order. Which of the following sequences can not be the degree sequence of any graph?

I. 7, 6, 5, 4, 4, 3, 2, 1
II. 6, 6, 6, 6, 3, 3, 2, 2
III. 7, 6, 6, 4, 4, 3, 2, 2
IV. 8, 7, 7, 6, 4, 2, 1, 1
A. I and II B. III and IV C. IV only D. II and IV

Q 12. Consider an undirected graph G where self-loops are not allowed. The vertex set of G is {(i, j) | 1 ≤ 2014Set1
i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a, b) and (c, d) if |a − c| ≤ 1 and |b − d| ≤ 1. The number
of edges in this graph is .

Q 13. G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. 2017Set2
Then the maximum possible value of n is .

Q 14. Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum 2022
number of edges it can have is .

7.1 More Questions

Q 15. A vertex cover of a graph G = (V, E) is a set of vertices V ′ ⊆ V such that for any edge (u, v) ∈ E, ISI’11
either u or v (or both) is in V ′ . Write a linear time algorithm to find the minimum vertex cover of a
given tree T . Establish its correctness.

Q 16. Let G := (V, E) be a simple, connected, undirected, weighted graph with vertex set V , |V | ≥ 4, and ISI’22
edge set E, |E| ≥ 4. The edges have distinct positive weights on them. Prove that a minimum spanning
tree of G either contains the edge with the third smallest weight or the edge with the fourth smallest
weight.

53
 Algorithms Graph Theory Page 54 of 54

Q 17. Let G = (V, E) be an undirected simple graph. A subset M ⊆ E is a matching in G if distinct edges in TIFR’22
M do not share a vertex. A matching is maximal if no strict superset of M is a matching. How many
maximal matchings does the following graph have?

A. 1 B. 2 C. 3 D. 4 E. 5

Q 18. A graph is k-regular if all the vertices have degree exactly k. What is the minimum number of vertices CMI’23
in a k-regular graph that has no 3-length cycles?
A. k B. k + 1 C. 2k D. 2k + 1
Q 19. A d-regular graph is one in which every vertex has degree d. Also, a minimum cut in a graph is a smallest TIFR’25
set of edges which, upon removal, disconnects the graph, so that there are vertices in the resulting graph
with no path between them. We are given two graphs. G1 = (V1 , E1 ) is a connected, 3-regular graph.
G2 = (V2 , E2 ) is a connected, 4-regular graph. The vertex sets V1 and V2 are disjoint. We are further
told that the size of any minimum cut in G1 is the same as the size of any minimum cut in G2 . Which
of the following must be the size of this minimum cut?
A. 0 B. 1 C. 2 D. 3 E. 4
Q 20. In a finite directed graph, every vertex has exactly three incoming edges. Which of the following CMI’25
statements is guaranteed to be true?
A. Some vertex has at least three edges leaving it.
B. Exactly three edges leave every vertex.
C. Some vertex has exactly three edges leaving it.
D. None of the above is true.
Q 21. For an undirected graph G, let G refer to the complement (a graph on the same vertex set as G, with TIFR’24
(i, j) as an edge in G if and only if it is not an edge in G). Consider the following statements.
(I) G has a vertex-cover of size at most k.
(II) G has an independent set of size at least k.
(III) G has an independent set of size at least n − k.
(IV) G has a clique of size at least k.
(V) G has a clique of size at least n − k.
Which of the following is true for any graph G and its complement graph G?

A. (i) is equivalent to (iii) and (iv). D. (i) is equivalent to (ii) and (v)
B. (i) is equivalent to (iii) and (v). E. None of the ve statements are equivalent to
C. (i) is equivalent to (ii) and (iv). each other.

54