Indian Institute of Technology Madras
BS Degree Programme · Examination & Study Paper
Programming, Data Structures and Algorithms using Python
Intractability & NP-completeness
Official Paper
Examination Instructions & Guidelines
- Solve on notebook/paper first before checking solutions.
- MCQ: Exactly 1 option is correct. Negative marking applies.
- 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
- Q1MCQ4 Marks·Choose one option
- A
- B
- C
- D
- A
End Term · 31 Aug 2025 (AN)End Term
- Q2MCQ4 Marks·Choose one option
- AOnly statement 1 is correct
- BOnly statement 2 is correct
- CBoth the statements are correct
- DBoth the statements are wrong
End Term · 13 Apr 2025 (AN)End Term
- Q3NAT4 Marks·Write the number
Your answer:
End Term · 22 Dec 2024 (FN)End Term
- Q4MCQ4 Marks·Choose one option
Consider the following statements. 1. If an NP-hard problem A is polynomial time reducible to another problem B, then B belongs to the NP class. 2. There exists polynomial time checking algorithm for all problems in the class P. Which of the following option is correct?
- AOnly statement 1 is true
- BOnly statement 2 is true
- CBoth statements 1 and 2 are true
- DBoth statements 1 and 2 are false
End Term · 22 Dec 2024 (AN)End Term
- Q5MCQ4 Marks·Choose one option
Consider the following statements. 1. If an NP-hard problem A is polynomial time reducible to another problem B, then B belongs to the class NP. 2. If an NP-hard problem A is polynomial time reducible to another problem B, then B is NP- complete. Which of the following option is correct?
- AOnly statement 1 is true
- BOnly statement 2 is true
- CBoth statements 1 and 2 are true
- DBoth statements 1 and 2 are false