Indian Institute of Technology Madras
BS Degree Programme · Examination & Study Paper
Advanced Algorithms
NP-hardness & branching algorithms
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.
- 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
- Q1MSQ3 Marks·Choose all correct options
- AIt is in P.
- BIt is in NP.
- CIt is NP-hard.
- DIt is NP-complete.
- Q2MCQ3 Marks·Choose one option
- A
- B
- C
- D
- A
End Term · 31 Aug 2025 (AN)End Term
- Q3MSQ3 Marks·Choose all correct options
- AIt is in P.
- BIt is in NP.
- CIt is NP-hard.
- DIt is NP-complete.
- Q4MCQ3 Marks·Choose one option
- AIn both branches of the algorithm, at least one clause is falsified.
- BIn both branches of the algorithm, at least one clause is satisfied.
- CIn both branches of the algorithm, at least two clauses are falsified.
- DIn both branches of the algorithm, at least two clauses are satisfied.