Problem Set #4 Solution

Problem 1. In this exercise, we consider two variants of the following problem. You are given an array of integer numbers X[0]; : : : ; X[n 1]. You need to partition it into k groups P1; : : : ; Pk so that numbers in every group Pj are distinct. Your goal is to minimize the number of groups, k.




Problem 1A: In the rst variant of the problem, each group Pj must contain consecutive elements of array X. For example, we can partition array 1; 2; 3; 4; 1; 7 into groups G1 = h1; 2i and G2 = h3; 4; 1; 7i or G1 = h1; 2; 3i and G2 = h4; 1; 7i, but we cannot partition it into groups G1 = h1; 3; 7i and G2 = h2; 4; 1i, because elements in these groups are not consecutive. We also cannot partition X into G1 = h1; 2; 3; 4; 1i and G2 = h7i, because in this case G1 contains two identical elements (speci cally, two \1"s).




Problem 1B: In the second variant of the problem, groups Gi do not have to contain consecutive elements of array X. So in the above example, the rst three partitionings G1 = h1; 2i and G2 = h3; 4; 1; 7i; G1 = h1; 2; 3i and G2 = h4; 1; 7i; G1 = h1; 3; 7i and G2 = h2; 4; 1i are valid. However, the fourth partitioning G1 = h1; 2; 3; 4; 1i and G2 = h7i is still not valid.




For both problems { Problem 1A and Problem 1B { do the following:




 
Describe a greedy algorithm that solves this problem.




 
Prove that your algorithm is correct.




 
Analyze the running time of your algorithm. To get a full credit for this problem, the running time your algorithm should be O(n log n) or less.




Problem 2. We ask you to implement your algorithms for Problem 1A and Problem 1B:




int ProblemA (std::vector<int X) int ProblemB (std::vector<int X)




Array X is the array you need to partition. ProblemA and ProblemB should return the number of groups in the optimal solutions to Problem 1A and Problem 1B.




Instructions for the programming assignment. Download les:




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




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







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




If you use CLang compiler, type




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




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







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







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




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




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




Make sure that you are submitting the latest versions.




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



































































2