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

Advanced Algorithms · All 2025 papers

68 questions · 150 marks · 3 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Advanced Algorithms

All 2025 papers

Official Paper

Examination Instructions & Guidelines

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

End Term · 31 Aug 2025 (FN)End Term

Q1MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. ANeither algorithm always correctly determines whether or not a given tree graph has a perfect matching.
2. BBoth algorithms always correctly determine whether or not a given tree graph has a perfect matching.
3. CAlgorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.
4. DAlgorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.
Read the passage below, then answer Q2–Q6
Based on the above data, answer the given subquestions.
Q2MCQ2 Marks·Choose one option
Asked 3 times Key ↓
1. A3^n
2. B2^n
3. Cn^3
4. Dn^2
Q3MCQ2 Marks·Choose one option
Asked 3 times Key ↓
1. A2^n
2. Bn
3. C1
4. D0
Q4MCQ2 Marks·Choose one option
Asked 3 times Key ↓
1. A3^n
2. B2^n
3. C1
4. D0
Q5NAT2 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:
Q6NAT2 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:
Q7MSQ3 Marks·Choose all correct options
Asked 2 times Key ↓
1. AIt is in P.
2. BIt is in NP.
3. CIt is NP-hard.
4. DIt is NP-complete.
Q8MSQ3 Marks·Choose all correct options
Asked 2 times Key ↓
Choose the correct options:
1. A
2. B
3. C
Q9MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. ATRUE
2. BFALSE
Q10MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A0
2. B1
3. C2
4. D3
Read the passage below, then answer Q11–Q12
Based on the above data, answer the given subquestions.
Q11MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q12MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q13MCQ3 Marks·Choose one option
Key ↓
1. A
2. B
3. C
4. D
Read the passage below, then answer Q14–Q15
Consider the following statements and answer the given subquestions if they are true or false.
Q14MCQ2 Marks·Choose one option
Asked 2 times Key ↓
The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.
1. ATRUE
2. BFALSE
Q15MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. ATRUE
2. BFALSE
Read the passage below, then answer Q16–Q20
Answer the given subquestions.
Q16MCQ2 Marks·Choose one option
Asked 2 times Key ↓
Every linear program has a unique optimal solution.
1. ATRUE
2. BFALSE
Q17MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. AYes
2. BNo
Q18MCQ2 Marks·Choose one option
Key ↓
Consider the algorithm in the previous question no 18. Does the algorithm always output an optimal vertex cover?
1. AYes
2. BNo
Q19MCQ2 Marks·Choose one option
Key ↓
Consider the algorithm in the previous question no 18. Does the algorithm always output a 2- approximate vertex cover?
1. AYes
2. BNo
Q20MCQ2 Marks·Choose one option
Asked 2 times Key ↓
Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there examples of graphs where the size of the optimal vertex cover is exactly equal to twice the size of its maximum matching? For example, this is not true for a path on three vertices: the size of both the maximum matching and minimum vertex cover is 1.
1. AYes
2. BNo
Q21MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D

End Term · 31 Aug 2025 (AN)End Term

Q22MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. ANeither algorithm always correctly determines whether or not a given tree graph has a perfect matching.
2. BBoth algorithms always correctly determine whether or not a given tree graph has a perfect matching.
3. CAlgorithm B always correctly determines whether or not a given tree graph has a perfect matching; algorithm A does not.
4. DAlgorithm A always correctly determines whether or not a given tree graph has a perfect matching; algorithm B does not.
Read the passage below, then answer Q23–Q27
Based on the above data, answer the given subquestions.
Q23MCQ2 Marks·Choose one option
Asked 3 times Key ↓
1. A3^n
2. B2^n
3. Cn^3
4. Dn^2
Q24MCQ2 Marks·Choose one option
Asked 3 times Key ↓
1. A2^n
2. Bn
3. C1
4. D0
Q25MCQ2 Marks·Choose one option
Asked 3 times Key ↓
1. A3^n
2. B2^n
3. C1
4. D0
Q26NAT2 Marks·Write the number
Asked 6 times Key ↓
For n = 4, calculate the number of sequences of length 3 consisting only of numbers 0, 1, and 2 such that each number occurs at least once.
Your answer:
Q27NAT2 Marks·Write the number
Asked 6 times Key ↓
For n = 6, 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:
Q28MSQ3 Marks·Choose all correct options
Asked 2 times Key ↓
1. AIt is in P.
2. BIt is in NP.
3. CIt is NP-hard.
4. DIt is NP-complete.
Q29MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. ATRUE
2. BFALSE
Q30MCQ3 Marks·Choose one option
Asked 2 times Key ↓
Choose the correct options:
1. A
2. B
3. C
Q31MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A0
2. B1
3. C2
4. D3
Read the passage below, then answer Q32–Q33
Based on the above data, answer the given subquestions.
Q32MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q33MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D
Q34MCQ3 Marks·Choose one option
Key ↓
1. AIn both branches of the algorithm, at least one clause is falsified.
2. BIn both branches of the algorithm, at least one clause is satisfied.
3. CIn both branches of the algorithm, at least two clauses are falsified.
4. DIn both branches of the algorithm, at least two clauses are satisfied.
Read the passage below, then answer Q35–Q36
Consider the given statements and answer the subquestions if they are true or false.
Q35MCQ2 Marks·Choose one option
Asked 2 times Key ↓
The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.
1. ATRUE
2. BFALSE
Q36MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. ATRUE
2. BFALSE
Read the passage below, then answer Q37–Q39
Answer the given subquestions.
Q37MCQ2 Marks·Choose one option
Asked 2 times Key ↓
Every linear program has a unique optimal solution.
1. ATRUE
2. BFALSE
Q38MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. AYes
2. BNo
Q39MCQ2 Marks·Choose one option
Asked 2 times Key ↓
Recall that the size of an optimal vertex cover is at most twice the size of a maximum matching of a graph G. Are there examples of graphs where the size of the optimal vertex cover is exactly equal to twice the size of its maximum matching? For example, this is not true for a path on three vertices: the size of both the maximum matching and minimum vertex cover is 1
1. AYes
2. BNo
Read the passage below, then answer Q40–Q41
Based on the above data, answer the given subquestions.
Q40MCQ2 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.
Q41MCQ2 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.
Q42MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D

Quiz 2 · 3 Aug 2025 (AN)Quiz 2

Read the passage below, then answer Q43–Q54
Q43MCQ3 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
Q44MCQ2 Marks·Choose one option
Key ↓
1. A
2. B
3. C
Q45MCQ2 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
Q46MCQ2 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
Q47MCQ2 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
Q48MCQ2 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
Q49MCQ2 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
Q50MCQ2 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
Q51MCQ2 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
Q52MCQ2 Marks·Choose one option
Key ↓
DISJOINT CLUSTER VERTEX DELETION is polynomial time solvable.
1. ATRUE
2. BFALSE
Q53MCQ2 Marks·Choose one option
Key ↓
DISJOINT CLUSTER VERTEX DELETION is NP-hard.
1. ATRUE
2. BFALSE
Q54MCQ2 Marks·Choose one option
Key ↓
1. ATRUE
2. BFALSE
Read the passage below, then answer Q55–Q56
Based on the above data, answer the given subquestions.
Q55MCQ2 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.
Q56MCQ2 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 Q57–Q63
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.
Q57MCQ2 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
Q58MCQ2 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
Q59MCQ2 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
Q60MCQ2 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
Q61MCQ2 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
Q62MCQ2 Marks·Choose one option
Key ↓
The graph in Figure 1 has a FVS disjoint from S of size 2.
1. ATRUE
2. BFALSE
Q63MCQ2 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 Q64–Q68
Based on the above data, answer the given subquestions.
Q64MCQ1 Mark·Choose one option
Asked 3 times Key ↓
1. A
2. B
3. C
4. D
Q65MCQ1 Mark·Choose one option
Asked 3 times Key ↓
1. A
2. B
3. C
4. D
Q66MCQ1 Mark·Choose one option
Asked 3 times Key ↓
1. A
2. B
3. C
4. D
Q67NAT2 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:
Q68NAT2 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

Q1C

Q2B

Q3C

Q4D

Q536

Q6150

Q7A, B

Q8A, C

Q9A

Q10C

Q11C

Q12D

Q13C

Q14B

Q15B

Q16B

Q17A

Q18B

Q19B

Q20A

Q21D

Q22C

Q23B

Q24C

Q25D

Q266

Q27540

Q28B, C, D

Q29A

Q30A

Q31C

Q32C

Q33A

Q34B

Q35B

Q36B

Q37B

Q38A

Q39A

Q40B

Q41C

Q42C

Q43A

Q44A

Q45B

Q46A

Q47B

Q48A

Q49B

Q50A

Q51A

Q52A

Q53B

Q54A

Q55B

Q56C

Q57B

Q58A

Q59B

Q60A

Q61B

Q62A

Q63A

Q64B

Q65C

Q66D

Q6736

Q68150

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