BTechibtechi.in
Loading Loading
Free IIT Madras BS notes, PYQs and mock tests at btechi.in

Advanced Algorithms · Quiz 2 · 3 Aug 2025 (Afternoon)

26 questions · 50 marks · 60 min

Answer key Take as mock

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Advanced Algorithms

Quiz 2 · 3 Aug 2025 (Afternoon)

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MCQ: Exactly 1 option is correct. Negative marking applies.
NAT: Numerical response. No negative marking.
Scientific calculator allowed for all calculations.
Official answer key is sealed at the end of this sheet.

Read the passage below, then answer Q1–Q12
Q1MCQ3 Marks·Choose one option
Key ↓
A graph G is a cluster graph if and only if it does not have an induced path on 3 vertices.
1. ATRUE
2. BFALSE
Q2MCQ2 Marks·Choose one option
Key ↓
1. A
2. B
3. C
Q3MCQ2 Marks·Choose one option
Key ↓
In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on S is not a cluster graph, we can immediately return YES.
1. ATRUE
2. BFALSE
Q4MCQ2 Marks·Choose one option
Key ↓
In the DISJOINT CLUSTER VERTEX DELETION problem, if the subgraph induced on the vertices of S is not a cluster graph, we can immediately return NO.
1. ATRUE
2. BFALSE
Q5MCQ2 Marks·Choose one option
Key ↓
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to at least two vertices in S which are in different cliques, then we can delete it and leave the parameter unchanged.
1. ATRUE
2. BFALSE
Q6MCQ2 Marks·Choose one option
Key ↓
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to at least two vertices in S which are in different cliques, then we can delete it and decrease the parameter by 1.
1. ATRUE
2. BFALSE
Q7MCQ2 Marks·Choose one option
Key ↓
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to some but not all vertices in a clique of G[S], then we can delete it and leave the parameter unchanged.
1. ATRUE
2. BFALSE
Q8MCQ2 Marks·Choose one option
Key ↓
If the subgraph induced on the vertices of S is a cluster graph and a vertex in V (G) \ S is adjacent to some but not all vertices in a clique of G[S], then we can delete it and decrease the parameter by 1.
1. ATRUE
2. BFALSE
Q9MCQ2 Marks·Choose one option
Key ↓
After modifying the input instance, we can solve DISJOINT CLUSTER VERTEX DELETION by solving a matching problem on a bipartite graph.
1. ATRUE
2. BFALSE
Q10MCQ2 Marks·Choose one option
Key ↓
DISJOINT CLUSTER VERTEX DELETION is polynomial time solvable.
1. ATRUE
2. BFALSE
Q11MCQ2 Marks·Choose one option
Key ↓
DISJOINT CLUSTER VERTEX DELETION is NP-hard.
1. ATRUE
2. BFALSE
Q12MCQ2 Marks·Choose one option
Key ↓
1. ATRUE
2. BFALSE
Read the passage below, then answer Q13–Q14
Based on the above data, answer the given subquestions.
Q13MCQ2 Marks·Choose one option
Asked 4 times Key ↓
1. AWe still get a valid solution, and the algorithm remains a 2-approximation.
2. BWe still get a valid solution, and the algorithm becomes a 3-approximation.
3. CWe may no longer get a valid solution.
Q14MCQ2 Marks·Choose one option
Asked 4 times Key ↓
1. AWe still get a valid solution, and the algorithm remains a 2-approximation.
2. BWe still get a valid solution, and the algorithm becomes a (3/2)-approximation.
3. CWe may no longer get a valid solution.
Read the passage below, then answer Q15–Q21
In Figure 1, we have a graph G and an FVS of size 3 which is given by the box, i.e., S ∶= {a,c,e}. We need to find a DISJOINT FVS of size 2.
For each of the given statements in the subquestions, determine if it is true or false.
Q15MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 2 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q16MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 3 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q17MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 4 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q18MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 5 shows a valid intermediate instance in the reduction with k= 2.
1. ATRUE
2. BFALSE
Q19MCQ2 Marks·Choose one option
Key ↓
According to the reduction rules for DFVS, Figure 4 shows a valid intermediate instance in the reduction with k= 1.
1. ATRUE
2. BFALSE
Q20MCQ2 Marks·Choose one option
Key ↓
The graph in Figure 1 has a FVS disjoint from S of size 2.
1. ATRUE
2. BFALSE
Q21MCQ2 Marks·Choose one option
Key ↓
The graph in Figure 1 has a FVS disjoint from S of size 1.
1. ATRUE
2. BFALSE
Read the passage below, then answer Q22–Q26
Based on the above data, answer the given subquestions.
Q22MCQ1 Mark·Choose one option
Asked 3 times Key ↓
1. A
2. B
3. C
4. D
Q23MCQ1 Mark·Choose one option
Asked 3 times Key ↓
1. A
2. B
3. C
4. D
Q24MCQ1 Mark·Choose one option
Asked 3 times Key ↓
1. A
2. B
3. C
4. D
Q25NAT2 Marks·Write the number
Asked 6 times Key ↓
For n= 4, calculate the number of sequences of length 4 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.
Your answer:
Q26NAT2 Marks·Write the number
Asked 6 times Key ↓
For n = 5, calculate the number of sequences of length 5 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.
Your answer:

Official Key

Master Answer Key & Explanations

Official answer keys from IIT Madras BS past papers. Click any question to review.

Reveal Key

Q1A

Q2A

Q3B

Q4A

Q5B

Q6A

Q7B

Q8A

Q9A

Q10A

Q11B

Q12A

Q13B

Q14C

Q15B

Q16A

Q17B

Q18A

Q19B

Q20A

Q21A

Q22B

Q23C

Q24D

Q2536

Q26150

Questions and answer keys are reproduced from the official IIT Madras BS papers. BTechi is not affiliated with IIT Madras.