Amog has been following the stock market for a while and is particularly interested in investing in Godrej. The stock price of the company is currently volatile and he wants to try and make some quick money. He decides to deploy an algorithm that can analyse pervious months’ stock prices and indicates when to buy and when to sell such as to maximize profits. He will use that learning to time his entry and exit in the future. Your goal is to help Amog come up with the program to analyse the stock prices. The figure below shows the price of the stock over a 17-day period.

Information about the price of stock after the close of trading over a period of 17 days is given above. The horizontal axis of the chart indicates the day, and the vertical axis shows the price. The bottom row of the table gives the change in price from the previous day.
Requirements:
1. Formulate an efficient recursive algorithm using Divide and Conquer to perform the above task
2. Also develop a non-recursive, linear-time algorithm for above problem.
3. Analyse the time complexity for requirement 1.
4. Implement the above problem statement using Python 3.7

Sample Input:
Input should be taken in through a file called “inputPS10.txt” which has the fixed format mentioned below using the “/” as a field separator:
/
Ex.
0 / 100
1 / 113
2 / 110
3 / 85
…
Note that the input data shown here is only for understanding and testing, the actual file used for evaluation will be different.

Sample Output:
Maximum Profit(Divide & Conquer): 43
Day to buy: 7
Day to sell: 11
Maximum Profit(Iterative Solution): 43
Day to buy: 7
Day to sell: 11
Note that the output data shown here is only for understanding and testing, the actual file used for evaluation will be different. The output need not match the sample input provided earlier.
The output should be written to the file outputPS10.txt

2. Deliverables

• Word document designPS10_.docx detailing your algorithm design and time complexity of the algorithm.
• [Group id]_Contribution.xlsx mentioning the contribution of each student in terms of percentage of work done. Download the Contribution.xlsx template from the link shared in the Assignment Announcement.
• Zipped AS2_PS10_MaxProfit_[Group id].py package folder containing all the modules classes and functions and the main body of the program.
• inputPS10.txt file used for testing
• outputPS10.txt file generated while testing

3. Instructions

a. It is compulsory to make use of the data structure(s) / algorithms mentioned in the problem statement.
b. Use only native data types like lists and tuples in Python. Use of libraries like graph, numpy, pandas library etc. is not allowed. The purpose of the assignment is for you to learn how these data structures are constructed and how they work internally.
c. It is compulsory to use Python 3.7 for implementation.
d. Ensure that all data structure insert and delete operations throw appropriate messages when their capacity is empty or full.
e. For the purposes of testing, you may implement some functions to print the data structures or other test data. But all such functions must be commented before submission.
f. Make sure that your read, understand, and follow all the instructions
g. Ensure that the input, prompt and output file guidelines are adhered to. Deviations from the mentioned formats will not be entertained. If your program fails to read the input file used for evaluation, your program will not be evaluated.
h. The input, prompt and output samples shown here are only a representation of the syntax to be used. Actual files used to test the submissions will be different. Hence, do not hard code any values into the code.
i. Run time analysis is provided in asymptotic notations and not timestamp based runtimes in sec or milliseconds.

 

120 110 100 90 80 70 0 2 3 4 5 Day 012 3 4 5 Price 100 113 110 85 105 102 Change 6 7 9 10 11 12 13 6 7 8 9 63 81 101 13 -3 -25 20 -3 -16 -23 18 86 14 10 11 12 94 106 101 20 -7 12 -5 15 16 13 14 15 16 79 94 90 97 -22 15 -4 7