Note: this assignment contains both a *written* part and a *
programming* part. Written answers should be in a
file `written.txt` and your program should be
in a file `invest.c`. Your file `written.txt` should contain
answers to the two tasks given in **this font** below. The written
portion is worth 20 points and the programming portion is worth 80 points.

If it were the case that you could buy and sell without paying any
commission, then this task would be easy. You simply look up which of
these investments did best on week 1, and say that all of your money
should have been there on week 1. Then you look up which investment
did best on week 2, and say that you should have moved all your
money there for week 2. Then you look up which did best on week
3, and so forth. Unfortunately, you have to pay a commission every
time you move money around. [Even a big company like
Funds-R-Us has to pay the ``specialists'' that determine a slight
difference between buy and sell prices of a given stock.] So, the
situation is a little more tricky. For instance, suppose on week 1
that investment A did well and investment B was mediocre, and then on week
2 investment A was mediocre and investment B was better, but only
slightly better than A. In that case, you would probably have been
best off with A on both weeks because you would have had to pay a fee
to move your money. But, now suppose weeks 3, 4, and 5 were all
like week 2. In that case, you *should* have moved your money
right after week 1, because the advantage of B over A on weeks 3,
4, and 5 was enough to pay for the cost of moving the money.

A simplifying assumption we will make is that all commission charges are in percentages. For instance, investment A might have a 1% charge to buy and a 1% charge to sell: so if you purchase investment A, then A doubles in value, and then you sell all your shares, your money will have gone up by a factor of 0.99 x 2.0 x 0.99 = 1.96.

There's one more important aspect to note about this kind of problem.
A standard piece of advice for investing when you *don't* know the
future is to diversify: to spread your money around to hedge against
risk. However, in the problem that we are looking at, there is always
an optimal strategy that at every point in time has all its money in
one place. For instance, it
might say: ``you should have started with all your money in investment
A, and then after week 1 moved all your money to investment B, and
then after week 5, moved it all back to investment A.'' It won't say
``in week 2 put half of your money in A and half of it in B.'' **Think
about why there is always an optimal strategy of this form, and give a
short (1 paragraph)
explanation. It's OK to talk to other people about this one, but
write down your answer in your own words.** This fact will allow us
to solve the problem by using Dynamic Programming.

4 5 0.0 0.0 0.01 0.01 0.05 0.0 0.0 0.03 1.0 1.07 1.04 1.01 1.0 0.95 1.02 1.01 1.0 1.02 1.00 1.04 1.0 0.99 0.99 1.01 1.0 0.0 0.0 0.0

Finally, there is the market data. In this example, in week 1 the first investment didn't change in value, the second investment went up by 7% (so your money gets multiplied by 1.07), the third investment went up by 4%, and the fourth investment went up by 1%. In week 2, the first investment didn't change in value, the second went down by 5%, the third up by 2%, and the fourth up by 1%. Notice that on the last day, all values are 0 except for the first investment: this is just to force you to ``cash out'' at the end. (E.g., at the end of the game we want to sell any holdings and count our money.) You may assume (it will save you a few lines of code) that the last line of the input file looks like this.

In this example, the optimal strategy turns out to be the following. Begin by buying the second investment (paying a 1% commission), then after week 1, sell it (paying another 1%) and buy the fourth investment (paying 0%). Keep the fourth investment throughout weeks 2,3,4, finally selling it at the end (paying a 3% commission). This causes the value of one's portfolio to increase by a factor of

0.99 x 1.07 x 0.99 x 1.01 x 1.04 x 1.01 x 0.97 = 1.0792.

(The ``0.99''s correspond to paying the 1% commission, and the ``0.97'' corresponds to the 3% commission.)

Your job is to write a program that will compute the optimal strategy.
If there are *N* investments and *T* weeks, your program
should run in time *O(N^2 * T)*. Here is a hint on how to do it.
Imagine that you
have already computed the best strategy for the first *t-1* weeks, and
moreover, for each *i <= N*, you have computed the best strategy for
the first *t-1* weeks that ends with all your money in investment
*i*.
Now, use this to compute the same thing for week *t*. For
instance, the best *t*-week strategy that ends with all your money in
investment 3 either had all its money in investment 3 at the end of
week *t-1* and then kept it there, or else it had all its money in one
of the other investments at the end of week *t-1* and then sold that
and bought number 3.
You want to pick the best out of these. **Explain in words why the
running time of your program is O(N^2 * T). **

Your program should print out what the value of the best strategy is (e.g., 1.0792 in the above example) and the sequence of buy/sell decisions.

We have given you executables in `invest.dec`, `invest.sparc`,
and `invest.hp` that you can try out to help you debug your code.
You are not required to produce output in exactly the same format as
this, but your output should make clear what the strategy produced is.
There are also several sample input files.

If you want, you can just use `cin` and `cout` for
input and output, and run your program by typing `run < inputfile`
in Objectcenter, or `programname < inputfile` at the unix prompt.
You might also find it useful to create a 2-dimensional array in your
program. Here is one way to make a 2-d array if you haven't done this sort of
thing before:

typedef double *double_arr; // double_arr means an array of double-precision floats int main(void) { double_arr *arr; //2-d array of doubles int num_investments, max_time; cin >> num_investments >> max_time; arr = new double_arr[max_time+1]; for(int t=0; t <= max_time; ++t) arr[t] = new double[num_investments]; ...

After this code, `arr` is a `num_investments` by `
max_time+1` size array, and `arr[t][i]` would be the entry for
investment i and time t.