The IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 15 Mar 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.
At each iteration, pick the remaining request with the fewest number of conflicts with other remaining requests (breaking ties arbitrarily).
At each iteration, pick the remaining request with the earliest start time.
At each iteration, pick the remaining request with the earliest finish time.
Correct answer
At each iteration, pick the remaining request with the earliest finish time.
Only Statement 1 is true
Only Statement 2 is true
Both Statement 1 and Statement 2 are true
Neither Statement 1 nor Statement 2 is true
Correct answer
Neither Statement 1 nor Statement 2 is true
Correct answer
A popular conference is being held, and there are several types of seats: VIP, Regular, and Economy. Each type of seat has a limited number of available spots. Each attendee has a preference for the type of seat they want, and the total number of attendees is greater than the number of available seats. The goal is to allocate the seats to attendees such that each attendee is assigned to their preferred seat type, and no seat type exceeds its capacity.
How can the given problem of allocating seats to attendees based on their preferences and seat type capacities be effectively solved?
Using a greedy algorithm to assign seats based on attendee preferences.
Modeling the problem as a maximum flow network with capacities representing seat limits and flows representing the number of attendees assigned to each seat type.
Implementing a first-come, first-serve approach without considering the preferences or seat type capacities.
Assigning all attendees to the VIP seats first and distributing the remaining attendees among Regular and Economy seats.
Correct answer
Modeling the problem as a maximum flow network with capacities representing seat limits and flows representing the number of attendees assigned to each seat type.
Let A be a decision problem. Suppose:
• A is in NP • A is NP-hard
Which of the following must be true?
A is in P
A is NP-complete
A is not solvable in polynomial time
P = NP
Correct answer
A is NP-complete
True
False
Correct answer
True
True
False
Correct answer
False
Consider the following greedy approach to find the Longest Increasing Subsequence (LIS):
Select the first element of the list. Then repeatedly select the next element that is strictly larger than the last selected element.
On which of the following inputs does this greedy algorithm give an incorrect answer?
[1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
[20, 18, 16, 14, 12, 10, 8, 6, 4, 2]
[15, 1, 2, 3, 4, 5, 6, 7, 8, 16]
[2, 9, 3, 6, 5, 1, 7, 8, 4, 10]
Correct answers
[15, 1, 2, 3, 4, 5, 6, 7, 8, 16]
[2, 9, 3, 6, 5, 1, 7, 8, 4, 10]
Which of the following expressions should replace the blank( ___ ) so that the algorithm correctly computes the LIS length?
Correct answer
Correct answers
There is a polynomial-time reduction from BoxDepth to MaxClique.
There is a polynomial-time algorithm for BoxDepth.
BoxDepth can be solved in polynomial time by sweeping a vertical line and maintaining the maximum number of overlapping rectangles at any point.
Correct answers
There is a polynomial-time reduction from BoxDepth to MaxClique.
There is a polynomial-time algorithm for BoxDepth.
BoxDepth can be solved in polynomial time by sweeping a vertical line and maintaining the maximum number of overlapping rectangles at any point.
Which of the following expressions should replace the blank( ___ ) so that the algorithm correctly computes the maximum sum subarray?
Correct answer
A university wants to cover all departments {1,2,3,4,5,6,7,8,9} using the minimum number of workshops. Each workshop can train certain departments.
Workshops and coverage:
• W1: {1, 2, 3, 4} • W2: {3, 5, 6} • W3: {2, 7, 8} • W4: {4, 6, 9} • W5: {1, 5, 8}
What is the minimum number of workshops required to cover all departments?
Correct answer: 4
Consider the following tree:
What is the size of the maximum independent set of this tree?
Correct answer: 4
Let G be a bipartite graph with:
• Total number of vertices = 20 • Size of maximum matching = 8
What is the size of the maximum independent set in G?
Correct answer: 12
The value of the maximum flow in the given network is______ .
Correct answer: 14
