1 Algorithms (318)

Searching, Sorting, Hashing, Asymptotic worst case time and Space complexity, Algorithm design
techniques: Greedy, Dynamic programming, and Divide‐and‐conquer, Graph search, Minimum spanning
trees, Shortest paths.

1.1 Algorithm Design (8)

1.1.1 Algorithm Design: GATE CSE 1992 | Question: 8

Let be a Depth First Tree of a undirected graph . An array indexed by the vertices of is given.
is the parent of vertex , in . Parent of the root is the root itself.

Give a method for finding and printing the cycle formed if the edge of not in (i.e., ) is now
added to .

Time taken by your method must be proportional to the length of the cycle.

Describe the algorithm in a PASCAL – like language. Assume that the variables have been suitably declared.

gate1992 algorithms descriptive algorithm-design

Answer key☟

1.1.2 Algorithm Design: GATE CSE 1994 | Question: 7

An array contains integers in locations . It is required to shift the elements of

the array cyclically to the left by places, where . An incomplete algorithm for doing this in
linear time, without using another array is given below. Complete the algorithm by filling in the blanks. Assume all
variables are suitably declared.
min:=n;
i=0;
while _____ do
begin
temp:=A[i];
j:=i;
while ____ do
begin
A[j]:=____;
j:=(j+K) mod n;
if j<min then
min:=j;
end;
A[(n+i-K)mod n]:=____;
i:=______;
end;

gate1994 algorithms normal algorithm-design fill-in-the-blanks

Answer key☟

1.1.3 Algorithm Design: GATE CSE 2006 | Question: 17

An element in an array is called a leader if it is greater than all elements to the right of it in . The best
algorithm to find all leaders in an array

A. solves it in linear time using a left to right pass of the array

B. solves it in linear time using a right to left pass of the array
C. solves it using divide and conquer in time
D. solves it in time
 gatecse-2006 algorithms normal algorithm-design

Answer key☟

1.1.4 Algorithm Design: GATE CSE 2006 | Question: 54

Given two arrays of numbers and where each number is or , the fastest algorithm
to find the largest span such that or report that there is
not such span,

A. Takes and time if hashing is permitted

B. Takes and time in the key comparison mode
C. Takes time and space
D. Takes time only if the sum of the elements is an even number

gatecse-2006 algorithms normal algorithm-design time-complexity

Answer key☟

1.1.5 Algorithm Design: GATE CSE 2014 Set 1 | Question: 37

There are bags labeled to . All the coins in a given bag have the same weight. Some bags have coins
of weight gm, others have coins of weight gm. I pick coins respectively from bags to
Their total weight comes out to gm. Then the product of the labels of the bags having gm coins is ___.

gatecse-2014-set1 algorithms numerical-answers normal algorithm-design

Answer key☟

1.1.6 Algorithm Design: GATE CSE 2019 | Question: 25

Consider a sequence of elements: . The

sequence sum . Determine the maximum of , where . (Divide
and conquer approach may be used.)

Answer: ___________

gatecse-2019 numerical-answers algorithms algorithm-design 1-mark

Answer key☟

1.1.7 Algorithm Design: GATE CSE 2021 Set 1 | Question: 40

Define to be the maximum amount earned by cutting a rod of length meters into one or more pieces of
integer length and selling them. For , let denote the selling price of a rod whose length is meters.
Consider the array of prices:

Which of the following statements is/are correct about ?

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

gatecse-2021-set1 multiple-selects algorithms algorithm-design 2-marks

Answer key☟

1.1.8 Algorithm Design: GATE CSE 2024 | Set 2 | Question: 32

Consider an array that contains positive integers. A subarray of is defined to be a sequence of array
locations with consecutive indices.
 The code snippet given below has been written to compute the length of the longest subarray of that contains
at most two distinct integers. The code has two missing expressions labelled and .

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

A.
B.
C.
D.

gatecse2024-set2 algorithms algorithm-design

Answer key☟

1.2 Algorithm Design Technique (9)

1.2.1 Algorithm Design Technique: GATE CSE 1990 | Question: 12b

Consider the following problem. Given positive integers it is required to partition them in to

two parts and such that, is minimised

Consider a greedy algorithm for solving this problem. The numbers are ordered so that and at
step, is placed in that part whose sum in smaller at that step. Give an example with for which the
solution produced by the greedy algorithm is not optimal.

gate1990 descriptive algorithms algorithm-design-technique

Answer key☟

1.2.2 Algorithm Design Technique: GATE CSE 1990 | Question: 2-vii

Match the pairs in the following questions:

gate1990 match-the-following algorithms algorithm-design-technique easy

Answer key☟
1.2.3 Algorithm Design Technique: GATE CSE 1994 | Question: 1.19, ISRO2016-31

Algorithm design technique used in quicksort algorithm is?

A. Dynamic programming B. Backtracking

C. Divide and conquer D. Greedy method
gate1994 algorithms algorithm-design-technique quick-sort easy isro2016

Answer key☟

1.2.4 Algorithm Design Technique: GATE CSE 1995 | Question: 1.5

Merge sort uses:

A. Divide and conquer strategy B. Backtracking approach

C. Heuristic search D. Greedy approach
gate1995 algorithms sorting easy algorithm-design-technique merge-sort

Answer key☟

1.2.5 Algorithm Design Technique: GATE CSE 1997 | Question: 1.5

The correct matching for the following pairs is

A. B. C. D.

gate1997 algorithms normal algorithm-design-technique easy match-the-following

Answer key☟

1.2.6 Algorithm Design Technique: GATE CSE 1998 | Question: 1.21, ISRO2008-16

Which one of the following algorithm design techniques is used in finding all pairs of shortest distances in a
graph?

A. Dynamic programming B. Backtracking

C. Greedy D. Divide and Conquer
gate1998 algorithms algorithm-design-technique easy isro2008

Answer key☟

1.2.7 Algorithm Design Technique: GATE CSE 2015 Set 1 | Question: 6

Match the following:

A. B.
C. D.
gatecse-2015-set1 algorithms normal match-the-following algorithm-design-technique

Answer key☟

1.2.8 Algorithm Design Technique: GATE CSE 2015 Set 2 | Question: 36

Given below are some algorithms, and some algorithm design paradigms.
 Match the above algorithms on the left to the corresponding design paradigm they follow.

A. B.
C. D.
gatecse-2015-set2 algorithms easy algorithm-design-technique match-the-following

Answer key☟

1.2.9 Algorithm Design Technique: GATE CSE 2017 Set 1 | Question: 05

Consider the following table:

Match the algorithms to the design paradigms they are based on.

A.
B.
C.
D.

gatecse-2017-set1 algorithms algorithm-design-technique easy match-the-following

Answer key☟

1.3 Asymptotic Notation (21)

1.3.1 Asymptotic Notation: GATE CSE 1994 | Question: 1.23

Consider the following two functions:

Which of the following is true?

A. B.
C. D.
gate1994 algorithms asymptotic-notation normal multiple-selects

Answer key☟

1.3.2 Asymptotic Notation: GATE CSE 1996 | Question: 1.11

Which of the following is false?

A. B.
 C. If D.
gate1996 algorithms asymptotic-notation normal

Answer key☟

1.3.3 Asymptotic Notation: GATE CSE 1999 | Question: 2.21

If , give the correct matching for the following pairs:

A. B.
C. D.
gate1999 algorithms recurrence-relation asymptotic-notation normal match-the-following

Answer key☟

1.3.4 Asymptotic Notation: GATE CSE 2000 | Question: 2.17

Consider the following functions

Which of the following is true?

A. is B. is
C. is not D. is
gatecse-2000 algorithms asymptotic-notation normal

Answer key☟

1.3.5 Asymptotic Notation: GATE CSE 2001 | Question: 1.16

Let and be two positive functions of . Which of the following

statements is correct?

A. B.
C. D.
gatecse-2001 algorithms asymptotic-notation time-complexity normal

Answer key☟

1.3.6 Asymptotic Notation: GATE CSE 2003 | Question: 20

Consider the following three claims:

I. where and are constants

II.
III.

Which of the following claims are correct?

A. I and II B. I and III C. II and III D. I, II, and III

gatecse-2003 algorithms asymptotic-notation normal

Answer key☟
1.3.7 Asymptotic Notation: GATE CSE 2004 | Question: 29

The tightest lower bound on the number of comparisons, in the worst case, for comparison-based sorting is
of the order of

A. B. C. D.
gatecse-2004 algorithms sorting asymptotic-notation easy

Answer key☟

1.3.8 Asymptotic Notation: GATE CSE 2005 | Question: 37

Suppose ,
Which one of the following is FALSE?

A. B.
C. D.
gatecse-2005 algorithms asymptotic-notation recurrence-relation normal

Answer key☟

1.3.9 Asymptotic Notation: GATE CSE 2008 | Question: 39

Consider the following functions:

Which of the following statements about the asymptotic behavior of , and is true?

A.
B.
C.
D.

gatecse-2008 algorithms asymptotic-notation normal

Answer key☟

1.3.10 Asymptotic Notation: GATE CSE 2011 | Question: 37

Which of the given options provides the increasing order of asymptotic complexity of functions and
?

A. B.
C. D.
gatecse-2011 algorithms asymptotic-notation normal

Answer key☟

1.3.11 Asymptotic Notation: GATE CSE 2012 | Question: 18

Let and denote respectively, the worst case and average case running time of an algorithm
executed on an input of size . Which of the following is ALWAYS TRUE?

A. B.
C. D.
gatecse-2012 algorithms easy asymptotic-notation
 Answer key☟

1.3.12 Asymptotic Notation: GATE CSE 2015 Set 3 | Question: 4

Consider the equality and the following choices for :

I.
II.
III.
IV.

The equality above remains correct if is replaced by

A. Only I B. Only II
C. I or III or IV but not II D. II or III or IV but not I
gatecse-2015-set3 algorithms asymptotic-notation normal

Answer key☟

1.3.13 Asymptotic Notation: GATE CSE 2015 Set 3 | Question: 42

Let and , where is a positive integer. Which of the following statements is/are
correct?

I.
II.

A. Only I B. Only II C. Both I and II D. Neither I nor II

gatecse-2015-set3 algorithms asymptotic-notation normal

Answer key☟

1.3.14 Asymptotic Notation: GATE CSE 2017 Set 1 | Question: 04

Consider the following functions from positive integers to real numbers:

, , , , .
The CORRECT arrangement of the above functions in increasing order of asymptotic complexity is:

A. , , , , B. , , , ,
C. , , , , D. , , , ,
gatecse-2017-set1 algorithms asymptotic-notation normal

Answer key☟

1.3.15 Asymptotic Notation: GATE CSE 2021 Set 1 | Question: 3

Consider the following three functions.

Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

A. B.
C. D.
gatecse-2021-set1 algorithms asymptotic-notation 1-mark

Answer key☟

1.3.16 Asymptotic Notation: GATE CSE 2022 | Question: 1

Which one of the following statements is for all positive functions

A. when is a polynomial
 B.
C. when is an exponential function
D.

gatecse-2022 algorithms asymptotic-notation 1-mark

Answer key☟

1.3.17 Asymptotic Notation: GATE CSE 2023 | Question: 19

Let and be functions of natural numbers given by and Which of the following
statements is/are

A. B.
C. D.
gatecse-2023 algorithms asymptotic-notation multiple-selects 1-mark

Answer key☟

1.3.18 Asymptotic Notation: GATE CSE 2023 | Question: 44

Consider functions and expressed in pseudocode as follows:

Function_1 | Function_2
while n > 1 do | for i = 1 to 100 * n do
for i = 1 to n do | x = x + 1;
x = x + 1; | end for
end for |
n = ⌊n/2⌋; |
end while |

Let and denote the number of times the statement is executed in and
respectively.
Which of the following statements is/are

A. B.
C. D.
gatecse-2023 algorithms asymptotic-notation multiple-selects 2-marks

Answer key☟

1.3.19 Asymptotic Notation: GATE CSE 2024 | Set 2 | Question: 5

​Let be the recurrence relation defined as follows:

Which one of the following statements is TRUE?

A. B.
C. D.
gatecse2024-set2 algorithms recurrence-relation asymptotic-notation

Answer key☟

1.3.20 Asymptotic Notation: GATE IT 2004 | Question: 55

Let , and be functions defined for positive integers such that

, , , and .
Which one of the following statements is FALSE?

A. B.
 C. D.
gateit-2004 algorithms asymptotic-notation normal

Answer key☟

1.3.21 Asymptotic Notation: GATE IT 2008 | Question: 10

Arrange the following functions in increasing asymptotic order:

a.
b.
c.
d.
e.

A. a, d, c, e, b B. d, a, c, e, b C. a, c, d, e, b D. a, c, d, b, e
gateit-2008 algorithms asymptotic-notation normal

Answer key☟

1.4 Bellman Ford (2)

1.4.1 Bellman Ford: GATE CSE 2009 | Question: 13

Which of the following statement(s) is/are correct regarding Bellman-Ford shortest path algorithm?
P: Always finds a negative weighted cycle, if one exists.
Q: Finds whether any negative weighted cycle is reachable from the source.

A. only B. only C. Both and D. Neither nor

gatecse-2009 algorithms graph-algorithms normal bellman-ford

Answer key☟

1.4.2 Bellman Ford: GATE CSE 2013 | Question: 19

What is the time complexity of Bellman-Ford single-source shortest path algorithm on a complete graph of n
vertices?

A. B.
C. D.
gatecse-2013 algorithms graph-algorithms normal bellman-ford

Answer key☟

1.5 Binary Search (2)

1.5.1 Binary Search: GATE CSE 2021 Set 2 | Question: 8

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted
array of size ?

A. B.
C. D.
gatecse-2021-set2 algorithms binary-search time-complexity 1-mark

Answer key☟

1.5.2 Binary Search: GATE DS&AI 2024 | Question: 30

Let denote the maximum number of comparisons made while searching for an entry in a sorted array
of size using binary search.

Which ONE of the following options is TRUE?

A. B.
 C. D.
gate-ds-ai-2024 algorithms binary-search

Answer key☟

1.6 Dijkstras Algorithm (6)

1.6.1 Dijkstras Algorithm: GATE CSE 1996 | Question: 17

Let be the directed, weighted graph shown in below figure

We are interested in the shortest paths from .

a. Output the sequence of vertices identified by the Dijkstra’s algorithm for single source shortest path when the
algorithm is started at node
b. Write down sequence of vertices in the shortest path from to
c. What is the cost of the shortest path from to ?

gate1996 algorithms graph-algorithms normal dijkstras-algorithm descriptive

Answer key☟

1.6.2 Dijkstras Algorithm: GATE CSE 2004 | Question: 44

Suppose we run Dijkstra’s single source shortest path algorithm on the following edge-weighted directed
graph with vertex 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. B. C. D.
gatecse-2004 algorithms graph-algorithms normal dijkstras-algorithm

Answer key☟

1.6.3 Dijkstras Algorithm: GATE CSE 2005 | Question: 38

Let be an undirected graph with positive edge weights. Dijkstra’s single source shortest path
algorithm can be implemented using the binary heap data structure with time complexity:

A. B.
C. D.
gatecse-2005 algorithms graph-algorithms normal dijkstras-algorithm

Answer key☟
 1.6.4 Dijkstras Algorithm: GATE CSE 2006 | Question: 12

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

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

gatecse-2006 algorithms graph-algorithms easy dijkstras-algorithm

Answer key☟

1.6.5 Dijkstras Algorithm: GATE CSE 2008 | Question: 45

Dijkstra's single source shortest path algorithm when run from vertex in the above graph, computes the correct
shortest path distance to

A. only vertex B. only vertices

C. only vertices D. all the vertices
gatecse-2008 algorithms graph-algorithms normal dijkstras-algorithm

Answer key☟

1.6.6 Dijkstras Algorithm: GATE CSE 2012 | Question: 40

Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices
and . Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the
shortest path to a vertex is updated only when a strictly shorter path to is discovered.

A. B. C. D.
gatecse-2012 algorithms graph-algorithms normal dijkstras-algorithm

Answer key☟

1.7 Dynamic Programming (9)

1.7.1 Dynamic Programming: GATE CSE 2008 | Question: 80

The subset-sum
problem is defined as follows. Given a set of positive integers,
, and positive integer , is there a subset of whose elements sum to ? A
dynamic program for solving this problem uses a Boolean array, , with rows and
columns. , is TRUE, if and only if there is a subset of whose
elements sum to .
Which of the following is valid for , and ?

A.
B.
C.
D.

gatecse-2008 algorithms normal dynamic-programming

Answer key☟

1.7.2 Dynamic Programming: GATE CSE 2008 | Question: 81

The subset-sum
problem is defined as follows. Given a set of positive integers,
, and positive integer , is there a subset of whose elements sum to ? A
dynamic program for solving this problem uses a Boolean array, , with rows and
columns. , is TRUE, if and only if there is a subset of whose
elements sum to .
Which entry of the array , if TRUE, implies that there is a subset whose elements sum to ?

A. B. C. D.
gatecse-2008 algorithms normal dynamic-programming

Answer key☟

1.7.3 Dynamic Programming: GATE CSE 2009 | Question: 53

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all)
left out. We are given two sequences and of lengths and , respectively with indexes of
and starting from .
We wish to find the length of the longest common sub-sequence (LCS) of and as , where an
incomplete recursive definition for the function to compute the length of the LCS of and 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. B.
C. D.
gatecse-2009 algorithms normal dynamic-programming recursion

Answer key☟

1.7.4 Dynamic Programming: GATE CSE 2009 | Question: 54

A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all)
left out. We are given two sequences and of lengths and , respectively with indexes of
and starting from .
We wish to find the length of the longest common sub-sequence (LCS) of and as , where an
incomplete recursive definition for the function to compute the length of the LCS of and is given
below:
, if either or
if and
if and
The value of could be obtained by dynamic programming based on the correct recursive definition of
of the form given above, using an array , where and , such that .
Which one of the following statements would be TRUE regarding the dynamic programming solution for the
recursive definition of ?

A. All elements of should be initialized to 0 for the values of to be properly computed.

B. The values of may be computed in a row major order or column major order of .
C. The values of cannot be computed in either row major order or column major order of .
D. needs to be computed before if either or .
 gatecse-2009 normal algorithms dynamic-programming recursion

Answer key☟

1.7.5 Dynamic Programming: GATE CSE 2010 | Question: 34

The weight of a sequence of real numbers is defined as .

A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order
of the remaining elements the same. Let denote the maximum possible weight of a subsequence of
and the maximum possible weight of a subsequence of . Then is equal to

A. B.
C. D.
gatecse-2010 algorithms dynamic-programming normal

Answer key☟

1.7.6 Dynamic Programming: GATE CSE 2011 | Question: 25

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array
is given below.
Let , denote the length of the longest monotonically increasing sequence starting at index in the array.
Initialize .
For all such that

Finally, the length of the longest monotonically increasing sequence is

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

gatecse-2011 algorithms easy dynamic-programming

Answer key☟

1.7.7 Dynamic Programming: GATE CSE 2014 Set 2 | Question: 37

Consider two strings ="qpqrr" and ="pqprqrp". Let be the length of the longest common
subsequence (not necessarily contiguous) between and and let be the number of such longest
common subsequences between and . Then ___.

gatecse-2014-set2 algorithms normal numerical-answers dynamic-programming

Answer key☟

1.7.8 Dynamic Programming: GATE CSE 2014 Set 3 | Question: 37

Suppose you want to move from to on the number line. In each step, you either move right by a unit
distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers . Given a
shortcut , if you are at position on the number line, you may directly move to . Suppose denotes the
smallest number of steps needed to move from to . Suppose further that there is at most shortcut involving
any number, and in particular, from there is a shortcut to . Let and be such that
. Then the value of the product is _____.

gatecse-2014-set3 algorithms normal numerical-answers dynamic-programming

Answer key☟
 1.7.9 Dynamic Programming: GATE CSE 2016 Set 2 | Question: 14

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

A. Greedy paradigm.
B. Divide-and-conquer paradigm.
C. Dynamic Programming paradigm.
D. Neither Greedy nor Divide-and-Conquer nor Dynamic Programming paradigm.

gatecse-2016-set2 algorithms dynamic-programming easy

Answer key☟

1.8 Graph Algorithms (11)

1.8.1 Graph Algorithms: GATE CSE 1994 | Question: 1.22

Which of the following statements is false?

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 can be used to find connected components of a graph

gate1994 algorithms normal graph-algorithms

Answer key☟

1.8.2 Graph Algorithms: GATE CSE 2003 | Question: 70

Let be a directed graph with vertices. A path from to in is a sequence of vertices (

) such that for all in through . A simple path is a path in which no
vertex appears more than once.
Let be an array initialized as follows:

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 and after termination of the above algorithm?

A.
B. If then has a Hamiltonian cycle
C. If there exists a path from to , contains the longest path length from to
D. If there exists a path from to , every simple path from to contains at most edges

gatecse-2003 algorithms graph-algorithms normal

Answer key☟

1.8.3 Graph Algorithms: GATE CSE 2005 | Question: 82a

Let and be two vertices in a undirected graph having distinct positive edge weights. Let
be a partition of such that and . Consider the edge having the minimum weight
amongst all those edges that have one vertex in and one vertex in .
The edge must definitely belong to:
 A. the minimum weighted spanning tree of B. the weighted shortest path from to
C. each path from to D. the weighted longest path from to
gatecse-2005 algorithms graph-algorithms normal

Answer key☟

1.8.4 Graph Algorithms: GATE CSE 2005 | Question: 82b

Let and be two vertices in a undirected graph having distinct positive edge weights. Let
be a partition of such that and . Consider the edge having the minimum weight
amongst all those edges that have one vertex in and one vertex in .
Let the weight of an edge denote the congestion on that edge. The congestion on a path is defined to be the
maximum of the congestions on the edges of the path. We wish to find the path from to having minimum
congestion. Which of the following paths is always such a path of minimum congestion?

A. a path from to in the minimum weighted spanning treeB. a weighted shortest path from to
C. an Euler walk from to D. a Hamiltonian path from to
gatecse-2005 algorithms graph-algorithms normal

Answer key☟

1.8.5 Graph Algorithms: GATE CSE 2016 Set 2 | Question: 41

In an adjacency list representation of an undirected simple graph , each edge has two
adjacency list entries: in the adjacency list of , and in the adjacency list of . These are called twins
of each other. A twin pointer is a pointer from an adjacency list entry to its twin. If and , 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. B.
C. D.
gatecse-2016-set2 algorithms graph-algorithms normal

Answer key☟

1.8.6 Graph Algorithms: GATE CSE 2017 Set 1 | Question: 26

Let be connected, undirected, edge-weighted graph. The weights of the edges in are
positive and distinct. Consider the following statements:

I. Minimum Spanning Tree of is always unique.

II. Shortest path between any two vertices of 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

gatecse-2017-set1 algorithms graph-algorithms normal

Answer key☟

1.8.7 Graph Algorithms: GATE CSE 2021 Set 2 | Question: 46

Consider the following directed graph:

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 classifies three directed edges as back edges
C. The graph does not have a strongly connected component
D. For each pair of vertices and , there is a directed path from to

gatecse-2021-set2 multiple-selects algorithms graph-algorithms 2-marks

Answer key☟

1.8.8 Graph Algorithms: GATE CSE 2021 Set 2 | Question: 55

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

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

gatecse-2021-set2 algorithms graph-algorithms directed-acyclic-graph numerical-answers 2-marks

Answer key☟

1.8.9 Graph Algorithms: GATE IT 2005 | Question: 15

In the following table, the left column contains the names of standard graph algorithms and the right column
contains the time complexities of the algorithms. Match each algorithm with its time complexity.

A. B.
C. D.
gateit-2005 algorithms graph-algorithms match-the-following easy

Answer key☟

1.8.10 Graph Algorithms: GATE IT 2005 | Question: 84a

A sink in a directed graph is a vertex i such that there is an edge from every vertex to and there is no
edge from to any other vertex. A directed graph with vertices is represented by its adjacency matrix ,
where if there is an edge directed from vertex to and otherwise. The following algorithm
determines whether there is a sink in the graph .
i = 0;
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists");
else printf ("Sink does not exist");

Choose the correct expressions for and

 A. and ; B. and ;
C. and ; D. and ;
gateit-2005 algorithms graph-algorithms normal

Answer key☟

1.8.11 Graph Algorithms: GATE IT 2005 | Question: 84b

A sink in a directed graph is a vertex i such that there is an edge from every vertex to and there is no
edge from to any other vertex. A directed graph with vertices is represented by its adjacency matrix ,
where if there is an edge directed from vertex to and otherwise. The following algorithm
determines whether there is a sink in the graph .
i = 0;
do {
j = i + 1;
while ((j < n) && E1) j++;
if (j < n) E2;
} while (j < n);
flag = 1;
for (j = 0; j < n; j++)
if ((j! = i) && E3) flag = 0;
if (flag) printf("Sink exists") ;
else printf ("Sink does not exist");

Choose the correct expression for

A. B.
C. D.
gateit-2005 algorithms graph-algorithms normal

Answer key☟

1.9 Graph Search (22)

1.9.1 Graph Search: GATE CSE 1989 | Question: 4-vii

In the graph shown above, the depth-first spanning tree edges are marked with a . Identify the forward,
backward, and cross edges.

gate1989 descriptive algorithms graph-algorithms depth-first-search graph-search

Answer key☟

1.9.2 Graph Search: GATE CSE 2000 | Question: 1.13

The most appropriate matching for the following pairs

is:

A. B.
C. D.
gatecse-2000 algorithms easy graph-algorithms graph-search match-the-following

Answer key☟

1.9.3 Graph Search: GATE CSE 2000 | Question: 2.19

Let be an undirected graph. Consider a depth-first traversal of , and let be the resulting depth-first
search tree. Let be a vertex in and let be the first new (unvisited) vertex visited after visiting in the
traversal. Which of the following statement is always true?

A. must be an edge in , and is a descendant of in

B. must be an edge in , and is a descendant of in
C. If is not an edge in then is a leaf in
D. If is not an edge in then and must have the same parent in

gatecse-2000 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.4 Graph Search: GATE CSE 2001 | Question: 2.14

Consider an undirected, unweighted graph . Let a breadth-first traversal of be done starting from a node
. Let and be the lengths of the shortest paths from to and respectively in . If is
visited before during the breadth-first traversal, which of the following statements is correct?

A. B.
C. D. None of the above
gatecse-2001 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.5 Graph Search: GATE CSE 2003 | Question: 21

Consider the following graph:

Among the following sequences:

I. abeghf
II. abfehg
III. abfhge
IV. afghbe

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

A. I, II and IV only B. I and IV only C. II, III and IV only D. I, III and IV only
gatecse-2003 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.6 Graph Search: GATE CSE 2006 | Question: 48

Let be a depth first search tree in an undirected graph . Vertices and are leaves of this tree . The
degrees of both and in are at least . which one of the following statements is true?
 A. There must exist a vertex adjacent to both and in
B. There must exist a vertex whose removal disconnects and in
C. There must exist a cycle in containing and
D. There must exist a cycle in containing and all its neighbours in

gatecse-2006 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.7 Graph Search: GATE CSE 2008 | Question: 19

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

A. B. C. D.
gatecse-2008 normal algorithms graph-algorithms graph-search

Answer key☟

1.9.8 Graph Search: GATE CSE 2014 Set 1 | Question: 11

Let be a graph with vertices and edges. What is the tightest upper bound on the running time of
Depth First Search on , when is represented as an adjacency matrix?

A. B. C. D.
gatecse-2014-set1 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.9 Graph Search: GATE CSE 2014 Set 2 | Question: 14

Consider the tree arcs of a BFS traversal from a source node in an unweighted, connected, undirected
graph. The tree 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 to every vertex in the graph.
C. the shortest paths from to only those nodes that are leaves of .
D. the longest path in the graph.

gatecse-2014-set2 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.10 Graph Search: GATE CSE 2014 Set 3 | Question: 13

Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a
recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier.
Then the maximum possible recursion depth (including the initial call) is _________.

gatecse-2014-set3 algorithms graph-algorithms numerical-answers normal graph-search

Answer key☟
1.9.11 Graph Search: GATE CSE 2015 Set 1 | Question: 45

Let be a simple undirected graph, and be a particular vertex in it called the source. For
, let denote the shortest distance in from to . A breadth first search (BFS) is performed
starting at . Let be the resultant BFS tree. If is an edge of that is not in , then which one of the
following CANNOT be the value of ?

A. B. C. D.
gatecse-2015-set1 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.12 Graph Search: GATE CSE 2016 Set 2 | Question: 11

Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex at a
distance four from the root. If is the vertex in this BFS traversal, then the maximum possible value of
is __________

gatecse-2016-set2 algorithms graph-algorithms normal numerical-answers graph-search

Answer key☟

1.9.13 Graph Search: GATE CSE 2017 Set 2 | Question: 15

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

A. B. C. D.
gatecse-2017-set2 algorithms graph-algorithms graph-search

Answer key☟

1.9.14 Graph Search: GATE CSE 2018 | Question: 30

Let be a simple undirected graph. Let be a depth first search tree of . Let be a breadth first
search tree of . Consider the following statements.

I. No edge of is a cross edge with respect to . (A cross edge in is between two nodes neither of which is
an ancestor of the other in ).
II. For every edge of , if is at depth and is at depth in , then .

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

gatecse-2018 algorithms graph-algorithms graph-search normal 2-marks

Answer key☟

1.9.15 Graph Search: GATE CSE 2023 | Question: 46

Let . Let denote the powerset of . Consider an undirected graph whose vertex set is
. For any is an edge in if and only if (i) , and (ii) either or .
For any vertex in , the set of all possible orderings in which the vertices of can be visited in a Breadth First
Search starting from is denoted by .

If denotes the empty set, then the cardinality of is ______________.

gatecse-2023 algorithms breadth-first-search numerical-answers 2-marks graph-search

Answer key☟
1.9.16 Graph Search: GATE CSE 2024 | Set 1 | Question: 35

Let be a directed graph and a depth first search spanning tree in that is rooted at a vertex .
Suppose is also a breadth first search tree in , rooted at . Which of the following statements
is/are TRUE for every such graph and tree ?

A. There are no back-edges in with respect to the tree

B. There are no cross-edges in with respect to the tree
C. There are no forward-edge in with respect to the tree
D. The only edges in are the edges in

gatecse2024-set1 algorithms multiple-selects graph-search

Answer key☟

1.9.17 Graph Search: GATE CSE 2024 | Set 1 | Question: 50

The number of edges present in the forest generated by the traversal of an undirected graph with
vertices is . The number of connected components in is __________.

gatecse2024-set1 numerical-answers graph-search graph-algorithms

Answer key☟

1.9.18 Graph Search: GATE DS&AI 2024 | Question: 4

Consider performing depth-first search (DFS) on an undirected and unweighted graph starting at vertex .
For any vertex in is the length of the shortest path from to . Let be an edge in such
that . If the edge is explored first in the direction from to during the above DFS, then
becomes a edge.

A. tree B. cross C. back D. gray

gate-ds-ai-2024 graph-search depth-first-search algorithms

Answer key☟

1.9.19 Graph Search: GATE IT 2005 | Question: 14

In a depth-first traversal of a graph with vertices, edges are marked as tree edges. The number of
connected components in is

A. B. C. D.
gateit-2005 algorithms graph-algorithms normal graph-search

Answer key☟

1.9.20 Graph Search: GATE IT 2006 | Question: 47

Consider the depth-first-search of an undirected graph with vertices , , and . Let discovery time
represent the time instant when the vertex is first visited, and finish time represent the time instant
when the vertex is last visited. Given that

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 and are connected
C. There are two connected components, and and are connected
D. There are two connected components, and and are connected
 gateit-2006 algorithms graph-algorithms normal graph-search depth-first-search

Answer key☟

1.9.21 Graph Search: GATE IT 2007 | Question: 24

A depth-first search is performed on a directed acyclic graph. Let denote the time at which vertex is
visited for the first time and the time at which the DFS call to the vertex terminates. Which of the
following statements is always TRUE for all edges in the graph ?

A. B.
C. D.
gateit-2007 algorithms graph-algorithms normal graph-search depth-first-search

Answer key☟

1.9.22 Graph Search: GATE IT 2008 | Question: 47

Consider the following sequence of nodes for the undirected graph given below:

1.
2.
3.
4.

A Depth First Search (DFS) is started at node . The nodes are listed in the order they are first visited. Which of the
above is/are possible output(s)?

A. and only B. and only C. and only D. and only

gateit-2008 algorithms graph-algorithms normal graph-search depth-first-search

Answer key☟

1.10 Greedy Algorithm (5)

1.10.1 Greedy Algorithm: GATE CSE 1999 | Question: 2.20

The minimum number of record movements required to merge five files A (with records), B (with
records), C (with records), D (with records) and E (with records) is:

A. B. C. D.
gate1999 algorithms normal greedy-algorithm

Answer key☟

1.10.2 Greedy Algorithm: GATE CSE 2003 | Question: 69

The following are the starting and ending times of activities and respectively in
chronological order: . Here, denotes the starting time and
denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An
activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the
minimum number of rooms required?

A. B. C. D.
 gatecse-2003 algorithms normal greedy-algorithm

Answer key☟

1.10.3 Greedy Algorithm: GATE CSE 2005 | Question: 84a

We are given tasks . The execution of each task requires one unit of time. We can execute
one task at a time. Each task has a profit and a deadline . Profit is earned if the task is completed
before the end of the unit of time.

Are all tasks completed in the schedule that gives maximum profit?

A. All tasks are completed B. and are left out

C. and are left out D. and are left out
gatecse-2005 algorithms greedy-algorithm process-scheduling normal

Answer key☟

1.10.4 Greedy Algorithm: GATE CSE 2005 | Question: 84b

We are given tasks . The execution of each task requires one unit of time. We can execute
one task at a time. Each task has a profit and a deadline . Profit is earned if the task is completed
before the end of the unit of time.

What is the maximum profit earned?

A. B. C. D.
gatecse-2005 algorithms greedy-algorithm process-scheduling normal

Answer key☟

1.10.5 Greedy Algorithm: GATE CSE 2018 | Question: 48

Consider the weights and values of items listed below. Note that there is only one unit of each item.

The task is to pick a subset of these items such that their total weight is no more than 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
. 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 .

The value of is ____

gatecse-2018 algorithms greedy-algorithm numerical-answers 2-marks

 Answer key☟

1.11 Hashing (7)

1.11.1 Hashing: GATE CSE 1989 | Question: 1-vii, ISRO2015-14

A hash table with ten buckets with one slot per bucket is shown in the following figure. The symbols to
initially entered using a hashing function with linear probing. The maximum number of comparisons
needed in searching an item that is not present is

A. B. C. D.
hashing isro2015 gate1989 algorithms normal

Answer key☟

1.11.2 Hashing: GATE CSE 1990 | Question: 13b

Consider a hash table with chaining scheme for overflow handling:

i. What is the worst-case timing complexity of inserting elements into such a table?
ii. For what type of instance does this hashing scheme take the worst-case time for insertion?

gate1990 hashing algorithms descriptive

Answer key☟

1.11.3 Hashing: GATE CSE 2020 | Question: 23

Consider a double hashing scheme in which the primary hash function is , and the
secondary hash function is . Assume that the table size is . Then the address
returned by probe in the probe sequence (assume that the probe sequence begins at probe ) for key value
is_____________.

gatecse-2020 numerical-answers algorithms hashing 1-mark

Answer key☟

1.11.4 Hashing: GATE CSE 2021 Set 1 | Question: 47

Consider a hashing approach for -bit integer keys:

1. There is a main hash table of size .

2. The least significant bits of a key is used to index into the main hash table.
3. Initially, the main hash table entries are empty.
4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main
hash table entry is organized as a binary tree that grows on demand.
5. First, the least significant bit is used to divide the keys into left and right subtrees.
6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based
on the least significant bit.
7. A split is done only if it is needed, i.e., only when there is a collision.

Consider the following state of the hash table.

 Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys
are in decimal notation)?

A. B.
C. D.
gatecse-2021-set1 multiple-selects algorithms hashing 2-marks

Answer key☟

1.11.5 Hashing: GATE CSE 2022 | Question: 6

Suppose we are given keys, hash table slots, and two simple uniform hash functions and
Further suppose our hashing scheme uses for the odd keys and for the even keys. What is the
expected number of keys in a slot?

A. B. C. D.
gatecse-2022 algorithms hashing uniform-hashing 1-mark

Answer key☟

1.11.6 Hashing: GATE CSE 2023 | Question: 10

An algorithm has to store several keys generated by an adversary in a hash table. The adversary is
malicious who tries to maximize the number of collisions. Let be the number of keys, be the number of
slots in the hash table, and .
Which one of the following is the best hashing strategy to counteract the adversary?

A. Division method, i.e., use the hash function .

B. Multiplication method, i.e., use the hash function , where is a carefully chosen
constant.
C. Universal hashing method.
D. If is a prime number, use Division method. Otherwise, use Multiplication method.

gatecse-2023 algorithms hashing 1-mark

Answer key☟

1.11.7 Hashing: GATE IT 2005 | Question: 16

A hash table contains buckets and uses linear probing to resolve collisions. The key values are integers
and the hash function used is . If the values are inserted in the table, in what
location would the key value be inserted?

A. B. C. D.
gateit-2005 algorithms hashing easy

Answer key☟

1.12 Huffman Code (6)

1.12.1 Huffman Code: GATE CSE 1989 | Question: 13a

A language uses an alphabet of six letters, . The relative frequency of use of each letter of
the alphabet in the language is as given below:
Design a prefix binary code for the language which would minimize the average length of the encoded words of the
language.

descriptive gate1989 algorithms huffman-code

Answer key☟

1.12.2 Huffman Code: GATE CSE 2007 | Question: 76

Suppose the letters have probabilities , respectively.

Which of the following is the Huffman code for the letter ?

A. , , , , , B. , , , , ,
C. , , , , , D. , , , , ,
gatecse-2007 algorithms greedy-algorithm normal huffman-code

Answer key☟

1.12.3 Huffman Code: GATE CSE 2007 | Question: 77

Suppose the letters have probabilities , respectively.

What is the average length of the Huffman code for the letters ?

A. B. C. D.
gatecse-2007 algorithms greedy-algorithm normal huffman-code

Answer key☟

1.12.4 Huffman Code: GATE CSE 2017 Set 2 | Question: 50

A message is made up entirely of characters from the set . The table of probabilities
for each of the characters is shown below:

If a message of characters over is encoded using Huffman coding, then the expected length of the encoded
message in bits is ______.

gatecse-2017-set2 huffman-code numerical-answers algorithms

Answer key☟
 1.12.5 Huffman Code: GATE CSE 2021 Set 2 | Question: 26

Consider the string . Each letter in the string must be assigned a binary code satisfying the
following properties:

1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a
code whose length is at most the length of the code assigned to the other letter.

Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length
of the encoded string?

A. B. C. D.
gatecse-2021-set2 algorithms huffman-code 2-marks

Answer key☟

1.12.6 Huffman Code: GATE IT 2006 | Question: 48

The characters to have the set of frequencies based on the first Fibonacci numbers as follows
, , , , , , ,
A Huffman code is used to represent the characters. What is the sequence of characters corresponding to the
following code?

A. B. C. D.
gateit-2006 algorithms greedy-algorithm normal huffman-code

Answer key☟

1.13 Identify Function (38)

1.13.1 Identify Function: GATE CSE 1989 | Question: 8a

What is the output produced by the following program, when the input is "HTGATE"
Function what (s:string): string;
var n:integer;
begin
n = s.length
if n <= 1
then what := s
else what :=contact (what (substring (s, 2, n)), s.C [1])
end;

Note

i. type string=record
length:integer;
C:array[1..100] of char
end
ii. Substring (s, i, j): this yields the string made up of the through characters in s; for appropriately defined in
and .
iii. Contact : this function yields a string of length length + - length obtained by concatenating with
such that precedes .

gate1989 descriptive algorithms identify-function

Answer key☟

1.13.2 Identify Function: GATE CSE 1990 | Question: 11b

The following program computes values of a mathematical function . Determine the form of .
main ()
{
 int m, n; float x, y, t;
scanf ("%f%d", &x, &n);
t = 1; y = 0; m = 1;
do
{
t *= (-x/m);
y += t;
} while (m++ < n);
printf ("The value of y is %f", y);
}

gate1990 descriptive algorithms identify-function

Answer key☟

1.13.3 Identify Function: GATE CSE 1991 | Question: 03-viii

Consider the following Pascal function:

Function X(M:integer):integer;
Var i:integer;
Begin
i := 0;
while i*i < M
do i:= i+1
X := i
end

The function call , if is positive, will return

A. B.
C. D.
E. None of the above
gate1991 algorithms easy identify-function multiple-selects

Answer key☟

1.13.4 Identify Function: GATE CSE 1993 | Question: 7.4

What does the following code do?

var a, b: integer;
begin
a:=a+b;
b:=a-b;
a:=a-b;
end;

A. exchanges and B. doubles and stores in

C. doubles and stores in D. leaves and unchanged
E. none of the above

gate1993 algorithms identify-function easy

Answer key☟

1.13.5 Identify Function: GATE CSE 1994 | Question: 6

What function of , is computed by this program?

Function what(x, n:integer): integer:
Var
value : integer
begin
value := 1
if n > 0 then
begin
if n mod 2 =1 then
value := value * x;
value := value * what(x*x, n div 2);
end;
what := value;
end;
 gate1994 algorithms identify-function normal descriptive

Answer key☟

1.13.6 Identify Function: GATE CSE 1995 | Question: 1.4

In the following Pascal program segment, what is the value of X after the execution of the program segment?
X := -10; Y := 20;
If X > Y then if X < 0 then X := abs(X) else X := 2*X;

A. B. C. D. None
gate1995 algorithms identify-function easy

Answer key☟

1.13.7 Identify Function: GATE CSE 1995 | Question: 2.3

Assume that and are non-zero positive integers. What does the following Pascal program segment do?
while X <> Y do
if X > Y then
X := X - Y
else
Y := Y - X;
write(X);

A. Computes the LCM of two numbers B. Divides the larger number by the smaller number
C. Computes the GCD of two numbers D. None of the above
gate1995 algorithms identify-function normal

Answer key☟

1.13.8 Identify Function: GATE CSE 1995 | Question: 4

A. Consider the following Pascal function where and are non-zero positive integers. What is the value of
?
function GET(A,B:integer): integer;
begin
if B=0 then
GET:= 1
else if A < B then
GET:= 0
else
GET:= GET(A-1, B) + GET(A-1, B-1)
end;

B. The Pascal procedure given for computing the transpose of an matrix of integers has an
error. Find the error and correct it. Assume that the following declaration are made in the main program
const
MAXSIZE=20;
type
INTARR=array [1..MAXSIZE,1..MAXSIZE] of integer;
Procedure TRANSPOSE (var A: INTARR; N : integer);
var
I, J, TMP: integer;
begin
for I:=1 to N – 1 do
for J:=1 to N do
begin
TMP:= A[I, J];
A[I, J]:= A[J, I];
A[J, I]:= TMP
end
end;

gate1995 algorithms identify-function normal descriptive

Answer key☟
1.13.9 Identify Function: GATE CSE 1998 | Question: 2.12

What value would the following function return for the input ?
Function fun (x:integer):integer;
Begin
If x > 100 then fun = x – 10
Else fun = fun(fun (x+11))
End;

A. B. C. D.
gate1998 algorithms recursion identify-function normal

Answer key☟

1.13.10 Identify Function: GATE CSE 1999 | Question: 2.24

Consider the following function definition

int Trial (int a, int b, int c)
{
if ((a>=b) && (c<b)) return b;
else if (a>=b) return Trial(a, c, b);
else return Trial(b, a, c);
}

The functional Trial:

A. Finds the maximum of , , and B. Finds the minimum of , , and

C. Finds the middle number of , , D. None of the above
gate1999 algorithms identify-function normal

Answer key☟

1.13.11 Identify Function: GATE CSE 2000 | Question: 2.15

Suppose you are given an array and a procedure reverse which reverses the order of
elements in between positions and (both inclusive). What does the following sequence do, where
:
reverse (s, 1, k);
reverse (s, k+1, n);
reverse (s, 1, n);

A. Rotates left by positions B. Leaves unchanged

C. Reverses all elements of D. None of the above
gatecse-2000 algorithms normal identify-function

Answer key☟

1.13.12 Identify Function: GATE CSE 2003 | Question: 1

Consider the following function.

For large values of , the return value of the function best approximates
float f,(float x, int y) {
float p, s; int i;
for (s=1,p=1,i=1; i<y; i++) {
p *= x/i;
s += p;
}
return s;
}

A. B. C. D.
gatecse-2003 algorithms identify-function normal

Answer key☟
1.13.13 Identify Function: GATE CSE 2003 | Question: 88

In the following program fragment, , , and TwoLog_n are integer variables, and is an array of
integers. The variable is initialized to an integer , and TwoLog_n is initialized to the value of

for (k = 3; k <= n; k++)

A[k] = 0;
for (k = 2; k <= TwoLog_n; k++)
for (j = k+1; j <= n; j++)
A[j] = A[j] || (j%k);
for (j = 3; j <= n; j++)
if (!A[j]) printf("%d", j);

The set of numbers printed by this program fragment is

A. B.
C. D. { }
gatecse-2003 algorithms identify-function normal

Answer key☟

1.13.14 Identify Function: GATE CSE 2004 | Question: 41

Consider the following C program

main()
{
int x, y, m, n;
scanf("%d %d", &x, &y);
/* Assume x>0 and y>0*/
m = x; n = y;
while(m != n)
{
if (m > n)
m = m-n;
else
n = n-m;
}
printf("%d", n);
}

The program computes

A. using repeated subtraction B. using repeated subtraction

C. the greatest common divisor of and D. the least common multiple of and
gatecse-2004 algorithms normal identify-function

Answer key☟

1.13.15 Identify Function: GATE CSE 2004 | Question: 42

What does the following algorithm approximate? (Assume ).

x = m;
y = 1;
While (x-y > ϵ)
{
x = (x+y)/2;
y = m/x;
}
print(x);

A. B. C. D.
gatecse-2004 algorithms identify-function normal

Answer key☟

1.13.16 Identify Function: GATE CSE 2005 | Question: 31

Consider the following C-program:

 void foo (int n, int sum) {
int k = 0, j = 0;
if (n == 0) return;
k = n % 10; j = n/10;
sum = sum + k;
foo (j, sum);
printf ("%d,",k);
}

int main() {
int a = 2048, sum = 0;
foo(a, sum);
printf("%d\n", sum);
}

What does the above program print?

A. B.
C. D.
gatecse-2005 algorithms identify-function recursion normal

Answer key☟

1.13.17 Identify Function: GATE CSE 2006 | Question: 50

A set can be represented by an array as follows:

Consider the following algorithm in which , , and are Boolean arrays of size :
algorithm zzz(x[], y[], z[]) {
int i;
for(i=0; i<n; ++i)
z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] ∧ y[i]);
}

The set computed by the algorithm is:

A. B. C. D.
gatecse-2006 algorithms identify-function normal

Answer key☟

1.13.18 Identify Function: GATE CSE 2006 | Question: 53

Consider the following C-function in which and are two sorted integer arrays and be
another integer array,
void xyz(int a[], int b [], int c []){
int i,j,k;
i=j=k=0;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}

Which of the following condition(s) hold(s) after the termination of the while loop?

i. and if
ii. and if

A. only (i) B. only (ii)

C. either (i) or (ii) but not both D. neither (i) nor (ii)
gatecse-2006 algorithms identify-function normal

Answer key☟

1.13.19 Identify Function: GATE CSE 2009 | Question: 18

Consider the program below:

 #include <stdio.h>
int fun(int n, int *f_p) {
int t, f;
if (n <= 1) {
*f_p = 1;
return 1;
}
t = fun(n-1, f_p);
f = t + *f_p;
*f_p = t;
return f;
}

int main() {
int x = 15;
printf("%d/n", fun(5, &x));
return 0;
}

The value printed is:

A. B. C. D.
gatecse-2009 algorithms recursion identify-function normal

Answer key☟

1.13.20 Identify Function: GATE CSE 2010 | Question: 35

What is the value printed by the following C program?

#include<stdio.h>

int f(int *a, int n)

{
if (n <= 0) return 0;
else if (*a % 2 == 0) return *a+f(a+1, n-1);
else return *a - f(a+1, n-1);
}

int main()
{
int a[] = {12, 7, 13, 4, 11, 6};
printf("%d", f(a, 6));
return 0;
}

A. B. C. D.
gatecse-2010 algorithms recursion identify-function normal

Answer key☟

1.13.21 Identify Function: GATE CSE 2011 | Question: 48

Consider the following recursive C function that takes two arguments.

unsigned int foo(unsigned int n, unsigned int r) {
if (n>0) return ((n%r) + foo(n/r, r));
else return 0;
}

What is the return value of the function when it is called as ?

A. B. C. D.
gatecse-2011 algorithms recursion identify-function normal

Answer key☟

1.13.22 Identify Function: GATE CSE 2011 | Question: 49

Consider the following recursive C function that takes two arguments.

unsigned int foo(unsigned int n, unsigned int r) {
if (n>0) return ((n%r) + foo(n/r, r));
else return 0;
}
What is the return value of the function when it is called as ?

A. B. C. D.
gatecse-2011 algorithms recursion identify-function normal

Answer key☟

1.13.23 Identify Function: GATE CSE 2013 | Question: 31

Consider the following function:

int unknown(int n){

int i, j, k=0;
for (i=n/2; i<=n; i++)
for (j=2; j<=n; j=j*2)
k = k + n/2;
return (k);

The return value of the function is

A. B.
C. D.
gatecse-2013 algorithms identify-function normal

Answer key☟

1.13.24 Identify Function: GATE CSE 2014 Set 1 | Question: 41

Consider the following C function in which size is the number of elements in the array E:
int MyX(int *E, unsigned int size)
{
int Y = 0;
int Z;
int i, j, k;

for(i = 0; i< size; i++)

Y = Y + E[i];

for(i=0; i < size; i++)

for(j = i; j < size; j++)
{
Z = 0;
for(k = i; k <= j; k++)
Z = Z + E[k];
if(Z > Y)
Y = Z;
}
return Y;
}

The value returned by the function MyX is the

A. maximum possible sum of elements in any sub-array of array E.

B. maximum element in any sub-array of array E.
C. sum of the maximum elements in all possible sub-arrays of array E.
D. the sum of all the elements in the array E.

gatecse-2014-set1 algorithms identify-function normal

Answer key☟

1.13.25 Identify Function: GATE CSE 2014 Set 2 | Question: 10

Consider the function func shown below:

int func(int num) {
int count = 0;
while (num) {
count++;
 num>>= 1;
}
return (count);
}

The value returned by func( ) is ________

gatecse-2014-set2 algorithms identify-function numerical-answers easy

Answer key☟

1.13.26 Identify Function: GATE CSE 2014 Set 3 | Question: 10

Let be the square matrix of size . Consider the following pseudocode. What is the expected output?
C=100;
for i=1 to n do
for j=1 to n do
{
Temp = A[i][j]+C;
A[i][j] = A[j][i];
A[j][i] = Temp -C;
}
for i=1 to n do
for j=1 to n do
output (A[i][j]);

A. The matrix itself

B. Transpose of the matrix
C. Adding to the upper diagonal elements and subtracting from lower diagonal elements of
D. None of the above

gatecse-2014-set3 algorithms identify-function easy

Answer key☟

1.13.27 Identify Function: GATE CSE 2015 Set 1 | Question: 31

Consider the following C function.

int fun1 (int n) {
int i, j, k, p, q = 0;
for (i = 1; i < n; ++i)
{
p = 0;
for (j = n; j > 1; j = j/2)
++p;
for (k = 1; k < p; k = k * 2)
++q;
}
return q;
}

Which one of the following most closely approximates the return value of the function ?

A. B. C. D.
gatecse-2015-set1 algorithms normal identify-function

Answer key☟

1.13.28 Identify Function: GATE CSE 2015 Set 2 | Question: 11

Consider the following C function.

int fun(int n) {
int x=1, k;
if (n==1) return x;
for (k=1; k<n; ++k)
x = x + fun(k) * fun (n-k);
return x;
}

The return value of is ______.

 gatecse-2015-set2 algorithms identify-function recurrence-relation normal numerical-answers

Answer key☟

1.13.29 Identify Function: GATE CSE 2015 Set 3 | Question: 49

Suppose is an array of length , where all the entries are from the set . For
any positive integers , consider the following pseudocode.
DOSOMETHING (c, a, n)

for
do
if
then
return z
If , then the output of DOSOMETHING(c, a, n) is _______.

gatecse-2015-set3 algorithms identify-function normal numerical-answers

Answer key☟

1.13.30 Identify Function: GATE CSE 2019 | Question: 26

Consider the following C function.

void convert (int n ) {
if (n<0)
printf{“%d”, n);
else {
convert(n/2);
printf(“%d”, n%2);
}
}

Which one of the following will happen when the function convert is called with any positive integer as argument?

A. It will print the binary representation of and terminate

B. It will print the binary representation of in the reverse order and terminate
C. It will print the binary representation of but will not terminate
D. It will not print anything and will not terminate

gatecse-2019 algorithms identify-function 2-marks

Answer key☟

1.13.31 Identify Function: GATE CSE 2020 | Question: 48

Consider the following C functions.

int tob (int b, int* arr) { int pp(int a, int b) {

int i; int arr[20];
for (i = 0; b>0; i++) { int i, tot = 1, ex, len;
if (b%2) arr [i] = 1; ex = a;
else arr[i] = 0; len = tob(b, arr);
b = b/2; for (i=0; i<len ; i++) {
} if (arr[i] ==1)
return (i); tot = tot * ex;
} ex= ex*ex;
}
return (tot) ;
}

The value returned by is _______.

gatecse-2020 numerical-answers identify-function 2-marks

Answer key☟
1.13.32 Identify Function: GATE CSE 2021 Set 1 | Question: 48

Consider the following function:

int SimpleFunction(int Y[], int n, int x)
{
int total = Y[0], loopIndex;
for (loopIndex=1; loopIndex<=n-1; loopIndex++)
total=x*total +Y[loopIndex];
return total;
}

Let be an array of elements with , for all such that . The value returned by
is __________

gatecse-2021-set1 algorithms numerical-answers identify-function 2-marks

Answer key☟

1.13.33 Identify Function: GATE CSE 2021 Set 2 | Question: 23

Consider the following function:

int SomeFunction (int x, int y)
{
if ((x==1) || (y==1)) return 1;
if (x==y) return x;
if (x > y) return SomeFunction(x-y, y);
if (y > x) return SomeFunction (x, y-x);

The value returned by is __________

gatecse-2021-set2 numerical-answers algorithms identify-function output 1-mark

Answer key☟

1.13.34 Identify Function: GATE IT 2005 | Question: 53

The following function takes two ASCII strings and determines whether one is an anagram of the other. An
anagram of a string s is a string obtained by permuting the letters in s.
int anagram (char *a, char *b) {
int count [128], j;
for (j = 0; j < 128; j++) count[j] = 0;
j = 0;
while (a[j] && b[j]) {
A;
B;
}
for (j = 0; j < 128; j++) if (count [j]) return 0;
return 1;
}

Choose the correct alternative for statements and .

A. A: count [a[j]]++ and B: count[b[j]]--

B. A: count [a[j]]++ and B: count[b[j]]++
C. A: count [a[j++]]++ and B: count[b[j]]--
D. A: count [a[j]]++ and B: count[b[j++]]--

gateit-2005 normal identify-function

Answer key☟

1.13.35 Identify Function: GATE IT 2005 | Question: 57

What is the output printed by the following program?

#include <stdio.h>

int f(int n, int k) {

 if (n == 0) return 0;
else if (n % 2) return f(n/2, 2*k) + k;
else return f(n/2, 2*k) - k;
}

int main () {
printf("%d", f(20, 1));
return 0;
}

A. B. C. D.
gateit-2005 algorithms identify-function normal

Answer key☟

1.13.36 Identify Function: GATE IT 2006 | Question: 52

The following function computes the value of correctly for all legal values and ( and
)
int func(int m, int n)
{
if (E) return 1;
else return(func(m -1, n) + func(m - 1, n - 1));
}

In the above function, which of the following is the correct expression for E?

A. B. &&
C. D. &&
gateit-2006 algorithms identify-function normal

Answer key☟

1.13.37 Identify Function: GATE IT 2008 | Question: 82

Consider the code fragment written in C below :

void f (int n)
{
if (n <=1) {
printf ("%d", n);
}
else {
f (n/2);
printf ("%d", n%2);
}
}

What does f(173) print?

A. B. C. D.
gateit-2008 algorithms recursion identify-function normal

Answer key☟

1.13.38 Identify Function: GATE IT 2008 | Question: 83

Consider the code fragment written in C below :

void f (int n)
{
if (n <= 1) {
printf ("%d", n);
}
else {
f (n/2);
printf ("%d", n%2);
}
}
 Which of the following implementations will produce the same output for as the above code?
P1 P2

void f (int n)
{
void f (int n)
if (n <=1) {
{
printf ("%d", n);
if (n/2) {
}
f(n/2);
else {
}
printf ("%d", n%2);
printf ("%d", n%2);
f (n/2);
}
}
}

A. Both and B. only C. only D. Neither nor

gateit-2008 algorithms recursion identify-function normal

Answer key☟

1.14 Insertion Sort (2)

1.14.1 Insertion Sort: GATE CSE 2003 | Question: 22

The usual implementation of Insertion Sort to sort an array uses linear search to identify the position
where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search
to identify the position, the worst case running time will

A. remain B. become
C. become D. become
gatecse-2003 algorithms sorting time-complexity normal insertion-sort

Answer key☟

1.14.2 Insertion Sort: GATE CSE 2003 | Question: 62

In a permutation , of distinct integers, an inversion is a pair such that and

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to
permutations of with at most inversions?

A. B. C. D.
gatecse-2003 algorithms sorting normal insertion-sort

Answer key☟

1.15 Matrix Chain Ordering (3)

1.15.1 Matrix Chain Ordering: GATE CSE 2011 | Question: 38

Four Matrices and of dimensions and respectively can be

multiplied in several ways with different number of total scalar multiplications. For example when multiplied
as , the total number of scalar multiplications is . When multiplied as
, the total number of scalar multiplications is .

If and , then the minimum number of scalar multiplications needed is

A. B. C. D.
gatecse-2011 algorithms dynamic-programming normal matrix-chain-ordering

Answer key☟

1.15.2 Matrix Chain Ordering: GATE CSE 2016 Set 2 | Question: 38

Let and be four matrices of dimensions and , respectively.

The minimum number of scalar multiplications required to find the product using the basic
matrix multiplication method is _________.
 gatecse-2016-set2 dynamic-programming algorithms matrix-chain-ordering normal numerical-answers

Answer key☟

1.15.3 Matrix Chain Ordering: GATE CSE 2018 | Question: 31

Assume that multiplying a matrix of dimension with another matrix of dimension requires
scalar multiplications. Computing the product of matrices can be done by
parenthesizing in different ways. Define as an explicitly computed pair for a given paranthesization if
they are directly multiplied. For example, in the matrix multiplication chain using
parenthesization and are only explicitly computed pairs.
Consider a matrix multiplication chain , where matrices and are of dimensions
and , respectively. In the parenthesization of that
minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

A. and only B. only

C. only D. and only
gatecse-2018 algorithms dynamic-programming 2-marks matrix-chain-ordering

Answer key☟

1.16 Merge Sort (3)

1.16.1 Merge Sort: GATE CSE 1999 | Question: 1.14, ISRO2015-42

If one uses straight two-way merge sort algorithm to sort the following elements in ascending order:

then the order of these elements after second pass of the algorithm is:

A.
B.
C.
D.

gate1999 algorithms merge-sort normal isro2015 sorting

Answer key☟

1.16.2 Merge Sort: GATE CSE 2012 | Question: 39

A list of strings, each of length , is sorted into lexicographic order using the merge-sort algorithm. The
worst case running time of this computation is

A. B. C. D.
gatecse-2012 algorithms sorting normal merge-sort

Answer key☟

1.16.3 Merge Sort: GATE CSE 2015 Set 3 | Question: 27

Assume that a mergesort algorithm in the worst case takes seconds for an input of size . Which of the
following most closely approximates the maximum input size of a problem that can be solved in minutes?

A. B. C. D.
gatecse-2015-set3 algorithms sorting merge-sort

Answer key☟

1.17 Merging (2)

1.17.1 Merging: GATE CSE 1995 | Question: 1.16

For merging two sorted lists of sizes and into a sorted list of size , we require comparisons of
 A. B. C. D.

gate1995 algorithms sorting normal merging

Answer key☟

1.17.2 Merging: GATE CSE 2014 Set 2 | Question: 38

Suppose are sorted sequences having lengths respectively. They are to

be merged into a single sequence by merging together two sequences at a time. The number of
comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

gatecse-2014-set2 algorithms sorting normal numerical-answers merging

Answer key☟

1.18 Minimum Spanning Tree (33)

1.18.1 Minimum Spanning Tree: GATE CSE 1991 | Question: 03,vi

Kruskal’s algorithm for finding a minimum spanning tree of a weighted graph with vertices and edges
has the time complexity of:

A. B. C. D.

E.
gate1991 algorithms graph-algorithms minimum-spanning-tree time-complexity multiple-selects

Answer key☟

1.18.2 Minimum Spanning Tree: GATE CSE 1992 | Question: 01,ix

Complexity of Kruskal’s algorithm for finding the minimum spanning tree of an undirected graph containing
vertices and edges if the edges are sorted is _______

gate1992 minimum-spanning-tree algorithms time-complexity easy fill-in-the-blanks

Answer key☟

1.18.3 Minimum Spanning Tree: GATE CSE 1995 | Question: 22

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

gate1995 algorithms graph-algorithms minimum-spanning-tree easy descriptive

Answer key☟

1.18.4 Minimum Spanning Tree: GATE CSE 1996 | Question: 16

A complete, undirected, weighted graph is given on the vertex for any fixed ‘n’. Draw
the minimum spanning tree of if

A. the weight of the edge is

B. the weight of the edge is

gate1996 algorithms graph-algorithms minimum-spanning-tree normal descriptive

Answer key☟
1.18.5 Minimum Spanning Tree: GATE CSE 1997 | Question: 9

Consider a graph whose vertices are points in the plane with integer co-ordinates such that
and , where is an integer. Two vertices and are adjacent iff
. The weight of an edge

A. What is the weight of a minimum weight-spanning tree in this graph? Write only the answer without any
explanations.
B. What is the weight of a maximum weight-spanning tree in this graph? Write only the answer without any
explanations.

gate1997 algorithms minimum-spanning-tree normal descriptive

Answer key☟

1.18.6 Minimum Spanning Tree: GATE CSE 2000 | Question: 2.18

Let be an undirected connected graph with distinct edge weights. Let be the edge with maximum
weight and the edge with minimum weight. Which of the following statements is false?

A. Every minimum spanning tree of must contain

B. If is in a minimum spanning tree, then its removal must disconnect
C. No minimum spanning tree contains
D. has a unique minimum spanning tree

gatecse-2000 algorithms minimum-spanning-tree normal

Answer key☟

1.18.7 Minimum Spanning Tree: GATE CSE 2001 | Question: 15

Consider a weighted undirected graph with vertex set and edge set
.
The third value in each tuple represents the weight of the edge specified in the tuple.

A. List the edges of a minimum spanning tree of the graph.

B. How many distinct minimum spanning trees does this graph have?
C. Is the minimum among the edge weights of a minimum spanning tree unique over all possible minimum
spanning trees of a graph?
D. Is the maximum among the edge weights of a minimum spanning tree unique over all possible minimum
spanning tree of a graph?

gatecse-2001 algorithms minimum-spanning-tree normal descriptive

Answer key☟

1.18.8 Minimum Spanning Tree: GATE CSE 2003 | Question: 68

What is the weight of a minimum spanning tree of the following graph?

A. B. C. D.
 gatecse-2003 algorithms minimum-spanning-tree normal

Answer key☟

1.18.9 Minimum Spanning Tree: GATE CSE 2005 | Question: 6

An undirected graph has nodes. its adjacency matrix is given by an square matrix whose (i)
diagonal elements are 0’s and (ii) non-diagonal elements are 1’s. Which one of the following is TRUE?

A. Graph has no minimum spanning tree (MST)

B. Graph has unique MST of cost
C. Graph has multiple distinct MSTs, each of cost
D. Graph has multiple spanning trees of different costs

gatecse-2005 algorithms minimum-spanning-tree normal

Answer key☟

1.18.10 Minimum Spanning Tree: GATE CSE 2006 | Question: 11

Consider a weighted complete graph on the vertex set such that the weight of the
edge is . The weight of a minimum spanning tree of is:

A. B. C. D.

gatecse-2006 algorithms minimum-spanning-tree normal

Answer key☟

1.18.11 Minimum Spanning Tree: GATE CSE 2006 | Question: 47

Consider the following graph:

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. B.
C. D.
gatecse-2006 algorithms graph-algorithms minimum-spanning-tree normal

Answer key☟

1.18.12 Minimum Spanning Tree: GATE CSE 2007 | Question: 49

Let be the minimum weight among all edge weights in an undirected connected graph. Let be a specific
edge of weight . Which of the following is FALSE?

A. There is a minimum spanning tree containing

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

Answer key☟

1.18.13 Minimum Spanning Tree: GATE CSE 2009 | Question: 38

Consider the following graph:

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

A.
B.
C.
D.

gatecse-2009 algorithms minimum-spanning-tree normal

Answer key☟

1.18.14 Minimum Spanning Tree: GATE CSE 2010 | Question: 50

Consider a complete undirected graph with vertex set . Entry in the matrix below is the
weight of the edge

What is the minimum possible weight of a spanning tree in this graph such that vertex is a leaf node in the tree
?

A. B. C. D.
gatecse-2010 algorithms minimum-spanning-tree normal

Answer key☟

1.18.15 Minimum Spanning Tree: GATE CSE 2010 | Question: 51

Consider a complete undirected graph with vertex set . Entry in the matrix below is the
weight of the edge

What is the minimum possible weight of a path from vertex to vertex in this graph such that contains at
most edges?

A. B. C. D.
gatecse-2010 normal algorithms minimum-spanning-tree

Answer key☟

1.18.16 Minimum Spanning Tree: GATE CSE 2011 | Question: 54

An undirected graph contains nodes named . Two nodes are

connected if and only if . Each edge is assigned a weight . A sample graph with
is shown below.

What will be the cost of the minimum spanning tree (MST) of such a graph with nodes?

A. B. C. D.
gatecse-2011 algorithms graph-algorithms minimum-spanning-tree normal

Answer key☟

1.18.17 Minimum Spanning Tree: GATE CSE 2011 | Question: 55

An undirected graph contains nodes named . Two nodes are

connected if and only if . Each edge is assigned a weight . A sample graph with
is shown below.

The length of the path from to in the MST of previous question with is

A. B. C. D.
gatecse-2011 algorithms graph-algorithms minimum-spanning-tree normal

Answer key☟

1.18.18 Minimum Spanning Tree: GATE CSE 2012 | Question: 29

Let be a weighted graph with edge weights greater than one and be the graph constructed by squaring
the weights of edges in . Let and be the minimum spanning trees of and , respectively, with total
weights and . Which of the following statements is TRUE?

A. with total weight B. with total weight

C. but total weight D. None of the above
gatecse-2012 algorithms minimum-spanning-tree normal marks-to-all

Answer key☟

1.18.19 Minimum Spanning Tree: GATE CSE 2014 Set 2 | Question: 52

The number of distinct minimum spanning trees for the weighted graph below is _____
 gatecse-2014-set2 algorithms minimum-spanning-tree numerical-answers normal

Answer key☟

1.18.20 Minimum Spanning Tree: GATE CSE 2015 Set 1 | Question: 43

The graph shown below has edges with distinct integer edge weights. The minimum spanning tree (MST)
is of weight and contains the edges: . 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 edges of this graph is_______________.

gatecse-2015-set1 algorithms minimum-spanning-tree normal numerical-answers

Answer key☟

1.18.21 Minimum Spanning Tree: GATE CSE 2015 Set 3 | Question: 40

Let be a connected undirected graph of vertices and edges. The weight of a minimum spanning
tree of is . When the weight of each edge of is increased by five, the weight of a minimum spanning
tree becomes ______.

gatecse-2015-set3 algorithms minimum-spanning-tree easy numerical-answers

Answer key☟

1.18.22 Minimum Spanning Tree: GATE CSE 2016 Set 1 | Question: 14

Let be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is
increased by the same value, then which of the following statements is/are TRUE?

: Minimum spanning tree of does not change.

: Shortest path between any pair of vertices does not change.

A. only B. only C. Neither nor D. Both and

gatecse-2016-set1 algorithms minimum-spanning-tree normal

Answer key☟

1.18.23 Minimum Spanning Tree: GATE CSE 2016 Set 1 | Question: 39

Let be a complete undirected graph on vertices, having edges with weights being and .
The maximum possible weight that a minimum weight spanning tree of can have is __________

gatecse-2016-set1 algorithms minimum-spanning-tree normal numerical-answers

Answer key☟
1.18.24 Minimum Spanning Tree: GATE CSE 2016 Set 1 | Question: 40

is an undirected simple graph in which each edge has a distinct weight, and is a particular
edge of . Which of the following statements about the minimum spanning trees of is/are
TRUE?

I. If is the lightest edge of some cycle in , then every MST of includes .

II. If is the heaviest edge of some cycle in , then every MST of excludes .

A. I only. B. II only. C. Both I and II. D. Neither I nor II.

gatecse-2016-set1 algorithms minimum-spanning-tree normal

Answer key☟

1.18.25 Minimum Spanning Tree: GATE CSE 2018 | Question: 47

Consider the following undirected graph :

Choose a value for that will maximize the number of minimum weight spanning trees (MWSTs) of . The number
of MWSTs of for this value of is ____.

gatecse-2018 algorithms graph-algorithms minimum-spanning-tree numerical-answers 2-marks

Answer key☟

1.18.26 Minimum Spanning Tree: GATE CSE 2020 | Question: 31

Let be a weighted undirected graph and let be a Minimum Spanning Tree (MST) of
maintained using adjacency lists. Suppose a new weighed edge is added to . The worst
case time complexity of determining if is still an MST of the resultant graph is

A. B.

C. D.

gatecse-2020 algorithms minimum-spanning-tree graph-algorithms 2-marks

Answer key☟

1.18.27 Minimum Spanning Tree: GATE CSE 2020 | Question: 49

Consider a graph , where , , and

weight of the edge is . The weight of minimum spanning tree of is _________

gatecse-2020 numerical-answers algorithms graph-algorithms 2-marks minimum-spanning-tree

Answer key☟

1.18.28 Minimum Spanning Tree: GATE CSE 2021 Set 1 | Question: 17

Consider the following undirected graph with edge weights as shown:

The number of minimum-weight spanning trees of the graph is ___________.

gatecse-2021-set1 algorithms graph-algorithms minimum-spanning-tree numerical-answers 1-mark

Answer key☟

1.18.29 Minimum Spanning Tree: GATE CSE 2021 Set 2 | Question: 1

Let be a connected undirected weighted graph. Consider the following two statements.

: There exists a minimum weight edge in which is present in every minimum spanning tree of .
: If every edge in has distinct weight, then has a unique minimum spanning tree.

Which one of the following options is correct?

A. Both and are true B. is true and is false

C. is false and is true D. Both and are false
gatecse-2021-set2 algorithms graph-algorithms minimum-spanning-tree 1-mark

Answer key☟

1.18.30 Minimum Spanning Tree: GATE CSE 2022 | Question: 39

Consider a simple undirected weighted graph all of whose edge weights are distinct. Which of the
following statements about the minimum spanning trees of is/are

A. The edge with the second smallest weight is always part of any minimum spanning tree of
B. One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum
spanning tree of
C. Suppose be such that and . Consider the edge with the minimum weight such that one of
its vertices is in and the other in Such an edge will always be part of any minimum spanning tree of
D. can have multiple minimum spanning trees.

gatecse-2022 algorithms minimum-spanning-tree multiple-selects 2-marks

Answer key☟

1.18.31 Minimum Spanning Tree: GATE CSE 2022 | Question: 48

Let be a directed graph, where is the set of vertices and is the set of
directed edges, as defined by the following adjacency matrix

indicates a directed edge from node to node A of rooted at is

defined as a subgraph of such that the undirected version of is a tree, and contains a directed path from
to every other vertex in The number of such directed spanning trees rooted at vertex is
__________________.

gatecse-2022 numerical-answers algorithms minimum-spanning-tree 2-marks

Answer key☟
 1.18.32 Minimum Spanning Tree: GATE CSE 2024 | Set 2 | Question: 49

The number of distinct minimum-weight spanning trees of the following graph is

gatecse2024-set2 numerical-answers algorithms minimum-spanning-tree

Answer key☟

1.18.33 Minimum Spanning Tree: GATE IT 2005 | Question: 52

Let be a weighted undirected graph and e be an edge with maximum weight in . Suppose there is a
minimum weight spanning tree in containing the edge . Which of the following statements is always
TRUE?

A. There exists a cutset in having all edges of maximum weight.

B. There exists a cycle in having all edges of maximum weight.
C. Edge cannot be contained in a cycle.
D. All edges in have the same weight.

gateit-2005 algorithms minimum-spanning-tree normal

Answer key☟

1.19 Prims Algorithm (2)

1.19.1 Prims Algorithm: GATE IT 2004 | Question: 56

Consider the undirected graph below:

Using Prim's algorithm to construct a minimum spanning tree starting with node A, which one of the following
sequences of edges represents a possible order in which the edges would be added to construct the minimum
spanning tree?

A.
B.
C.
D.

gateit-2004 algorithms graph-algorithms normal prims-algorithm

Answer key☟

1.19.2 Prims Algorithm: GATE IT 2008 | Question: 45

For the undirected, weighted graph given below, which of the following sequences of edges represents a
correct execution of Prim's algorithm to construct a Minimum Span​ning Tree?
 A.
B.
C.
D.

gateit-2008 algorithms graph-algorithms minimum-spanning-tree normal prims-algorithm

Answer key☟

1.20 Quick Sort (14)

1.20.1 Quick Sort: GATE CSE 1987 | Question: 1-xviii

Let be a quicksort program to sort numbers in ascending order. Let and be the time taken by the
program for the inputs and , respectively. Which of the following holds?

A. B.
C. D.
gate1987 algorithms sorting quick-sort

Answer key☟

1.20.2 Quick Sort: GATE CSE 1989 | Question: 9

An input files has records with keys as given below:

This is to be sorted in non-decreasing order.

i. Sort the input file using QUICKSORT by correctly positioning the first element of the file/subfile. Show the
subfiles obtained at all intermediate steps. Use square brackets to demarcate subfiles.
ii. Sort the input file using -way- MERGESORT showing all major intermediate steps. Use square brackets to
demarcate subfiles.

gate1989 descriptive algorithms sorting quick-sort

Answer key☟

1.20.3 Quick Sort: GATE CSE 1992 | Question: 03,iv

Assume that the last element of the set is used as partition element in Quicksort. If distinct elements from
the set are to be sorted, give an input for which Quicksort takes maximum time.

gate1992 algorithms sorting easy quick-sort descriptive

Answer key☟

1.20.4 Quick Sort: GATE CSE 1996 | Question: 2.15

Quick-sort is run on two inputs shown below to sort in ascending order taking first element as pivot

i.
ii.

Let and be the number of comparisons made for the inputs (i) and (ii) respectively. Then,

A. B.
C. D. we cannot say anything for arbitrary
 gate1996 algorithms sorting normal quick-sort

Answer key☟

1.20.5 Quick Sort: GATE CSE 2001 | Question: 1.14

Randomized quicksort is an extension of quicksort where the pivot is chosen randomly. What is the worst
case complexity of sorting n numbers using Randomized quicksort?

A. B. C. D.
gatecse-2001 algorithms sorting time-complexity easy quick-sort

Answer key☟

1.20.6 Quick Sort: GATE CSE 2006 | Question: 52

The median of elements can be found in time. Which one of the following is correct about the
complexity of quick sort, in which median is selected as pivot?

A. B.
C. D.
gatecse-2006 algorithms sorting easy quick-sort

Answer key☟

1.20.7 Quick Sort: GATE CSE 2008 | Question: 43

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the
list into two sub-lists each of which contains at least one-fifth of the elements. Let be the number of
comparisons required to sort elements. Then

A. B.
C. D.
gatecse-2008 algorithms sorting easy quick-sort

Answer key☟

1.20.8 Quick Sort: GATE CSE 2009 | Question: 39

In quick-sort, for sorting elements, the smallest element is selected as pivot using an time
algorithm. What is the worst case time complexity of the quick sort?

A. B.
C. D.
gatecse-2009 algorithms sorting normal quick-sort

Answer key☟

1.20.9 Quick Sort: GATE CSE 2014 Set 1 | Question: 14

Let be quicksort program to sort numbers in ascending order using the first element as the pivot. Let
and be the number of comparisons made by P for the inputs and respectively.
Which one of the following holds?

A. B. C. D.
gatecse-2014-set1 algorithms sorting easy quick-sort

Answer key☟

1.20.10 Quick Sort: GATE CSE 2014 Set 3 | Question: 14

You have an array of elements. Suppose you implement quicksort by always choosing the central element
of the array as the pivot. Then the tightest upper bound for the worst case performance is

A. B. C. D.
 gatecse-2014-set3 algorithms sorting easy quick-sort

Answer key☟

1.20.11 Quick Sort: GATE CSE 2015 Set 1 | Question: 2

Which one of the following is the recurrence equation for the worst case time complexity of the quick sort
algorithm for sorting numbers? In the recurrence equations given in the options below, is a
constant.

A. B.
C. D.
gatecse-2015-set1 algorithms recurrence-relation sorting easy quick-sort

Answer key☟

1.20.12 Quick Sort: GATE CSE 2015 Set 2 | Question: 45

Suppose you are provided with the following function declaration in the C programming language.
int partition(int a[], int n);

The function treats the first element of 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 smallest element in an
array of size using the partition function. We assume .
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 (___________);
}
}

The missing arguments lists are respectively

A. left_end and left_end left_end

B. left_end and left_end left_end
left_end
C. left_end left_end left_end and D. left_end left_end and left_end
left_end
gatecse-2015-set2 algorithms normal sorting quick-sort

Answer key☟

1.20.13 Quick Sort: GATE CSE 2019 | Question: 20

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

gatecse-2019 numerical-answers algorithms quick-sort probability 1-mark

Answer key☟

1.20.14 Quick Sort: GATE DS&AI 2024 | Question: 20

Consider sorting the following array of integers in ascending order using an inplace Quicksort algorithm that
uses the last element as the pivot.
 The minimum number of swaps performed during this Quicksort is .

gate-ds-ai-2024 numerical-answers algorithms quick-sort

Answer key☟

1.21 Recurrence Relation (34)

1.21.1 Recurrence Relation: GATE CSE 1987 | Question: 10a

Solve the recurrence equations:

gate1987 algorithms recurrence-relation descriptive

Answer key☟

1.21.2 Recurrence Relation: GATE CSE 1988 | Question: 13iv

Solve the recurrence equations:

gate1988 descriptive algorithms recurrence-relation

Answer key☟

1.21.3 Recurrence Relation: GATE CSE 1989 | Question: 13b

Find a solution to the following recurrence equation:

gate1989 descriptive algorithms recurrence-relation

Answer key☟

1.21.4 Recurrence Relation: GATE CSE 1990 | Question: 17a

Express in terms of the harmonic number , where satisfies the

recurrence relation,

, for and

What is the asymptotic behaviour of as a function of ?

gate1990 descriptive algorithms recurrence-relation

Answer key☟

1.21.5 Recurrence Relation: GATE CSE 1992 | Question: 07a

Consider the function for which the pseudocode is given below :

Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
else
For i = 1 to n do
begin
 C←0
For j = 1 to n – 1 do
begin C ← C + 1 end
F1 = F1 * C
end
F = F1
end

[ is a positive integer greater than zero]

A. Derive a recurrence relation for .

gate1992 algorithms recurrence-relation descriptive

Answer key☟

1.21.6 Recurrence Relation: GATE CSE 1992 | Question: 07b

Consider the function for which the pseudocode is given below :

Function F(n)
begin
F1 ← 1
if(n=1) then F ← 3
else
For i = 1 to n do
begin
C←0
For j = 1 to n – 1 do
begin C ← C + 1 end
F1 = F1 * C
end
F = F1
end

[ is a positive integer greater than zero]

B. Solve the recurrence relation for a closed form solution of .

gate1992 algorithms recurrence-relation descriptive

Answer key☟

1.21.7 Recurrence Relation: GATE CSE 1993 | Question: 15

Consider the recursive algorithm given below:

procedure bubblesort (n);
var i,j: index; temp : item;
begin
for i:=1 to n-1 do
if A[i] > A[i+1] then
begin
temp := A[i];
A[i] := A[i+1];
A[i+1] := temp;
end;
bubblesort (n-1)
end

Let be the number of times the ‘if…then…’ statement gets executed when the algorithm is run with value . Set
up the recurrence relation by defining in terms of . Solve for .

gate1993 algorithms recurrence-relation normal descriptive

Answer key☟

1.21.8 Recurrence Relation: GATE CSE 1994 | Question: 1.7, ISRO2017-14

The recurrence relation that arises in relation with the complexity of binary search is:

A. B.
 C. D.
gate1994 algorithms recurrence-relation easy isro2017

Answer key☟

1.21.9 Recurrence Relation: GATE CSE 1996 | Question: 2.12

The recurrence relation

has the solution equal to

A. B. C. D. None of the above

gate1996 algorithms recurrence-relation normal

Answer key☟

1.21.10 Recurrence Relation: GATE CSE 1997 | Question: 15

Consider the following function.

Function F(n, m:integer):integer;
begin
if (n<=0) or (m<=0) then F:=1
else
F:F(n-1, m) + F(n, m-1);
end;

Use the recurrence relation to answer the following questions. Assume that
are positive integers. Write only the answers without any explanation.

a. What is the value of ?

b. What is the value of ?
c. How many recursive calls are made to the function , including the original call, when evaluating .

gate1997 algorithms recurrence-relation descriptive

Answer key☟

1.21.11 Recurrence Relation: GATE CSE 1997 | Question: 4.6

Let be the function defined by for .

Which of the following statements is true?

A. B.
C. D. None of the above
gate1997 algorithms recurrence-relation normal

Answer key☟

1.21.12 Recurrence Relation: GATE CSE 1998 | Question: 6a

Solve the following recurrence relation

gate1998 algorithms recurrence-relation descriptive

Answer key☟
1.21.13 Recurrence Relation: GATE CSE 2002 | Question: 1.3

The solution to the recurrence equation is

A. B. C. D.

gatecse-2002 algorithms recurrence-relation normal

Answer key☟

1.21.14 Recurrence Relation: GATE CSE 2002 | Question: 2.11

The running time of the following algorithm

Procedure
If return ( ) else return ;
is best described by

A. B. C. D.
gatecse-2002 algorithms recurrence-relation normal

Answer key☟

1.21.15 Recurrence Relation: GATE CSE 2003 | Question: 35

Consider the following recurrence relation

for all
The value of for is

A. B.
C. D.
gatecse-2003 algorithms time-complexity recurrence-relation difficult

Answer key☟

1.21.16 Recurrence Relation: GATE CSE 2004 | Question: 83, ISRO2015-40

The time complexity of the following C function is (assume )

int recursive (int n) {
if(n == 1)
return (1);
else
return (recursive (n-1) + recursive (n-1));
}

A. B. C. D.
gatecse-2004 algorithms recurrence-relation time-complexity normal isro2015

Answer key☟

1.21.17 Recurrence Relation: GATE CSE 2004 | Question: 84

The recurrence equation

evaluates to

A. B. C. D.
gatecse-2004 algorithms recurrence-relation normal

Answer key☟
1.21.18 Recurrence Relation: GATE CSE 2006 | Question: 51, ISRO2016-34

Consider the following recurrence:

Which one of the following is true?

A. B.
C. D.
algorithms recurrence-relation isro2016 gatecse-2006

Answer key☟

1.21.19 Recurrence Relation: GATE CSE 2008 | Question: 78

Let denote the number of binary strings of length that contain no consecutive s.
Which of the following recurrences does satisfy?

A. B.
C. D.
gatecse-2008 algorithms recurrence-relation normal

Answer key☟

1.21.20 Recurrence Relation: GATE CSE 2008 | Question: 79

Let denote the number of binary strings of length that contain no consecutive s.
The value of is

A. B. C. D.
gatecse-2008 algorithms recurrence-relation normal

Answer key☟

1.21.21 Recurrence Relation: GATE CSE 2009 | Question: 35

The running time of an algorithm is represented by the following recurrence relation:

Which one of the following represents the time complexity of the algorithm?

A. B.
C. D.
gatecse-2009 algorithms recurrence-relation time-complexity normal

Answer key☟

1.21.22 Recurrence Relation: GATE CSE 2012 | Question: 16

The recurrence relation capturing the optimal execution time of the problem with
discs is

A. B.
C. D.
gatecse-2012 algorithms easy recurrence-relation

Answer key☟

1.21.23 Recurrence Relation: GATE CSE 2014 Set 2 | Question: 13

Which one of the following correctly determines the solution of the recurrence relation with ?
 A. B. C. D.
gatecse-2014-set2 algorithms recurrence-relation normal

Answer key☟

1.21.24 Recurrence Relation: GATE CSE 2015 Set 1 | Question: 49

Let a represent the number of bit strings of length n containing two consecutive s. What is the recurrence
relation for ?

A. B.
C. D.
gatecse-2015-set1 algorithms recurrence-relation normal

Answer key☟

1.21.25 Recurrence Relation: GATE CSE 2015 Set 3 | Question: 39

Consider the following recursive C function.

void get(int n)
{
if (n<1) return;
get (n-1);
get (n-3);
printf("%d", n);
}

If function is being called in then how many times will the function be invoked before returning
to the ?

A. B. C. D.
gatecse-2015-set3 algorithms recurrence-relation normal

Answer key☟

1.21.26 Recurrence Relation: GATE CSE 2016 Set 2 | Question: 39

The given diagram shows the flowchart for a recursive function . Assume that all statements, except for
the recursive calls, have time complexity. If the worst case time complexity of this function is ,
then the least possible value (accurate up to two decimal positions) of is ________.
Flow chart for Recursive Function .

gatecse-2016-set2 algorithms time-complexity recurrence-relation normal numerical-answers

Answer key☟

1.21.27 Recurrence Relation: GATE CSE 2017 Set 2 | Question: 30

Consider the recurrence function

Then in terms of notation is

A. B.
C. D.
gatecse-2017-set2 algorithms recurrence-relation

Answer key☟

1.21.28 Recurrence Relation: GATE CSE 2020 | Question: 2

For parameters and , both of which are , , and . Then is

A. B. )
C. ) D. )
gatecse-2020 algorithms recurrence-relation 1-mark

Answer key☟

1.21.29 Recurrence Relation: GATE CSE 2021 Set 1 | Question: 30

Consider the following recurrence relation.

Which one of the following options is correct?

A. B.
C. D.
gatecse-2021-set1 algorithms recurrence-relation time-complexity 2-marks

Answer key☟

1.21.30 Recurrence Relation: GATE CSE 2021 Set 2 | Question: 39

For constants and , consider the following recurrence defined on the non-negative integers:

Which one of the following options is correct about the recurrence ?

A. If is , then is
B. If is , then is

C. If is for some , then is

D. If is , then is

gatecse-2021-set2 algorithms recurrence-relation 2-marks

Answer key☟

1.21.31 Recurrence Relation: GATE CSE 2024 | Set 1 | Question: 32

Consider the following recurrence relation:

Which one of the following options is CORRECT?

A. B.
C. D.
 gatecse2024-set1 algorithms recurrence-relation

Answer key☟

1.21.32 Recurrence Relation: GATE IT 2004 | Question: 57

Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence
relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm.

Which of the following is the correct match between the algorithms and their recurrence relations?

A. B.
C. D.
gateit-2004 algorithms recurrence-relation normal match-the-following

Answer key☟

1.21.33 Recurrence Relation: GATE IT 2005 | Question: 51

Let be a function defined by the recurrence

for and

Which of the following statements is TRUE?

A. B.
C. D.
gateit-2005 algorithms recurrence-relation easy

Answer key☟

1.21.34 Recurrence Relation: GATE IT 2008 | Question: 44

When for some , the recurrence relation

,
evaluates to :

A. B.
C. D.
gateit-2008 algorithms recurrence-relation normal

Answer key☟

1.22 Recursion (4)

1.22.1 Recursion: GATE CSE 1995 | Question: 2.9

A language with string manipulation facilities uses the following operations

head(s): first character of a string
tail(s): all but exclude the first character of a string

concat(s1, s2): s1s2

For the string " " what will be the output of

concat(head(s), head(tail(tail(s))))
 A. B. C. D.
gate1995 algorithms normal recursion

Answer key☟

1.22.2 Recursion: GATE CSE 2007 | Question: 44

In the following C function, let .

int gcd(n,m) {
if (n%m == 0) return m;
n = n%m;
return gcd(m,n);
}

How many recursive calls are made by this function?

A. B.
C. D.
gatecse-2007 algorithms recursion time-complexity normal

Answer key☟

1.22.3 Recursion: GATE CSE 2018 | Question: 45

Consider the following program written in pseudo-code. Assume that and are integers.
Count (x, y) {
if (y !=1 ) {
if (x !=1) {
print("*");
Count (x/2, y);
}
else {
y=y-1;
Count (1024, y);
}
}
}

The number of times that the statement is executed by the call is _____

gatecse-2018 numerical-answers algorithms recursion 2-marks

Answer key☟

1.22.4 Recursion: GATE CSE 2021 Set 2 | Question: 49

Consider the following program

#include <stdio.h>
int foo(int x, int y, int q)
{
if ((x<=0) && (y<=0))
return q;
if (x<=0)
return foo(x, y-q, q);
if (y<=0)
return foo(x-q, y, q);
return foo(x, y-q, q) + foo(x-q, y, q);
}
int main( )
{
int r = foo(15, 15, 10);
printf(“%d”, r);
return 0;
}

The output of the program upon execution is _________

gatecse-2021-set2 algorithms recursion output numerical-answers 2-marks

Answer key☟
1.23 Searching (6)

1.23.1 Searching: GATE CSE 1996 | Question: 18

Consider the following program that attempts to locate an element in an array using binary search.
Assume . The program is erroneous. Under what conditions does the program fail?
var i,j,k: integer; x: integer;
a: array; [1..N] of integer;
begin i:= 1; j:= n;
repeat
k:(i+j) div 2;
if a[k] < x then i:= k
else j:= k
until (a[k] = x) or (i >= j);

if (a[k] = x) then
writeln ('x is in the array')
else
writeln ('x is not in the array')
end;

gate1996 algorithms searching normal descriptive

Answer key☟

1.23.2 Searching: GATE CSE 1996 | Question: 2.13, ISRO2016-28

The average number of key comparisons required for a successful search for sequential search on items
is

A. B. C. D. None of the above

gate1996 algorithms easy isro2016 searching

Answer key☟

1.23.3 Searching: GATE CSE 2002 | Question: 2.10

Consider the following algorithm for searching for a given number in an unsorted array having
distinct values:

1. Choose an at random from

2. If , then Stop else Goto 1;

Assuming that is present in , what is the expected number of comparisons made by the algorithm before it
terminates?

A. B. C. D.
gatecse-2002 searching normal

Answer key☟

1.23.4 Searching: GATE CSE 2008 | Question: 84

Consider the following C program that attempts to locate an element in an array using binary search.
The program is erroneous.
f (int Y[10] , int x) {
int i, j, k;
i= 0; j = 9;
do {
k = (i+ j) / 2;
if( Y[k] < x) i = k;else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}

On which of the following contents of and does the program fail?

 A. is and
B. is and
C. is and
D. is and and is even

gatecse-2008 algorithms searching normal

Answer key☟

1.23.5 Searching: GATE CSE 2008 | Question: 85

Consider the following C program that attempts to locate an element in an array using binary search.
The program is erroneous.
f (int Y[10] , int x) {
int i, j, k;
i= 0; j = 9;
do {
k = (i + j) / 2;
if( Y[k] < x) i = k;else j = k;
} while (Y[k] != x) && (i < j)) ;
if(Y[k] == x) printf(" x is in the array ") ;
else printf(" x is not in the array ") ;
}

The correction needed in the program to make it work properly is

A. Change line 6 to: if ; else ;

B. Change line 6 to: if ; else ;
C. Change line 6 to: if ; else ;
D. Change line 7 to: } while ;

gatecse-2008 algorithms searching normal

Answer key☟

1.23.6 Searching: GATE CSE 2017 Set 1 | Question: 48

Let be an array of numbers consisting of a sequence of 's followed by a sequence of 's. The
problem is to find the smallest index such that is by probing the minimum number of locations in .
The worst case number of probes performed by an optimal algorithm is ____________.

gatecse-2017-set1 algorithms normal numerical-answers searching

Answer key☟

1.24 Shortest Path (5)

1.24.1 Shortest Path: GATE CSE 2002 | Question: 12

Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a
directed graph with adjacency matrix . equals if there is an edge in from to , and
otherwise. Your aim in filling in the blanks is to ensure that the algorithm is correct.
INITIALIZATION: For i = 1 ... n
{For j = 1 ... n
{ if a[i,j] = 0 then P[i,j] =_______ else P[i,j] =_______;}
}

ALGORITHM: For i = 1 ... n

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

a. Copy the complete line containing the blanks in the Initialization step and fill in the blanks.
b. Copy the complete line containing the blanks in the Algorithm step and fill in the blanks.
c. Fill in the blank: The running time of the Algorithm is (___).
 gatecse-2002 algorithms graph-algorithms time-complexity normal descriptive shortest-path

Answer key☟

1.24.2 Shortest Path: GATE CSE 2003 | Question: 67

Let be an undirected graph with a subgraph . Weights are assigned to edges of

as follows.

A single-source shortest path algorithm is executed on the weighted graph with an arbitrary vertex of
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 to all vertices of

B. is connected
C. forms a clique in
D. is a tree

gatecse-2003 algorithms graph-algorithms normal shortest-path

Answer key☟

1.24.3 Shortest Path: GATE CSE 2007 | Question: 41

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

A. Dijkstra’s algorithm starting from . B. Warshall’s algorithm.

C. Performing a DFS starting from . D. Performing a BFS starting from .
gatecse-2007 algorithms graph-algorithms easy shortest-path

Answer key☟

1.24.4 Shortest Path: GATE CSE 2020 | Question: 40

Let be a directed, weighted graph with weight function . For some function
, for each edge , define as .
Which one of the options completes the following sentence so that it is TRUE?
“The shortest paths in under are shortest paths under too,_____________”.

A. for every
B. if and only if is positive
C. if and only if is negative
D. if and only if is the distance from to in the graph obtained by adding a new vertex to and edges of
zero weight from to every vertex of

gatecse-2020 algorithms graph-algorithms 2-marks shortest-path

Answer key☟

1.24.5 Shortest Path: GATE IT 2007 | Question: 3, UGCNET-June2012-III: 34

Consider a weighted, undirected graph with positive edge weights and let be an edge in the graph. It is
known that the shortest path from the source vertex to has weight 53 and the shortest path from to
has weight 65. Which one of the following statements is always TRUE?

A. Weight B. Weight
C. Weight D. Weight
gateit-2007 algorithms graph-algorithms normal ugcnetcse-june2012-paper3 shortest-path
 Answer key☟

1.25 Sorting (27)

1.25.1 Sorting: GATE CSE 1988 | Question: 1iii

Quicksort is ________ efficient than heapsort in the worst case.

gate1988 algorithms sorting fill-in-the-blanks easy

Answer key☟

1.25.2 Sorting: GATE CSE 1990 | Question: 3-v

The complexity of comparison based sorting algorithms is:

A. B.
C. D.
gate1990 normal algorithms sorting easy time-complexity multiple-selects

Answer key☟

1.25.3 Sorting: GATE CSE 1991 | Question: 01,vii

The minimum number of comparisons required to sort elements is ______

gate1991 normal algorithms sorting numerical-answers

Answer key☟

1.25.4 Sorting: GATE CSE 1991 | Question: 13

Give an optimal algorithm in pseudo-code for sorting a sequence of numbers which has only distinct
numbers ( is not known a Priori). Give a brief analysis for the time-complexity of your algorithm.

gate1991 sorting time-complexity algorithms difficult descriptive

Answer key☟

1.25.5 Sorting: GATE CSE 1992 | Question: 02,ix

Following algorithm(s) can be used to sort in the range in time

a. Heap sort b. Quick sort c. Merge sort d. Radix sort

gate1992 easy algorithms sorting multiple-selects

Answer key☟

1.25.6 Sorting: GATE CSE 1995 | Question: 12

Consider the following sequence of numbers:

Use Bubble sort to arrange the sequence in ascending order. Give the sequence at the end of each of the first five
passes.

gate1995 algorithms sorting easy descriptive bubble-sort

Answer key☟

1.25.7 Sorting: GATE CSE 1996 | Question: 14

A two dimensional array of integers is partially sorted if

a. The smallest item in the array is at where and .

b. The smallest item is deleted. Complete the following procedure to insert item (which is guaranteed to be
smaller than any item in the last row or column) still keeping partially sorted.
 procedure insert (x: integer);
var i,j: integer;
begin
i:=1; j:=1, A[i][j]:=x;
while (x > __ or x > __) do
if A[i+1][j] < A[i][j] ___ then begin
A[i][j]:=A[i+1][j]; i:=i+1;
end
else begin
_____
end
A[i][j]:= ____
end

gate1996 algorithms sorting normal descriptive

Answer key☟

1.25.8 Sorting: GATE CSE 1998 | Question: 1.22

Give the correct matching for the following pairs:

A. B.
C. D.
gate1998 algorithms sorting easy match-the-following

Answer key☟

1.25.9 Sorting: GATE CSE 1999 | Question: 1.12

A sorting technique is called stable if

A. it takes time
B. it maintains the relative order of occurrence of non-distinct elements
C. it uses divide and conquer paradigm
D. it takes space

gate1999 algorithms sorting easy

Answer key☟

1.25.10 Sorting: GATE CSE 1999 | Question: 8

Let be an matrix such that the elements in each row and each column are arranged in ascending
order. Draw a decision tree, which finds st, nd and rd smallest elements in minimum number of
comparisons.

gate1999 algorithms sorting normal descriptive

Answer key☟

1.25.11 Sorting: GATE CSE 2000 | Question: 17

An array contains four occurrences of , five occurrences of , and three occurrences of in any order. The
array is to be sorted using swap operations (elements that are swapped need to be adjacent).

a. What is the minimum number of swaps needed to sort such an array in the worst case?
b. Give an ordering of elements in the above array so that the minimum number of swaps needed to sort the
array is maximum.
 gatecse-2000 algorithms sorting normal descriptive

Answer key☟

1.25.12 Sorting: GATE CSE 2003 | Question: 61

In a permutation , of n distinct integers, an inversion is a pair such that and .

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen
permutation of ?

A. B. C. D.
gatecse-2003 algorithms sorting inversion normal

Answer key☟

1.25.13 Sorting: GATE CSE 2005 | Question: 39

Suppose there are sorted lists of elements each. The time complexity of producing a
sorted list of all these elements is: (Hint:Use a heap data structure)

A. B.
C. D.
gatecse-2005 algorithms sorting normal

Answer key☟

1.25.14 Sorting: GATE CSE 2006 | Question: 14, ISRO2011-14

Which one of the following in place sorting algorithms needs the minimum number of swaps?

A. Quick sort B. Insertion sort C. Selection sort D. Heap sort

gatecse-2006 algorithms sorting easy isro2011

Answer key☟

1.25.15 Sorting: GATE CSE 2007 | Question: 14

Which of the following sorting algorithms has the lowest worse-case complexity?

A. Merge sort B. Bubble sort C. Quick sort D. Selection sort

gatecse-2007 algorithms sorting time-complexity easy

Answer key☟

1.25.16 Sorting: GATE CSE 2009 | Question: 11

What is the number of swaps required to sort elements using selection sort, in the worst case?

A. B.
C. D.
gatecse-2009 algorithms sorting easy selection-sort

Answer key☟

1.25.17 Sorting: GATE CSE 2013 | Question: 30

The number of elements that can be sorted in time using heap sort is

A. B.
C. D.
gatecse-2013 algorithms sorting normal heap-sort

Answer key☟
1.25.18 Sorting: GATE CSE 2013 | Question: 6

Which one of the following is the tightest upper bound that represents the number of swaps required to sort
numbers using selection sort?

A. ) B. ) C. ) D. )
gatecse-2013 algorithms sorting easy selection-sort

Answer key☟

1.25.19 Sorting: GATE CSE 2014 Set 1 | Question: 39

The minimum number of comparisons required to find the minimum and the maximum of numbers is
________

gatecse-2014-set1 algorithms numerical-answers normal maximum-minimum sorting

Answer key☟

1.25.20 Sorting: GATE CSE 2016 Set 1 | Question: 13

The worst case running times of Insertion sort , Merge sort and Quick sort, respectively are:

A. , and
B. , and
C. , and
D. , and

gatecse-2016-set1 algorithms sorting easy

Answer key☟

1.25.21 Sorting: GATE CSE 2016 Set 2 | Question: 13

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

I. Quicksort runs in time

II. Bubblesort runs in time
III. Mergesort runs in time
IV. Insertion sort runs in time

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

gatecse-2016-set2 algorithms sorting time-complexity normal ambiguous

Answer key☟

1.25.22 Sorting: GATE CSE 2021 Set 1 | Question: 9

Consider the following array.

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 B. Mergesort

C. Insertion sort D. Quicksort using the last element as pivot
gatecse-2021-set1 algorithms sorting 1-mark

Answer key☟

1.25.23 Sorting: GATE CSE 2024 | Set 1 | Question: 31

An array is heapified. Which one of the following options

 represents the first three elements in the heapified array?

A. B. C. D.
gatecse2024-set1 algorithms heap-sort sorting

Answer key☟

1.25.24 Sorting: GATE CSE 2024 | Set 2 | Question: 25

Let be an array containing integer values. The distance of is defined as the minimum number of
elements in that must be replaced with another integer so that the resulting array is sorted in non-
decreasing order. The distance of the array is ___________.

gatecse2024-set2 numerical-answers algorithms sorting

Answer key☟

1.25.25 Sorting: GATE DS&AI 2024 | Question: 35

Consider the following sorting algorithms:

i. Bubble sort
ii. Insertion sort
iii. Selection sort

Which ONE among the following choices of sorting algorithms sorts the numbers in the array in
increasing order after exactly two passes over the array?

A. only B. only C. and only D. and only

gate-ds-ai-2024 algorithms sorting

Answer key☟

1.25.26 Sorting: GATE IT 2005 | Question: 59

Let and be two sorted arrays containing integers each, in non-decreasing order. Let be a sorted
array containing integers obtained by merging the two arrays and . Assuming the arrays are indexed
starting from , consider the following four statements

I.
II.
III.
IV.

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
gateit-2005 algorithms sorting normal

Answer key☟

1.25.27 Sorting: GATE IT 2008 | Question: 43

If we use Radix Sort to sort integers in the range , for some which is independent of ,
the time taken would be?

A. B. C. D.
gateit-2008 algorithms sorting normal

Answer key☟

1.26 Space Complexity (1)

 1.26.1 Space Complexity: GATE CSE 2005 | Question: 81a

double foo(int n)
{
int i;
double sum;
if(n == 0)
{
return 1.0;
}
else
{
sum = 0.0;
for(i = 0; i < n; i++)
{
sum += foo(i);
}
return sum;
}
}

The space complexity of the above code is?

A. B. C. D.
gatecse-2005 algorithms recursion normal space-complexity

Answer key☟

1.27 Strongly Connected Components (3)

1.27.1 Strongly Connected Components: GATE CSE 2008 | Question: 7

The most efficient algorithm for finding the number of connected components in an undirected graph on
vertices and edges has time complexity

A. B. C. D.
gatecse-2008 algorithms graph-algorithms time-complexity normal strongly-connected-components

Answer key☟

1.27.2 Strongly Connected Components: GATE CSE 2018 | Question: 43

Let be a graph with vertices, with each vertex labelled by a distinct permutation of the numbers
There is an edge between vertices and if and only if the label of can be obtained by
swapping two adjacent numbers in the label of . Let denote the degree of a vertex in , and denote the
number of connected components in . Then, ______.

gatecse-2018 algorithms graph-algorithms numerical-answers 2-marks strongly-connected-components

Answer key☟

1.27.3 Strongly Connected Components: GATE IT 2006 | Question: 46

Which of the following is the correct decomposition of the directed graph given below into its strongly
connected components?

A.
B.
C.
D.
 gateit-2006 algorithms graph-algorithms normal strongly-connected-components

Answer key☟

1.28 Time Complexity (29)

1.28.1 Time Complexity: GATE CSE 1988 | Question: 6i

Given below is the sketch of a program that represents the path in a two-person game tree by the sequence
of active procedure calls at any time. The program assumes that the payoffs are real number in a limited
range; that the constant INF is larger than any positive payoff and its negation is smaller than any negative payoff
and that there is a function “payoff” and that computes the payoff for any board that is a leaf. The type “boardtype”
has been suitably declared to represent board positions. It is player- ’s move if mode = MAX and player- ’s move if
mode=MIN. The type modetype =(MAX, MIN). The functions “min” and “max” find the minimum and maximum of
two real numbers.
function search(B: boardtype; mode: modetype): real;
var
C:boardtype; {a child of board B}
value:real;
begin
if B is a leaf then
return (payoff(B))
else
begin
if mode = MAX then value :=-INF
else
value:INF;
for each child C of board B do
if mode = MAX then
value:=max (value, search (C, MIN))
else
value:=min(value, search(C, MAX))
return(value)
end
end; (search)

Comment on the working principle of the above program. Suggest a possible mechanism for reducing the amount
of search.

gate1988 normal descriptive algorithms time-complexity

Answer key☟

1.28.2 Time Complexity: GATE CSE 1989 | Question: 2-iii

Match the pairs in the following:

gate1989 match-the-following algorithms time-complexity

Answer key☟

1.28.3 Time Complexity: GATE CSE 1993 | Question: 8.7

, where stands for order is:

A. B. C. D.

E.
gate1993 algorithms time-complexity easy

Answer key☟
1.28.4 Time Complexity: GATE CSE 1999 | Question: 1.13

Suppose we want to arrange the numbers stored in any array such that all negative values occur before all
positive ones. Minimum number of exchanges required in the worst case is

A. B. C. D. None of the above

gate1999 algorithms time-complexity normal

Answer key☟

1.28.5 Time Complexity: GATE CSE 1999 | Question: 1.16

If is a power of , then the minimum number of multiplications needed to compute is

A. B. C. D.
gate1999 algorithms time-complexity normal

Answer key☟

1.28.6 Time Complexity: GATE CSE 1999 | Question: 11a

Consider the following algorithms. Assume, procedure and procedure take and unit of
time respectively. Derive the time complexity of the algorithm in -notation.
algorithm what (n)
begin
if n = 1 then call A
else
begin
what (n-1);
call B(n)
end
end.

gate1999 algorithms time-complexity normal descriptive

Answer key☟

1.28.7 Time Complexity: GATE CSE 2000 | Question: 1.15

Let be a sorted array of integers. Let denote the time taken for the most efficient algorithm to
determined if there are two elements with sum less than in . Which of the following statement is true?

A. is B.
C. D.
gatecse-2000 easy algorithms time-complexity

Answer key☟

1.28.8 Time Complexity: GATE CSE 2003 | Question: 66

The cube root of a natural number is defined as the largest natural number such that . The
complexity of computing the cube root of ( is represented by binary notation) is

A. but not
B. but not for any constant
C. for some constant , but not for any constant
D. for some constant , but not

gatecse-2003 algorithms time-complexity normal

Answer key☟

1.28.9 Time Complexity: GATE CSE 2004 | Question: 39

Two matrices and are to be stored in arrays and respectively. Each array can be stored either
in row-major or column-major order in contiguous memory locations. The time complexity of an algorithm to
compute will be
 A. best if is in row-major, and 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

gatecse-2004 algorithms time-complexity easy

Answer key☟

1.28.10 Time Complexity: GATE CSE 2004 | Question: 82

Let be an array storing a bit ( or ) at each location, and is a function whose time
complexity is . Consider the following program fragment written in a C like language:
counter = 0;
for (i=1; i<=n; i++)
{
if (a[i] == 1) counter++;
else {f (counter); counter = 0;}
}

The complexity of this program fragment is

A. B.
C. D.
gatecse-2004 algorithms time-complexity normal

Answer key☟

1.28.11 Time Complexity: GATE CSE 2006 | Question: 15

Consider the following C-program fragment in which , and are integer variables.
for( i = n, j = 0; i > 0; i /= 2, j +=i );

Let denote the value stored in the variable after termination of the for loop. Which one of the following is
true?

A. B.
C. D.
gatecse-2006 algorithms normal time-complexity

Answer key☟

1.28.12 Time Complexity: GATE CSE 2007 | Question: 15, ISRO2016-26

Consider the following segment of C-code:

int j, n;
j = 1;
while (j <= n)
j = j * 2;

The number of comparisons made in the execution of the loop for any is:

A. B.
C. D.
gatecse-2007 algorithms time-complexity normal isro2016

Answer key☟

1.28.13 Time Complexity: GATE CSE 2007 | Question: 45

What is the of the following recursive function?

int DoSomething (int n) {
if (n <= 2)
return 1;
else
 return (DoSomething (floor (sqrt(n))) + n);
}

A. B.
C. D.
gatecse-2007 algorithms time-complexity normal

Answer key☟

1.28.14 Time Complexity: GATE CSE 2007 | Question: 50

An array of numbers is given, where is an even number. The maximum as well as the minimum of these
numbers needs to be determined. Which of the following is TRUE about the number of comparisons
needed?

A. At least comparisons, for some constant are needed.

B. At most comparisons are needed.
C. At least comparisons are needed
D. None of the above

gatecse-2007 algorithms time-complexity easy

Answer key☟

1.28.15 Time Complexity: GATE CSE 2007 | Question: 51

Consider the following C program segment:

int IsPrime (n)
{
int i, n;
for (i=2; i<=sqrt(n);i++)
if(n%i == 0)
{printf("Not Prime \n"); return 0;}
return 1;
}

Let denote number of times the loop is executed by the program on input . Which of the following is
TRUE?

A. B.
C. D. None of the above
gatecse-2007 algorithms time-complexity normal

Answer key☟

1.28.16 Time Complexity: GATE CSE 2008 | Question: 40

The minimum number of comparisons required to determine if an integer appears more than times in a
sorted array of integers is

A. B. C. D.
gatecse-2008 normal algorithms time-complexity

Answer key☟

1.28.17 Time Complexity: GATE CSE 2008 | Question: 47

We have a binary heap on elements and wish to insert more elements (not necessarily one after
another) into this heap. The total time required for this is

A. B. C. D.

gatecse-2008 algorithms time-complexity normal

Answer key☟
1.28.18 Time Complexity: GATE CSE 2008 | Question: 74

Consider the following C functions:

int f1 (int n)
{
if(n == 0 || n == 1)
return n;
else
return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i-1] + Z[i-2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

The running time of and are

A. and B. and
C. and D. and
gatecse-2008 algorithms time-complexity normal

Answer key☟

1.28.19 Time Complexity: GATE CSE 2008 | Question: 75

Consider the following C functions:

int f1 (int n)
{
if(n == 0 || n == 1)
return n;
else
return (2 * f1(n-1) + 3 * f1(n-2));
}
int f2(int n)
{
int i;
int X[N], Y[N], Z[N];
X[0] = Y[0] = Z[0] = 0;
X[1] = 1; Y[1] = 2; Z[1] = 3;
for(i = 2; i <= n; i++){
X[i] = Y[i-1] + Z[i-2];
Y[i] = 2 * X[i];
Z[i] = 3 * X[i];
}
return X[n];
}

and return the values

A. and B. and C. and D. and

gatecse-2008 normal algorithms time-complexity

Answer key☟

1.28.20 Time Complexity: GATE CSE 2010 | Question: 12

Two alternative packages and are available for processing a database having records. Package
requires time units and package requires time units to process records. What is
the smallest value of for which package will be preferred over ?

A. B. C. D.
gatecse-2010 algorithms time-complexity easy
 Answer key☟

1.28.21 Time Complexity: GATE CSE 2014 Set 1 | Question: 42

Consider the following pseudo code. What is the total number of multiplications to be performed?
D=2
for i = 1 to n do
for j = i to n do
for k = j + 1 to n do
D=D*3

A. Half of the product of the consecutive integers.

B. One-third of the product of the consecutive integers.
C. One-sixth of the product of the consecutive integers.
D. None of the above.

gatecse-2014-set1 algorithms time-complexity normal

Answer key☟

1.28.22 Time Complexity: GATE CSE 2015 Set 1 | Question: 40

An algorithm performs find operations , insert operations, delete operations, and

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
gatecse-2015-set1 algorithms data-structures normal time-complexity

Answer key☟

1.28.23 Time Complexity: GATE CSE 2015 Set 2 | Question: 22

An unordered list contains distinct elements. The number of comparisons to find an element in this list that
is neither maximum nor minimum is

A. B. C. D.
gatecse-2015-set2 algorithms time-complexity easy

Answer key☟

1.28.24 Time Complexity: GATE CSE 2017 Set 2 | Question: 03

Match the algorithms with their time complexities:

A.
B.
C.
D.

gatecse-2017-set2 algorithms time-complexity match-the-following easy

 Answer key☟

1.28.25 Time Complexity: GATE CSE 2017 Set 2 | Question: 38

Consider the following C function

int fun(int n) {
int i, j;
for(i=1; i<=n; i++) {
for (j=1; j<n; j+=i) {
printf("%d %d", i, j);
}
}
}

Time complexity of in terms of notation is

A. B.
C. D.
gatecse-2017-set2 algorithms time-complexity

Answer key☟

1.28.26 Time Complexity: GATE CSE 2019 | Question: 37

There are unsorted arrays: . Assume that is odd.Each of contains

distinct elements. There are no common elements between any two arrays. The worst-case time complexity
of computing the median of the medians of is

A. B.
C. D.
gatecse-2019 algorithms time-complexity 2-marks

Answer key☟

1.28.27 Time Complexity: GATE CSE 2024 | Set 1 | Question: 7

Given an integer array of size , we want to check if the array is sorted (in either ascending or descending
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

A. both and B. but

C. but not D. neither nor
gatecse2024-set1 algorithms time-complexity

Answer key☟

1.28.28 Time Complexity: GATE IT 2007 | Question: 17

Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the
tightest upper bound on the number of multiplications required to compute ?

A. B.
D.
C.

gateit-2007 algorithms time-complexity normal

Answer key☟

1.28.29 Time Complexity: GATE IT 2007 | Question: 81

Let be points in the -plane such that no three of them are collinear. For every pair of
points and , let be the line passing through them. Let be the line with the steepest gradient
among all lines.
The time complexity of the best algorithm for finding and is

A. B.
C. D.
 gateit-2007 algorithms time-complexity normal

Answer key☟

1.29 Topological Sort (4)

1.29.1 Topological Sort: GATE CSE 2007 | Question: 5

Consider the DAG with shown below.

Which of the following is not a topological ordering?

A. B. C. D.
gatecse-2007 algorithms graph-algorithms topological-sort easy

Answer key☟

1.29.2 Topological Sort: GATE CSE 2014 Set 1 | Question: 13

Consider the directed graph below given.

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.

gatecse-2014-set1 graph-algorithms easy topological-sort

Answer key☟

1.29.3 Topological Sort: GATE CSE 2016 Set 1 | Question: 11

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is _____________.

gatecse-2016-set1 algorithms graph-algorithms normal numerical-answers topological-sort

Answer key☟

1.29.4 Topological Sort: GATE DS&AI 2024 | Question: 41

​Consider the directed acyclic graph (DAG) below:

 Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG?

A. B.
C. D.
gate-ds-ai-2024 algorithms topological-sort directed-acyclic-graph

Answer key☟

Answer Keys
1.1.1 N/A 1.1.2 N/A 1.1.3 B 1.1.4 C 1.1.5 12
1.1.6 29 1.1.7 A;C 1.1.8 B 1.2.1 N/A 1.2.2 N/A
1.2.3 C 1.2.4 A 1.2.5 B 1.2.6 A 1.2.7 C
1.2.8 C 1.2.9 C 1.3.1 A;B 1.3.2 B 1.3.3 X
1.3.4 D 1.3.6 A 1.3.7 C 1.3.8 C 1.3.9 D
1.3.10 A 1.3.11 C 1.3.12 C 1.3.13 D 1.3.15 D
1.3.16 A 1.3.17 A;C 1.3.18 A;D 1.3.19 A 1.3.20 D
1.3.21 A 1.4.1 B 1.4.2 C 1.5.1 B 1.5.2 A
1.6.1 N/A 1.6.2 B 1.6.3 D 1.6.4 A 1.6.5 D
1.6.6 D 1.7.1 B 1.7.2 C 1.7.3 C 1.7.4 B
1.7.5 B 1.7.6 A 1.7.7 34 1.7.9 C 1.8.1 B
1.8.2 D 1.8.3 A 1.8.4 A 1.8.5 B 1.8.6 A
1.8.7 A;B 1.8.8 929 : 929 1.8.9 A 1.8.10 C 1.8.11 D
1.9.1 N/A 1.9.2 C 1.9.3 C 1.9.4 C 1.9.5 D
1.9.7 C 1.9.8 C 1.9.9 B 1.9.10 19 1.9.11 D
1.9.12 31 1.9.13 D 1.9.14 A 1.9.15 5040 1.9.16 C
1.9.17 60 1.9.18 A 1.9.19 D 1.9.20 D 1.9.21 D
1.9.22 B 1.10.1 A 1.10.2 B 1.10.3 D 1.10.4 A
1.10.5 16 1.11.1 B 1.11.2 N/A 1.11.3 13 1.11.4 C
1.11.5 B 1.11.6 C 1.11.7 D 1.12.1 2.33 1.12.2 A
1.12.3 D 1.12.4 225 1.12.5 B 1.12.6 A 1.13.1 N/A
1.13.2 N/A 1.13.3 C 1.13.4 A 1.13.5 N/A 1.13.6 C
1.13.7 C 1.13.8 N/A 1.13.9 C 1.13.10 D 1.13.11 A
1.13.12 B 1.13.13 D 1.13.14 C 1.13.15 C 1.13.16 D
1.13.17 D 1.13.18 D 1.13.19 B 1.13.21 B 1.13.22 D
1.13.23 B 1.13.24 A 1.13.25 9 1.13.26 A 1.13.27 D
1.13.28 51 1.13.29 0 1.13.30 D 1.13.31 81 1.13.32 1023 : 1023
1.13.33 15 : 15 1.13.34 D 1.13.35 C 1.13.36 C 1.13.37 D
1.14.1 A 1.14.2 D 1.15.1 C 1.15.2 1500 1.15.3 C
1.16.1 B 1.16.2 B 1.16.3 B 1.17.1 C 1.17.2 358
1.18.1 B;D;E 1.18.2 N/A 1.18.3 2 1.18.4 N/A 1.18.5 N/A
1.18.6 C 1.18.7 N/A 1.18.8 B 1.18.9 C 1.18.10 B
1.18.11 D 1.18.12 D 1.18.13 D 1.18.14 D 1.18.15 B
1.18.16 B 1.18.17 C 1.18.18 X 1.18.19 6 1.18.20 69
1.18.21 995 1.18.22 A 1.18.25 4 1.18.26 D 1.18.27 99
1.18.28 3:3 1.18.29 C 1.18.30 A;B;C 1.18.31 24 1.18.32 9
1.18.33 A 1.19.1 D 1.19.2 C 1.20.1 C 1.20.2 N/A
1.20.3 N/A 1.20.4 C 1.20.6 B 1.20.7 B 1.20.8 B
1.20.9 C 1.20.10 A 1.20.11 B 1.20.12 A 1.20.13 0.08
1.20.14 0 1.21.1 N/A 1.21.2 N/A 1.21.3 N/A 1.21.4 N/A
1.21.5 N/A 1.21.6 N/A 1.21.7 N/A 1.21.8 B 1.21.9 A
1.21.10 N/A 1.21.11 B 1.21.12 N/A 1.21.13 B 1.21.14 C
1.21.15 B 1.21.16 D 1.21.18 B 1.21.19 D 1.21.20 X
1.21.21 A 1.21.22 D 1.21.23 A 1.21.24 A 1.21.25 B
1.21.27 B 1.21.28 A 1.21.30 C 1.21.32 B 1.21.33 C
1.21.34 A 1.22.1 C 1.22.2 A 1.22.3 10230 1.22.4 60 : 60
1.23.1 N/A 1.23.2 C 1.23.3 A 1.23.4 C 1.23.5 A
1.24.1 N/A 1.24.2 B 1.24.3 D 1.24.4 A 1.24.5 C
1.25.1 N/A 1.25.2 A 1.25.3 7 1.25.4 N/A 1.25.5 D
1.25.6 N/A 1.25.7 N/A 1.25.8 B 1.25.9 B 1.25.10 N/A
1.25.11 N/A 1.25.12 B 1.25.13 A 1.25.14 C 1.25.15 A
1.25.16 A 1.25.17 C 1.25.18 B 1.25.19 147.1 : 148.1 1.25.20 D
1.25.21 D 1.25.22 C 1.25.23 D 1.25.24 3 1.25.25 B
1.25.26 C 1.25.27 C 1.26.1 B 1.27.1 C 1.27.2 109
1.27.3 B 1.28.1 N/A 1.28.2 N/A 1.28.3 B;C;D;E 1.28.4 D
1.28.5 A 1.28.6 N/A 1.28.7 A 1.28.8 C 1.28.9 D
1.28.10 C 1.28.11 C 1.28.12 X 1.28.13 D 1.28.14 B
1.28.15 B 1.28.16 B 1.28.17 B 1.28.18 B 1.28.19 C
1.28.20 C 1.28.21 C 1.28.22 A 1.28.23 D 1.28.24 C
1.28.25 C 1.28.27 A 1.28.28 A 1.28.29 B 1.29.1 D
1.29.2 C 1.29.4 B;D