Problem Set #6 Solution

Problem 1. A hedge fund Forecast336 is designing a machine learning algorithm that predicts time series X1; : : : ; Xn. It is known that all numbers Xi must belong to the set f0; 1; : : : ; Mg and X1 X2 Xn. The prediction algorithm consists of two functions: The rst function nds an initial guess Y1; : : : ; Yn. This guess may not satisfy the constraints imposed on the series X1; : : : ; Xn. Speci cally, the sequence Y1; : : : ; Yn may be non-monotone. The second function transforms Y1; : : : Yn into a non-decreasing sequence X1; : : : ; Xn that is close to Y1; : : : Yn.




In this exercise, your task is to design a dynamic programming algorithm for the second function. Your algorithm receives an array Y1; : : : Yn and a parameter M. Each element Yi belongs to the set f0; 1; : : : ; Mg. Your algorithm needs to nd a sequence X1; : : : ; Xn such that




 
Each Xi is in the set f0; 1; : : : ; Mg.




 
The sequence X1; : : : ; Xm is non-decreasing i.e., X1 X2Xn.




The algorithm needs to minimize the following objective:




n


Xi
jXi Yij2:
cost(X) =
=1


To design your algorithm, please do the following.





 
De ne a subproblem or several subproblems.




 
Describe the base cases.




 
Write a recurrence relation.




 
Prove that your recurrence relation is correct.




 
Give an algorithm for nding a solution to your subproblem.




 
Give an algorithm for nding the optimal solution to the original problem.




 
Analyze the running time of your algorithm. To get full credit for this problem, the running time




of your algorithm should be O(nM) or less. You will get most credit if the running time of your algorithm is O(nM2).




Remark: In this exercise, your algorithm needs to output the cost of the solution cost(X). You do not need to explain how to nd the actual vector X using backtracking.































1
Problem 2. We ask you to implement your algorithms for Problem 1 in function




int FindMonotonePrediction (const std::vector<int& y, int M)




FindMonotonePrediction should return the cost of the optimal vector X for a given y and M.




Instructions for the programming assignment. Download les




student code 6.h { this le should contain your solution.




problem solver 6.cpp { this is the main le in the project (don't edit this le!).




test framework.h { this is a library responsible for reading and writing data les (don't edit this le!)




problem set 6.in { this le contains test problems for your algorithm (don't edit this le!)







Remark: These les will posted online on Wednesday, February 20.




Place all les in a new folder/directory. Write your code in function FindMonotonePrediction.




Also, write your name in the function GetStudentName. Both functions are located in le student code 6.h.




Compile and run your code. To compile your code do the following.




If you use GNU C++ compiler, type




g++ -std=c++11 problem solver 6.cpp -o problem solver 6




If you use CLang compiler, type




clang++ -std=c++11 problem solver 6.cpp -o problem solver 6




If you use Microsoft Visual C++ compiler, start Developer Command Prompt and type cl /EHsc problem solver 6.cpp







Your compiler should be compatible with C++11. If you work in TLab, you need to start developer tools rst: Type




scl enable devtoolset-4 bash




Once you compile your code, start your program. Type ./problem solver 6 on Unix or Mac and problem solver 6.exe on Windows. Make sure that the executable is located in the same folder as le problem set 6.in. Your program will generate solution 6.dat that contains solutions to the problems from le problem set 6.in. If your code works correctly, you will get the following message:







Problem set 6. Your algorithm solved all test problems correctly. Congratulations! Don't forget to submit your source code and le solution 6.dat via Canvas.







If your code makes a mistake, you may get a message like this:




Problem set 6. Mistake in problem #15. Correct answer: 4. Your answer: 12.




Finally, when your code is ready, submit les student code 6.h and solution 6.dat via Canvas.




Make sure that you are submitting the latest versions.




Remark: If you want to debug your code, please, type ./problem solver 6 15 on Unix or Mac and problem solver 6.exe 15 on Windows. This command will call your function only on one prob-lem { the problem #15 and thus let you debug your code on the problem where your program erred. Note that this command will not generate or update solution 6.dat. So before submitting your solution, you need to run your program without any command line arguments.










2