Figure from the original question paper

(A) Finding a Hamiltonian cycle in a graph is as hard as determining the answer to the Marbles Elimination question; i.e, there is a reduction from the problem of Marbles Elimination to the problem of finding a Hamiltonian cycle.

(B) Determining the answer to the Marbles Elimination question is as hard as finding a Hamiltonian cycle in a graph; i.e, there is a reduction from the Hamiltonian cycle problem to the problem of Marbles Elimination.

(C) Marbles Elimination is in P by a reduction to the Max Flow problem.

Advanced Algorithms Quiz 2: 4 August 2024 (May 2024 term)

Question 1

+2 marksOne correct option

Based on the above data, answer the given subquestions.

Consider the following graph. A triangle-free subset of seven vertices is highlighted. Find the size of the largest triangle-free subset of vertices in this graph.

A
7
B
8
C
9
D
10

Question 2

+3 marksOne or more correct options

Based on the above data, answer the given subquestions.

The TRIANGLE-FREEDOM problem is the following: the input is a simple undirected graph G and a positive integer k. An instance (G, k) is a YES-instance if and only if G has a subset S of at least k vertices that are triangle-free.
What can you say about TRIANGLE-FREEDOM? Check all that apply.

Select all that apply.

A
It is in P.
B
It is in NP.
C
It is NP-hard.
D
It is NP-complete.

Question 3

+3 marksOne correct option

A
Finding a Hamiltonian cycle in a graph is as hard as determining the answer to the Marbles Elimination question; i.e, there is a reduction from the problem of Marbles Elimination to the problem of finding a Hamiltonian cycle.
B
Determining the answer to the Marbles Elimination question is as hard as finding a Hamiltonian cycle in a graph; i.e, there is a reduction from the Hamiltonian cycle problem to the problem of Marbles Elimination.
C
Marbles Elimination is in P by a reduction to the Max Flow problem.

18 more questions in this paper

Sign in with Google — it is free — to see every question with its answer and explanation, practise it in learning mode, or take it as a timed mock test.

More on the Advanced Algorithms Quiz 2 4 Aug 2024 paper

The IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 4 Aug 2024, in the May 2024 term: 21 questions for 50 marks in 120 minutes. The first 3 questions are below. Sign in with Google — it is free — to see the whole paper with its answers and explanations, in learning mode or as a timed mock test.

Feature	Advanced Algorithms Quiz 2 4 Aug 2024 at a glance
Term	May 2024 term
Subject	Advanced Algorithms
Course code	BSCS4021
Questions	21
Marks	50
Duration	120 min
MCQ	19
MSQ	2
Official paper	IIT M DEGREE AN EXAM QDB2 4 Aug 2024
Negative marking	No negative marking.
Updated	29 Sept 2026