Quiz Space

Advanced Algorithms · Quiz 2 · 1 Dec 2024 · September 2024 term

Question 3: Consider the following reduction from 3-PARTITION to 2-PA…

Question 3

+2 marksOne correct option

Based on the above data answer the given subquestions.

Consider the following reduction from 3-PARTITION to 2-PARTITION: let {a1,…,a3n}\{a_1, \ldots, a_{3n}\} be the instance of 3-PARTITION where ∑i−13nai=nT\sum_{i-1}^{3n} a_i = nT. Now consider the instance of 2-PARTITION made of the numbers:

{a1,a2,…,a2n},\{a_1, a_2, \ldots, a_{2n}\},

i.e, the reduced instance simply consists of the first 2n2n numbers of the 3-PARTITION instance. This reduction:

  1. A
  2. B
  3. C
  4. D
Show answer

Correct answer

  • B
See the whole paperTake it as a mock test

Question 3 of 26 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 2 paper sat on 1 Dec 2024, in the September 2024 term (IIT M DEGREE AN EXAM QDB2 01 Dec 2024). It carries 2 marks.

More questions from this paper

  1. Q1Based on the above data answer the given subquestions.
  2. Q2Consider the following reduction from 3-PARTITION to 2-PARTITION: let {a_1, \ldots, a_{3n}} be the instance of 3-PARTIT…
  3. Q4Based on the above data answer the given subquestions.
  4. Q5We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  5. Q6We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  6. Q7We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  7. Q8We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  8. Q9We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  9. Q10We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  10. Q11We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  11. Q12We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  12. Q13We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  13. Q14We are given a list of students and classes they are requesting. Each class has a capacity and each student must sign u…
  14. Q15Based on the above data answer the given subquestions.
  15. Q16Observe that for a given \pi, the length of the corresponding superstring s(\pi), which is obtained by writing the inpu…
  16. Q17We define an overlap graph OG(\mathcal{S}) associated with \mathcal{S} as follows: OG(\mathcal{S}) is a complete direct…
  17. Q18Based on the above data answer the given subquestions.
  18. Q19Figure question
  19. Q20Figure question
  20. Q21Figure question
  21. Q22Figure question
  22. Q23Figure question
  23. Q24Figure question
  24. Q25Figure question
  25. Q26Figure question