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

Advanced Algorithms · End Term · 31 Aug 2025 (Afternoon)

21 questions · 50 marks · 90 min

Answer key Take as mock

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Advanced Algorithms

End Term · 31 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.
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.

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 3 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 = 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:
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.
Q8MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. ATRUE
2. BFALSE
Q9MCQ3 Marks·Choose one option
Asked 2 times Key ↓
Choose the correct options:
1. A
2. B
3. C
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. 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 Q14–Q15
Consider the given statements and answer the 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–Q18
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
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 Q19–Q20
Based on the above data, answer the given subquestions.
Q19MCQ2 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.
Q20MCQ2 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.
Q21MCQ3 Marks·Choose one option
Asked 2 times Key ↓
1. A
2. B
3. C
4. D

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

Q56

Q6540

Q7B, C, D

Q8A

Q9A

Q10C

Q11C

Q12A

Q13B

Q14B

Q15B

Q16B

Q17A

Q18A

Q19B

Q20C

Q21C

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