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
Explanation: The first number in the file gives the number of
different investments under consideration: in the above example, there
are 4. The second number gives the number of time periods (weeks).
Next, for each investment, are two numbers: the commission you pay to
buy it, and the commission to sell it. For instance, in this example,
there is no commission to buy or sell the first investment. The second
investment costs 1% to buy and 1% to sell. The third
has a 5% charge to buy and zero to sell, and the fourth has zero to
buy and 3% to sell. We assume that at time zero, all our money is in
the first investment, which corresponds to having the money in our
pocket (that's why there's no commission on it).
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.