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

Advanced Algorithms · Most repeated questions

45 questions · 101 marks · 3 papers · 18 question types

Answer key

Indian Institute of Technology Madras

BS Degree Programme · Examination & Study Paper

Advanced Algorithms

Most repeated questions

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.

Type 1 · asked 6 times · Inclusion-exclusion counting

Count length-n sequences over {0,1,2} in which every digit appears

Read the passage below, then answer Q1–Q2
Based on the above data, answer the given subquestions.
Q1NAT2 Marks·Write the number
Quiz 2 · 3 Aug 2025 (AN)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:
Q2NAT2 Marks·Write the number
Quiz 2 · 3 Aug 2025 (AN)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:
Read the passage below, then answer Q3–Q4
Based on the above data, answer the given subquestions.
Q3NAT2 Marks·Write the number
End Term · 31 Aug 2025 (AN)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:
Q4NAT2 Marks·Write the number
End Term · 31 Aug 2025 (AN)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:
Read the passage below, then answer Q5–Q6
Based on the above data, answer the given subquestions.
Q5NAT2 Marks·Write the number
End Term · 31 Aug 2025 (FN)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
End Term · 31 Aug 2025 (FN)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:

Type 2 · asked 4 times · Linear programming & LP rounding

Effect of changing the LP rounding threshold in weighted vertex cover

Read the passage below, then answer Q7–Q8
Based on the above data, answer the given subquestions.
Q7MCQ2 Marks·Choose one option
Quiz 2 · 3 Aug 2025 (AN)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.
Q8MCQ2 Marks·Choose one option
Quiz 2 · 3 Aug 2025 (AN)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 Q9–Q10
Based on the above data, answer the given subquestions.
Q9MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)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.
Q10MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)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.

Type 3 · asked 3 times · Inclusion-exclusion counting

Inclusion-exclusion: size of each A_i (sequences missing digit i)

Read the passage below, then answer Q11
Based on the above data, answer the given subquestions.
Q11MCQ1 Mark·Choose one option
Quiz 2 · 3 Aug 2025 (AN)Key ↓
1. A
2. B
3. C
4. D
Read the passage below, then answer Q12
Based on the above data, answer the given subquestions.
Q12MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A3^n
2. B2^n
3. Cn^3
4. Dn^2
Read the passage below, then answer Q13
Based on the above data, answer the given subquestions.
Q13MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. A3^n
2. B2^n
3. Cn^3
4. Dn^2

Type 4 · asked 3 times · Inclusion-exclusion counting

Inclusion-exclusion: size of each pairwise intersection A_i ∩ A_j

Read the passage below, then answer Q14
Based on the above data, answer the given subquestions.
Q14MCQ1 Mark·Choose one option
Quiz 2 · 3 Aug 2025 (AN)Key ↓
1. A
2. B
3. C
4. D
Read the passage below, then answer Q15
Based on the above data, answer the given subquestions.
Q15MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A2^n
2. Bn
3. C1
4. D0
Read the passage below, then answer Q16
Based on the above data, answer the given subquestions.
Q16MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. A2^n
2. Bn
3. C1
4. D0

Type 5 · asked 3 times · Inclusion-exclusion counting

Inclusion-exclusion: size of the triple intersection A_0 ∩ A_1 ∩ A_2

Read the passage below, then answer Q17
Based on the above data, answer the given subquestions.
Q17MCQ1 Mark·Choose one option
Quiz 2 · 3 Aug 2025 (AN)Key ↓
1. A
2. B
3. C
4. D
Read the passage below, then answer Q18
Based on the above data, answer the given subquestions.
Q18MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A3^n
2. B2^n
3. C1
4. D0
Read the passage below, then answer Q19
Based on the above data, answer the given subquestions.
Q19MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. A3^n
2. B2^n
3. C1
4. D0

Type 6 · asked 2 times · Greedy algorithms & their pitfalls

Decide which greedy algorithm correctly tests if a tree has a perfect matching

Q20MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (AN)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.
Q21MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (FN)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.

Type 7 · asked 2 times · NP-hardness & branching algorithms

Identify the complexity class (P/NP/NP-hard) of the generalized SWISH game

Q22MSQ3 Marks·Choose all correct options
End Term · 31 Aug 2025 (AN)Key ↓
1. AIt is in P.
2. BIt is in NP.
3. CIt is NP-hard.
4. DIt is NP-complete.
Q23MSQ3 Marks·Choose all correct options
End Term · 31 Aug 2025 (FN)Key ↓
1. AIt is in P.
2. BIt is in NP.
3. CIt is NP-hard.
4. DIt is NP-complete.

Type 8 · asked 2 times · Matroids

Is a matroid with one element deleted still a matroid?

Q24MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. ATRUE
2. BFALSE
Q25MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. ATRUE
2. BFALSE

Type 9 · asked 2 times · Matroids

Check which given set systems (E, I) are matroids

Q26MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
Choose the correct options:
1. A
2. B
3. C
Q27MSQ3 Marks·Choose all correct options
End Term · 31 Aug 2025 (FN)Key ↓
Choose the correct options:
1. A
2. B
3. C

Type 10 · asked 2 times · Dynamic programming for set cover

Find the missing entry in a set cover DP table

Q28MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A0
2. B1
3. C2
4. D3
Q29MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. A0
2. B1
3. C2
4. D3

Type 11 · asked 2 times · Dynamic programming for set cover

Read values from the set cover DP table Pi(X, j)

Read the passage below, then answer Q30
Based on the above data, answer the given subquestions.
Q30MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A
2. B
3. C
4. D
Read the passage below, then answer Q31
Based on the above data, answer the given subquestions.
Q31MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. A
2. B
3. C
4. D

Type 12 · asked 2 times · Dynamic programming for set cover

Which DP table entries are looked up to compute Pi(X, j) for set cover

Read the passage below, then answer Q32
Based on the above data, answer the given subquestions.
Q32MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A
2. B
3. C
4. D
Read the passage below, then answer Q33
Based on the above data, answer the given subquestions.
Q33MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. A
2. B
3. C
4. D

Type 13 · asked 2 times · Randomized algorithms

True/false: worst-case and expected running time of randomized algorithms

Read the passage below, then answer Q34
Consider the given statements and answer the subquestions if they are true or false.
Q34MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.
1. ATRUE
2. BFALSE
Read the passage below, then answer Q35
Consider the following statements and answer the given subquestions if they are true or false.
Q35MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm.
1. ATRUE
2. BFALSE

Type 14 · asked 2 times · Randomized algorithms

Can an adversary force randomized quicksort beyond n log n time?

Read the passage below, then answer Q36
Consider the given statements and answer the subquestions if they are true or false.
Q36MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. ATRUE
2. BFALSE
Read the passage below, then answer Q37
Consider the following statements and answer the given subquestions if they are true or false.
Q37MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. ATRUE
2. BFALSE

Type 15 · asked 2 times · Linear programming & LP rounding

True/false: every linear program has a unique optimal solution

Read the passage below, then answer Q38–Q39
Answer the given subquestions.
Q38MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
Every linear program has a unique optimal solution.
1. ATRUE
2. BFALSE
Q39MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
Every linear program has a unique optimal solution.
1. ATRUE
2. BFALSE

Type 16 · asked 2 times · Greedy algorithms & their pitfalls

Does the max-degree greedy algorithm always output a vertex cover?

Read the passage below, then answer Q40–Q41
Answer the given subquestions.
Q40MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. AYes
2. BNo
Q41MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)Key ↓
1. AYes
2. BNo

Type 17 · asked 2 times · Greedy algorithms & their pitfalls

Can the minimum vertex cover be exactly twice the maximum matching?

Read the passage below, then answer Q42–Q43
Answer the given subquestions.
Q42MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (AN)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
Q43MCQ2 Marks·Choose one option
End Term · 31 Aug 2025 (FN)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

Type 18 · asked 2 times · Iterative compression & FPT

Running time of d-hitting set via iterative compression

Q44MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (AN)Key ↓
1. A
2. B
3. C
4. D
Q45MCQ3 Marks·Choose one option
End Term · 31 Aug 2025 (FN)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

Q136

Q2150

Q36

Q4540

Q536

Q6150

Q7B

Q8C

Q9B

Q10C

Q11B

Q12B

Q13B

Q14C

Q15C

Q16C

Q17D

Q18D

Q19D

Q20C

Q21C

Q22B, C, D

Q23A, B

Q24A

Q25A

Q26A

Q27A, C

Q28C

Q29C

Q30C

Q31C

Q32A

Q33D

Q34B

Q35B

Q36B

Q37B

Q38B

Q39B

Q40A

Q41A

Q42A

Q43A

Q44C

Q45D

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.