Question

A sequence numbers w1; w2; ; wn is said to be superincreasing if Pi1 j=1 wj < wi for 1 < i n.

(a) Show that the problem SUBSET-SUM restricted on superincreasing sequence is solvable in linear time.

Answer 1

The SUBSET-SUM problem, when applied to a superincreasing sequence, can be solved in linear time because the sum of any subset of terms is unique and less than the next term in the sequence. This allows for a simple linear algorithm that iteratively reduces the target sum by the largest term less than it, ensuring an efficient solution.

Step-by-step explanation:

Given a sequence of numbers w1, w2, ..., wn which is superincreasing, the condition for this sequence is that for each i, the sum of all previous terms is less than the current term. That is, the sum of the sequence up to the (i-1)th term is less than the ith term, for all i where 2 ≤ i ≤ n. This property is invaluable when considering the SUBSET-SUM problem, which involves finding a subset of numbers that add up to a given target sum.

To show that the problem can be solved in linear time for a superincreasing sequence, consider the following algorithm:

1. Start from the largest term in the sequence (wn) and compare it to the target sum.
2. If the term is less than or equal to the target sum, subtract it from the target sum and proceed to the next smallest term.
3. If the term is greater than the target sum, simply move to the next smallest term.
4. Repeat the process until either the target sum is reduced to 0 (a subset is found), or all terms have been considered (no subset can sum up to the target).

Since each term is only considered once and the comparison/subtraction operations are constant time, the entire process is linear with respect to the number of terms in the sequence.