Class test 2 marking scheme
Question 1:
- True.
- False.
- False.
Correct answer: 1 mark each, explanation: 1 mark each
Question 2:
- Correct algo: 2 marks, Analysis: 2 marks
- Two conditions: t is in unary or t=poly(n) 1 mark each
Question 3:
- Correct decicion version: 1 mark
- Containment in NP: 1 mark, reduction: 2 marks
- No. 1 mark, correct reasoning: 1 mark
Question 4: Algorithm: 2 marks, Analysis: 2 marks
Question 5:
- No: 1 mark, counter-example: 1 mark
- No: 1 mark, counter-example: 1 mark
- False, True: 1 mark each, explanation: 1 mark each