Assignment: Maximizing Stock Profit with Dynamic Programming Dynamic Programming is a fundamental design principle underlying many algorithms. In this project, you are expected to devise and implement...

Please follow the Grading Rubric


Assignment: Maximizing Stock Profit with Dynamic Programming Dynamic Programming is a fundamental design principle underlying many algorithms. In this project, you are expected to devise and implement a Dynamic Programming solution to the problem of maximizing the profit of a stock in ??(??) time and ??(1) space. Learning Objectives: The learning objectives for this assignment are four-fold: • To understand one of the core principles of algorithm design: the dynamic programming. • To demonstrate the ability to design and write a dynamic programming solution to a given problem. • To evaluate the time and space complexity of the three approaches: brute force, divide and conquer, and dynamic programming. • To benchmark and compare the performance of three approaches to the same problem: brute force, divide-and-conquer, and dynamic programming to a given problem. When to Buy and Sell Stock Problem Statement: Say you have an array of stock prices, for which the ????ℎ element is the price of a given stock on day ??. You are only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock). Design an algorithm to find the maximum profit. Note: The buy date should be before sell date. Report: the amount of the maximum profit, the buy day and the sell day. Support Materials: To complete this 3-part assignment, you are provided the following support materials. • The folder codes: contains Python implementations of the Brute Force and Divide & Conquer solutions to the problem. • The Google Drive folder for the SP500 data: contains real stock prices for different stocks. You are welcome to test your code on the real data sets: https://drive.google.com/file/d/0BzxtQMu0c3qhcGNaTFZHcFgxSXc/view The link contains a zip folder that includes the following: o sp500_data.hdf5 - hdf5 file with SP500 data from 1995 to 2015. It also includes 'R' column that was a calculated 'log return' o sp500_data.csv file containing log returns for all the symbols and dates in hdf5 file. • Description of the Brute Force and Divide & Conquer Strategies described below, for which the codes are provided in the codes folder • Hints/suggestions on how you might design the Dynamic Programming solution that requires ??(??) time and ??(1) space. What to Submit and Grading Rubric: You are expected to submit a single zip folder that includes the following: 1. Big-O analysis of the time complexity for the Brute Force strategy: 10 points 2. The recurrence formula for the Divide and Conquer strategy: 10 points 3. Application of the Master Theorem to the Divide and Conquer recurrence, with the final Big-O analysis of the time complexity: 10 points https://drive.google.com/file/d/0BzxtQMu0c3qhcGNaTFZHcFgxSXc/view 4. Python implementation of ONE of the three Dynamic Programming strategies: 40 points 5. Justification of why your DP implementation requires ??(??) time and ??(1) space: 10 points 6. The plot of experimental benchmarks that illustrates the comparative analysis of the three strategies (time complexity vs. problem size): 20 points Dynamic Programming Strategies (Hints): Implement ONLY ONE • DP Strategy #1: Start from the last day, linear scan through until the first day. While dealing with ????ℎ day, just find the day in ?? + 1 to ?? with maximum prices. Such day could be found in constant time ??(1) if you use the previous maximum value among the days from ?? + 2 to ??. • DP Strategy #2: Similar to Stretgy #1, start from the beginning of the price array, i.e., start from day 0 to day 1 to … day ??. Find the minimum prices among ????????????[0. . ??] and for each day ??, you need only to know the maximum profit you could earn by selling it at day ??. • DP Strategy #3: Converting the problem into Maximum Subarray problem. That is, from the original array prices, you make a new array called ?? with ??[??] = ????????????[??] − ???????????? [?? − 1]. Then the answer to the best time to buy and to sell the stock is the same answer as to find the maximum sum of consecutive subarray in array ??. Brute Force Strategy: The naive try (brute force) way is to just scan through all prices and find the pair with the maximum difference; basically, it looks at all possible buy and sell dates that meet the constraint that sell date may only happen on/after the buy date but not before. Divide and Conquer Strategy: Divide the input list into two parts and recursively find the solution. Here, we have three cases: • buyDateIndex and sellDateIndex both are in the earlier time period • buyDateIndex and sellDateIndex both are in the later time period • buyDateIndex is in the earlier part and sellDateIndex is in the later part of the time period The first two cases can be solved with recursion. The third case needs care because buyDateIndex is on one side and sellDateIndex is on the other side. In this case, we need to find the minimum and maximum prices in the two sub-parts and your time complexity analysis should take this cost into consideration.