Problem Set #5 Solution

Problem 1. In this exercise, your goal is to design an algorithm for a cryptocurrency startup. The startup has a supercomputer that can mine two types of coins: NorthCoins and WestCoins. The pro t from mining these coins drastically varies over time, and your goal is to determine which of the two types of coins the startup needs to mine at what time. The problem is that the supercomputer cannot immediately switch from mining NorthCoins to mining WestCoins or vice versa, because each type of coins requires its own software, and it takes 1 unit of time to load it. So, for example, if we mine NorthCoins at the time interval [t; t + 1], we can start mining WestCoins only at time t + 2. In this particular case, the supercomputer will be loading software for WestCoins and not mining any coins at time interval [t + 1; t + 2] .

Your algorithm is given two arrays of positive numbers N1; : : : ; NT and W1; : : : ; WT .




Nt is the pro t the startup gets from mining NorthCoins at interval [t; t + 1]; and




Wt is the pro t the startup gets from mining WestCoins at interval [t; t + 1].




Your algorithm needs to nd the maximum pro t the startup can get from mining NorthCoin and WestCoin at time interval [1; T ].




Example. Consider the following example: N = f10; 10; 10; 10; 20g and W = f2; 15; 1; 7; 100g.






1
2
3
4
5












N
10
10
10
10
20












W
2
15
1
7
100















Then, the optimal solution to the problem is to mine Northcoins at time intervals [1; 2], [2; 3], [3; 4], load new software at time interval [4; 5], and mine WestCoins at time interval [5; 6]. The pro t from this solution is 10 + 10 + 10 + 100 = 130.




 
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.




Hint: You may de ne not one but three subproblems ProfitN[t], ProfitW[t], and ProfitLoad[t]. In every feasible solution to ProfitN[t], the supercomputer mines NorthCoins at time t; in every feasible solution to ProfitW[t], the supercomputer mines WestCoins at time t; in every feasible solution to ProfitLoad[t], the supercomputer loads new software to mine NorthCoins or WestCoins.




Remark: You do not need to explain how backtracking works.




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




int FindMaxProfit (std::vector<int north, std::vector<int west)




Arrays north and west contain pro ts the startup can get from mining NorthCoin and WestCoin (respectively). Note that arrays north and west are indexed from 0 to T 1, here T is the size of the arrays. FindMaxProfit should return the maximum pro t startup can earn at time interval [0; T ].




Instructions for the programming assignment. Download les:




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




problem solver 5.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 5.in { this le contains test problems for your algorithm (don't edit this le!)







Place all les in a new folder/directory. Write your code in function FindMaxProfit. Also, write your name in the function GetStudentName. Both functions are located in le student code 5.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 5.cpp -o problem solver 5




If you use CLang compiler, type




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




If you use Microsoft Visual C++ compiler, start Developer Command Prompt and type cl /EHsc problem solver 5.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 5 on Unix or Mac and problem solver 5.exe on Windows. Make sure that the executable is located in the same folder as le problem set 5.in. Your program will generate solution 5.dat that contains solutions to the problems from le problem set 5.in. If your code works correctly, you will get the following message:







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




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




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




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




Make sure that you are submitting the latest versions.




Remark: If you want to debug your code, please, type ./problem solver 5 15 on Unix or Mac and problem solver 5.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 5.dat. So before submitting your solution, you need to run your program without any command line arguments.










2