Programming Assignment 7 - Additive Up-Sequences

See the assignment turn-in page (last modified on 4 March 2002) for instructions on turning in your assignment.

1. n > 1; that is, the sequence contains more than one integer.

2. i₀ = 1; that is, the sequence starts at 1.

3. i_{j - 1} < i_j for any 1 <= j < n; that is, the sequence is sorted in strictly increasing order.

4. for any 1 <= j < n there exists 0 <= k, l < i such that i_j = i_k + i_l; that is, any integer in the sequence except the first is the sum of two not necessarily distinct integers appearing earlier in the sequence.

For example,

1, 2, 4

is an additive up-sequence but

1, 3, 4

is not because 3 is not the sum of two integers appearing previously in the sequence.

std::vector<unsigned> mau(unsigned n);

that accepts an unsigned integer n and returns a minimal additive up-sequence in which the last number in the sequence is n. If no minimal additive up-sequence exists for the given value of n, mau() should return the empty vector.

An additive up-sequence s is minimal if any other additive up-sequence that ends in the same integer as does s has at least as many integers as does s. If more than one minimal additive up-sequence exists, mau() may return any one of them. You can test your procedure by compiling it with the file

where os is either linux, solaris, or stlport-solaris. Running the resulting executable calls your routine with a randomly generated value for n and compares the result returned with the result returned by my solution to the problem. If you get no output, then everything's fine; otherwise you'll get an error message indicating a problem.

The -s command-line option takes an integer argument and uses it as the seed for the random-number generator. You can run your code repeatedly on the same set of randomly-generated data by passing in the same value with -s on each execution. The default is to generate a different randomly-generated values of n with each execution.

The source file for main() will not be made available because it contains my answer to the problem.

If you use stlport-solaris-main.o, make sure you compile and link everything with STLPort files; otherwise you'll get link errors.

To be correct, your solution must be efficient; that is, you solution should take no more than twice the execution time my solution takes on the same input. The test executable keeps track of execution times. The -t command-line option prints the execution time taken by your version of mau().