Computer Science and Information Technology
GATE CSE Algorithms PYQs
Build your understanding with focused practice from past exam papers.
How to practice Algorithms
Separate the algorithm, its assumptions and the cost model. Practise tracing before estimating asymptotic complexity.
Attempt a question, record the concept and assumptions, then check the available answer. Rework mistakes after revising the relevant concepts. Topic tags can overlap; review the question context.
Questions 1–10 of 84. Imported answers require independent review unless marked reviewed.
Question 8
Open questionGAMCQ2 marksNeeds review
Figures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways.
A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which she started.
Which one of the following options is then true?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 17
Open questionCSMCQ1 markNeeds review
Consider the following recurrence relations:
For all
,
Assume that for all
,
and
.Which one of the following options is correct?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 24
Open questionCSMSQ1 markNeeds review
Consider a hash table
that is initially empty. The hash table is maintained using open addressing with linear probe. The hash function used is
.Consider the following sequence of insertions performed on
:
Which of the following positions in the hash table is/are empty after these insertions are performed?
Your answerSelect all correct options. You can choose more than one.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 24
Open questionCS2MCQ1 markNeeds review
Consider the following functions, where
is a positive integer.
Which one of the following options lists the functions in increasing order of asymptotic growth rate?
Note: Assume the base of log to be 2.
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 25
Open questionCS2MSQ1 markNeeds review
Which of the following can be recurrence relation(s) corresponding to an algorithm with time complexity
?Your answerSelect all correct options. You can choose more than one.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 32
Open questionCS2NAT1 markNeeds review
Consider an array
. Suppose the merge sort algorithm is executed on array
to sort it in increasing order. The merge sort algorithm will carry out a total of 7 merge operations.A merge operation on sorted left array
and sorted right array
is said to be void if the output of the merge operation is the elements of array
followed by the elements of array
.The number of void merge operations among these 7 merge operations is __________. (answer in integer)
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 36
Open questionCS2MCQ2 marksNeeds review
Consider a complete graph
with
vertices (
). Note that multiple spanning trees can be constructed over
. Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to the size of the union of the two sets.Which one of the following options gives the lowest possible value for the Jaccard coefficient between any two spanning trees of
?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 37
Open questionCS2MCQ2 marksNeeds review
Let
be a weighted directed acyclic graph with
edges and
vertices. Given
and a source vertex
in
, which one of the following options gives the worst case time complexity of the fastest algorithm to find the lengths of shortest paths from
to all vertices that are reachable from
in
?Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 38
Open questionCS2MCQ2 marksNeeds review
Consider an array
of integers of size
. The indices of
run from 1 to
. An algorithm is to be designed to check whether
satisfies the condition given below.
such that
,
Which one of the following gives the worst case time complexity of the fastest algorithm that can be designed for the problem?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answerQuestion 39
Open questionCS2MCQ2 marksNeeds review
Consider a table
, where the elements
,
, represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows:
Consider the following two algorithms to compute entries of
. Assume that for both the algorithms, for all
,
has been initialized to 1.Algorithm
: For
For
Algorithm
: For
For
For
If
Algorithm
,
is said to be correct if and only if it calculates the correct values of
, for all
, (as per the recursive formulation at the end of the execution of the algorithm
).Which one of the following statements is true?
Your answerChoose one option.
Log in to check the answer
You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer