Question

You have corrupt friends in Wall Street that supply you with the following information:
the stock price of ten fraudulent companies every month for a year. You have access to the
data for the entire year in advance. You would like to use this information to get as rich as
possible by the end of the year.
At the start of every month k, you look at the table S[i,k], which gives you the average return on
on a $1 investment in company i during the entire month k. You would like to invest $100 000
per month. You want to invest the entire sum in one company at a time. By the end of the
month, you either keep all your investments in one company for the next month, or your sell
your stocks, and invest the $100 000 in a new company. Every month k, you make 100 000 * S[i,k] of profit for investing in company i. You have to pay $7500 to Wall Street every time you
sell your stocks. This means that if you keep your investment in the same company from month
k to month k+1, you do not pay the $7500 fee.
(a)
Write a dynamic programming algorithm to guide your investments. Which company should
you invest in each month? You are given table S[0 <= i <=9, 0 <=k <=11] as input.

Store your answer in a table C, where C[k] = i indicates investing in company i at month k.

(b) Would your dynamic programming solution be simpler if you didn’t have to pay $7500 to
sell stocks? Explain your answer.

Algorithm to be written in python

Answer 1

Let's first see the main objective and the decision we have to actually make in this particular problem.

Aim- To gain maximum returns possible on every $100000 invested every month.

Decision to take-

1. Which company to invest in for maximum returns.
2. Whether it would be right to change the company after the present month is over. Here, we know every time the company is changed and the stocks are sold, an amount of $7500 has to be paid to Wall Street. So, here our main aim would be go for a company that not only gives returns more than the present company, but also that the overall returns for that month is greater than $7500.

So, here our base condition is deciding the company to invest in and whether the company should be changed.

Algorithm-

1. Select the first company to be invested in, this step is OPT(0). To find the value of OPT(0), take the return per dollar given by each company.
2. Start of loop.
3. Traverse through the table S[i,k]. The value S[i,k] gives the return by each i on a dollar.
4. Since, we are looking for the first month, the value of k would be zero (the value of k lies between o and 11).
5. Take an integer variable, say 'x', to store the value of return by the first company, here i=0, now go to the second company and check whether the value of return is greater or smaller than the value of return for the first company.
6. If the value of return for the second company is greater than that of the first company, put the value of S[1,0] (second company, 1st month, since the values are starting from zero, first means zero and second is one), in x.
7. Increament the value of i again and repeat the process.
8. At the end, x will contain the value of the maximum return possible for the first month.
9. End of loop.
10. Now, we need to find which company is giving the maximum return.
11. Start of loop.
12. Again traverse through the table S[i,k].
13. This time, find the index position which contains the company that gives the return equal to the value present in x.
14. Store the index value in an integer variable, say y.
15. Return the value of y.
16. End of loop.
17. Now we have found out company in which investment should be made for the first month(k=0)

Note- here, the value of the index could have been found out in the same loop, without having to use the second loop, that would have been more feasible solution, in fact instead of checking the maximum value by comparing each term, we could have used the MAX() function present in Python. But I didn't use it just because my aim is to give clear understanding of what needs to be done exactly. Please do make use of MAX() function to enhance the quality of the algo.

Now for the investment made for the subsequent months.

This step is OPT[1] and similarly OPT[2], and so on

The steps here would be the same for all the subsequent months.

1. Go for OPT[1]. in OPT[1], say the present company we have invested in is i and the next company to be chosen is j.
2. So, in OPT[1], i = j, when the maximum return is in the company i for the month k(the month in which investment has to be done). Or else, i<>j, when the maximum return is not in company i for the month k and also, the total return made by j (100000*S[j,k]) is greater than $7500.
3. Let's proceed for OPT[1]. (also, the steps are same for OPT[2], OPT[3], OPT[4], and so on)
4. Here, value of k>=1.
5. Store the value of return made by the present company in which you have already invested in an int variable b.
6. Start the loop.
7. Go through the table S[i,k].
8. Initialize the value of i with zero and loop till the value reaches 9.
9. Find the maximum return made using MAX(S[i,k]).
10. Store this maximum return in an int variable, say a.
11. Compare the values stored in a and b.
12. If b>a, then let the investment continue in the present company.
13. But, if a>b, multiply a by 100000 and check if a>7500.
14. If a<=7500, then again let the investment continue in the present company.
15. But, if a>7500, then find the index value of the company which stores the value a, i.e., find for which value of i, S[i,k] = a.
16. This particular index is the index position of the companty in which the next investment has to be made.
17. End of loop.

I have divided the alogorithm into two parts, these can also be combined if needed. But there would be two major parts, the investment made in first month when k=0 would be the first part, the investment made in the subsequent months k>=1 would be the second part.

Part (b) of the question

Yes, the algorithm would have been easier had there been no payment of $7500 to be made. This is because, in algorithm presently, we have to take two cases, first for the investment made in first month and second for the investment made in months after the first month. Also, for the investment in the second month and so on, we not only have to look for the company giving maximum profit, but we also have to check whether the company is giving overall profit greater than $7500. If there had been no case of $7500, our algorithm would have only one part and almost the same process would have been followed for all the months. The only decision to change the company would have been made on the basis of maximum profit. We only would have to check if the profit by present company for the month k+1 ( the next month) is highest or not, if yes, then continue in the same company. If no, then check company gives the highest profit and invest there. But, in case of time complexity, there is not much change. In the present scenario, we have to move one extra step, in which we are checking whether the overall profit made by the company giving maximum profit (profit on $100000) which is not the same as present company, is greater than $7500.