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

Advanced Algorithms · Greedy algorithms & their pitfalls

8 questions · 18 marks · 2 papers

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Advanced Algorithms

Greedy algorithms & their pitfalls

Official Paper

Examination Instructions & Guidelines

Solve on notebook/paper first before checking solutions.
MCQ: Exactly 1 option is correct. Negative marking applies.
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–Q5
Answer the given subquestions.
Q2MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. AYes
2. BNo
Q3MCQ2 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
Q4MCQ2 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
Q5MCQ2 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

End Term · 31 Aug 2025 (AN)End Term

Q6MCQ3 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 Q7–Q8
Answer the given subquestions.
Q7MCQ2 Marks·Choose one option
Asked 2 times Key ↓
1. AYes
2. BNo
Q8MCQ2 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

Official Key

Master Answer Key & Explanations

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

Reveal Key

Q1C

Q2A

Q3B

Q4B

Q5A

Q6C

Q7A

Q8A

Questions and answer keys are reproduced from the official IIT Madras BS papers. Topics and repeated question types are BTechi’s own grouping. BTechi is not affiliated with IIT Madras.