Class test 2 marking scheme


Question 1:
  1. True.
  2. False.
  3. False.

Correct answer: 1 mark each, explanation: 1 mark each
Question 2:
  1. Correct algo: 2 marks, Analysis: 2 marks
  2. Two conditions: t is in unary or t=poly(n) 1 mark each
Question 3:
  1. Correct decicion version: 1 mark
  2. Containment in NP: 1 mark, reduction: 2 marks
  3. No. 1 mark, correct reasoning: 1 mark
Question 4: Algorithm: 2 marks, Analysis: 2 marks

Question 5:
  1. No: 1 mark, counter-example: 1 mark
  2. No: 1 mark, counter-example: 1 mark
  3. False, True: 1 mark each, explanation: 1 mark each