COP4533 Algorithms Programming Project Solution

1 Problem Definition
We are given a array of price predictions for m stocks for n consecutive days. The price of stock i for day j is A[i][j] for i = 1,...,m and j = 1,...,n. You are tasked with finding the maximum possible profit by buying and selling stocks. The predicted price at any day will always be a non-negative integer. You can hold at most one share of any stock at any time. You are allowed to buy a stock on the same day you sell another stock. More formally,
Problem1 Given a matrix A of m×n integers (non-negative) representing the predicted prices of m stocks for n days, find a single transaction (buy and sell) that gives maximum profit.
Problem2 Given a matrix A of m×n integers (non-negative) representing the predicted prices of m stocks for n days and an integer k (positive), find a sequence of at most k transactions that gives maximum profit. You are allowed to buy and sell the same stock multiple times, as long as you hold at most one stock at any time.[Hint :- Try to solve for k = 2 first and then expand that solution.]
2 Algorithm Design Tasks
You are asked to design three different algorithms for each problem, with varying time complexity requirement in order to conduct an experimental comparative study.
Alg1 Design a Θ(m ∗ n2) time brute force algorithm for solving Problem1
Alg2 Design a Θ(m ∗ n) time greedy algorithm for solving Problem1
Alg3 Design a Θ(m ∗ n) time dynamic programming algorithm for solving Problem1
Alg4 Design a Θ( ) time brute force algorithm for solving Problem2
Alg5 Design a Θ(m ∗ n2∗ k) time dynamic programming algorithm for solving Problem2
Alg6 Design a Θ(m ∗ n ∗ k) time dynamic programming algorithm for solving Problem2
3 Programming Tasks
Once you complete the algorithm design tasks, perform the following programming tasks:
Task1 Give an implementation of Alg1.
Task2 Give an implementation of Alg2.
Task3a Give a recursive implementation of Alg3 using Memoization.
Task3b Give an iterative BottomUp implementation of Alg3.
Task4 Give an implementation of Alg4.
Task5 Give an implementation of Alg5.
Task6 Give an implementation of Alg6 (either Memoization or BottomUp, or both ,).
4 Language/Input/Output Specifications
Problem1: For convenience assume that 1 ≤ m < 100, 1 ≤ n < 105 and ∀i 0 ≤ A[i][j] < 104. If multiple buy/sell transaction pairs yield the maximum profit, output any one of them.
Input. Your program will read input from standard input (stdin) in the following order:
• Line 1 consists of two integers m and n separated by a single space.
• Next m lines each consists of n integers (prices for n days) separated by a single space.
Output. Print the optimal transaction info to standard output (stdout)
• A single line with 3 integers (Stock, BuyDay, & SellDay indices) separated by a space.
Problem2: For convenience assume that 1 ≤ k < 100, 1 ≤ m < 100, 1 ≤ n < 1000 and
∀ij 0 ≤ A[i][j] < 1000. If multiple sets of transactions yield the maximum profit, output any one of them.
Input. Your program will read input from standard input (stdin) in the following order
• Line 1 consists one integer k.
• Line 2 consists of two integers m and n separated by one space character.
• Next m lines each with n integers (predicted prices) separated by a single space.
Output. Print a set of (at most k) transactions that yields the max profit in order of dates. • Each line with 3 integers (Stock, BuyDay, & SellDay indices) separated by a single space.
5 Experiments and Report
Conduct an experimental study to test the performance/scalability of your algorithms/implementations. Your report must include at least the following components: i) Team members; ii) Design and Analysis of Algorithms; iii) Experimental Comparative Study; iv) Conclusion.
5.1 Team Members
You are allowed to work as teams of (at most) two students on this assignment. Clearly state the name and the contribution of each team member.
5.2 Design and Analysis of Algorithms
Describe each algorithm and analyze it (correctness, time & space complexity). Also include the recursive formulation expressing optimal substructure for the dynamic programming algorithms.
5.3 Experimental Comparative Study
Test your implementations extensively for correctness and performance. For this purpose, you should create randomly generated input files of various sizes. The exact size of the experimental data sets that your program can handle depends on the quality of your implementation. For instance, you might want to choose n = 1000,2000,3000,4000,5000 for Task1, and n = 20,40,60,80,100 for Task4 to create at least five data sets for each experiment. Then, you should conduct and present a performance comparison of at least the following: For each comparison, generate a two dimensional plot of running time (y-axis) against input size (x-axis). These should be included in your report along with additional comments/observations.
Plot1 Comparison of Task1, Task2, Task3A, Task3B with variable n and fixed m
Plot2 Comparison of Task1, Task2, Task3A, Task3B with variable m and fixed n
Plot3 Comparison of Task4, Task5, Task6 with variable n and fixed m and k
Plot4 Comparison of Task4, Task5, Task6 with variable m and fixed n and k
Plot5 Comparison of Task4, Task5, Task6 with variable k and fixed m and n
Pick an appropriate value for the fixed values. For each comparison, generate a two dimensional plot of running time (y-axis) against input variable (x-axis). Also include additional plots whenever the plot of one task overshadows others. For instance, if you ended up implementing both top-down and bottom-up versions of Task6, add a separate plot comparing them not to be overshadowed by Task4 and/or Task5. Feel free to include additional plots to present your results.
5.4 Conclusion
Summarize your learning experience on this project assignment. For each programming task, comment on the ease of implementation and other potential technical challenges.
6 Submission
The following contents are required for submission:
1. Makefile: Your makefile must be directly under the zip folder. No nested directories. Do not locate the executable file in any directory either.
2. Source code: should include detailed comments next to each non-trivial block of code.
3. Report: The report must be in PDF format.
4. Bundle: Compress all your files together using a zip utility and submit it on Canvas. Each team makes only one submission with a single zip file identified with last and first names of team members, i.e., LName1FName1LName2FName2.zip
7 Grading Policy
Grades will be based on the correctness & efficiency of algorithms and the quality of the report:
• Program 50%. Correct/efficient design and implementation/execution. Also make sure to include comments with your code for clarity.
• Report 50%. Quality (clarity, details) of the write up on your design, analysis, programming experience, and experimental study.
8 Bonus [upto %30]
For upto 30% bonus points, solve this problem with an additional constraint. Make sure to include all parts of the report for these bonus tasks as well.
Problem3 Given a matrix A of m×n integers (non-negative) representing the predicted prices of m stocks for n days and an integer c (positive), find the maximum profit with no restriction on number of transactions. However, you cannot buy any stock for c days after selling any stock. If you sell a stock at day i, you are not allowed to buy any stock until day i + c
8.1 Algorithm Design Tasks
Alg7 Design a Θ(m ∗ 2n) time brute force algorithm for solving Problem3
Alg8 Design a Θ(m ∗ n2) time dynamic programming algorithm for solving Problem3
Alg9 Design a Θ(m ∗ n) time dynamic programming algorithm for solving Problem3
8.2 Programming Tasks
Task7 Give an implementation of Alg7.
Task8 Give an implementation of Alg8.
Task9 Give an implementation of Alg9.
8.3 Input/Output Specifications
For convenience assume that 1 ≤ c < 100, 1 ≤ m < 100, 1 ≤ n < 1000 and ∀i 0 ≤ A[i][j] <
1000. If there are multiple possible sets of transactions that yield the maximum profit, output any one of them.
Input. Your program will read input from standard input (stdin) in the following order:
• Line 1 consists one integer c.
• Line 2 consists of two integers m and n separated by one space character.
• Next m lines each with n integers (predicted prices) separated by a single space.
Output. Print a set of transactions that yields the max profit in order of dates.
• Each line with 3 integers (Stock, BuyDay, & SellDay indices) separated by a single space.
8.4 Experimental Comparative Study
You might want to use the following comparisons for the Experimental Comparative Study:
Plot6 Comparison of Task7, Task8, Task9 with variable n and fixed m and c
Plot7 Comparison of Task7, Task8, Task9 with variable m and fixed n and c
Plot8 Comparison of Task8, Task9 with variable n and fixed m and c
Plot9 Comparison of Task8, Task9 with variable m and fixed n and c