Advanced Algorithms Quiz 2: 1 December 2024 (September 2024 term)

Based on the above data answer the given subquestions.

Based on the above data answer the given subquestions.

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

$\{a_1, T - a_1, a_2, T - a_2, \ldots, a_n, T - a_n\},$

i.e, the reduced instance consists of the first $n$ numbers of the original problem, and $n$ new numbers formed by taking the difference between each of the input numbers and the common sum $T$. This reduction:

Based on the above data answer the given subquestions.

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

$\{a_1, a_2, \ldots, a_{2n}\},$

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