The IIT Madras BS Programming, Data Structures and Algorithms using Python (PDSA) Quiz 2 paper sat on 12 Apr 2026, in the January 2026 term: 16 questions for 50 marks in 120 minutes. Every question is below with its answer. Take it as a timed mock test to be marked, or read it through first.
Which of the following statements is/are correct about Dijkstra's algorithm to find the shortest path? I. The shortest path returned by Dijkstra's algorithm always passes through the least number of vertices. II. To decide which vertex to visit next, Dijkstra's algorithm selects the vertex with the minimum known distance among all unvisited vertices.
Only I is correct
Only II is correct
Both I and II are correct
Both I and II are incorrect
Correct answer
Only II is correct
The Bellman–Ford algorithm can be used to detect the presence of a negative-weight cycle reachable from the source vertex in a weighted directed graph. Which of the following correctly explains how Bellman–Ford detects a negative-weight cycle?
A negative-weight cycle exists if the shortest distance to any vertex becomes negative at any point during the algorithm.
If, after performing exactly relaxation iterations, an additional relaxation of any edge further reduces a distance value, then a negative-weight cycle is present.
If the algorithm encounters an edge with a negative weight during relaxation, it immediately concludes that a negative-weight cycle exists.
If multiple shortest paths exist between two vertices, the graph must contain a negative-weight cycle.
Correct answer
If, after performing exactly relaxation iterations, an additional relaxation of any edge further reduces a distance value, then a negative-weight cycle is present.
Which of the following correctly represents the final max-heap after inserting elements 1, 2, 3, 5, 7, 6, and 4 in the given order one by one, starting with an empty heap? Note:- Ensure that the max-heap property is maintained after each insertion.
—
—
—
—
Correct answer
—
The maximum and minimum number of nodes possible in a binary search tree of height 8 are ___. Assume that the height of an empty tree is 0, and the height of a tree with a single node is 1.
255 and 8, respectively
256 and 7, respectively
127 and 8, respectively
255 and 7, respectively
Correct answer
255 and 8, respectively
Consider a Binary Search Tree (BST) containing distinct keys. Each node of the BST is defined using the following class:
The following recursive functions are applied by calling , where points to the root of the BST. Which of the following implementations will print the keys of the BST in strictly decreasing order?
Correct answer
Suppose the letters {a, b, c, d, e} occur with the following frequencies.
How many bits will be used to encode the letter b in the Huffman code for this alphabet?
1
2
3
4
Correct answer
2
Consider a set of activities , where each activity has: • a processing time (time required to complete the activity), and • a deadline . Only one activity can be executed at a time. If an activity finishes at time , the next activity can start at time itself. Assume that the initial start time is 0. The lateness of an activity is defined as:
where denotes the finish time of activity . Let denote the maximum lateness among all activities: The objective is to schedule the activities in an order that minimizes . Which of the following greedy strategies will always produce an optimal schedule for minimizing the maximum lateness ?
Always schedule first the activity with the minimum processing time.
Always schedule first the activity with the earliest deadline.
Always schedule first the activity with the minimum value of .
Always schedule first the activity with the maximum processing time.
Correct answer
Always schedule first the activity with the earliest deadline.
In a list , two elements and form a significant inversion if The total number of significant inversions for is ___.
3
4
5
6
Correct answer
5
Consider the Quick Select algorithm for finding the smallest element in an input list of size containing distinct elements. The algorithm uses the Median of Medians (MoM) technique to select the pivot element. Which of the following is the correct recurrence relation representing the worst-case running time of this Quick Select algorithm?
—
—
—
—
Correct answer
—
Consider the following strategy to solve a problem of input size . Divide the problem into sub-problems, each of size , where the time required to perform this division is proportional to the input size (i.e., ). The number of steps required to combine these 6 solutions is . We apply this strategy recursively till the sub-problems can not be further divided into sub-problems. What will be the nearest upper bound for the above algorithm?
—
—
—
—
Correct answer
—
Let be a connected complete graph with 4 vertices and 6 edges, where all edge weights are distinct and ordered as: Which of the following sets of edges can be in a minimum cost spanning tree of ? (Select all that apply.)
—
—
—
—
—
Correct answers
—
—
Consider a min-heap implemented using an array with distinct elements. Which of the following statements about the time complexity of operations on a min-heap is/are true in the worst case?
Inserting a new element into a min-heap can be performed in time.
Finding the second minimum element in a min-heap can be performed in time.
Finding the maximum element in a min-heap can be performed in time.
Deleting the minimum element from a min-heap can be performed in time.
Correct answers
Inserting a new element into a min-heap can be performed in time.
Finding the second minimum element in a min-heap can be performed in time.
Consider the given weighted adjacency matrix for a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Where in the matrix is the weight of the edge .
What is the total weight of the minimum spanning tree(MST) for the given graph?
A written answer, not marked automatically.
In the table below, we have 9 activities with the corresponding start and finish times. It might not be possible to complete all the activities since their time frames can conflict. For example, if any activity starts at time 0 and finishes at time 4, then other activities can not begin before 4. It can be started at 4 or later. What is the maximum number of activities which can be performed without conflict?
A written answer, not marked automatically.
An AVL tree contains 120 nodes. What is the maximum possible height of the AVL tree? Assume that the height of an empty AVL tree is 0 and the height of an AVL tree with a single node is 1
A written answer, not marked automatically.
Consider the following function
What median value will be returned by the given function for the following list?
A written answer, not marked automatically.
