Data Structures II Instructions: HW2 1. Download the hw2-files.zip file from the COL submission folder for HW2. As you did for HW1, unzip the file into the src folder that

is in the workspace you created for this class. 2. Start up Eclipse. Use the same workspace that was created when you set up Eclipse. If you do not see hw2, right-click on the project or the src folder in the explorer window in Eclipse and select refresh. 3. Open the hw2 folder inside of Eclipse. You will find 6 files. The only 2 files you will be modifying are SequentialSearchST.java and RSequentialSearchSt.java. 4. Modify the 3 methods, put, get, and delete in SequentialSearchST.java so that the list is maintained in increasing order of the keys. When implementing put, get and delete, make sure to take advantage of the fact that the list is in order to avoid looking at all the items in the list. Also, whenever the list is modified, you will need to make sure it is still in sorted order after the modification. None of the functions may use recursion. You may not use/call the keys() method. Note: You are modifying the implementation of the methods, but not their interface or contract. To the external world, the methods should behave exactly as before. Make sure you code takes advantage of the sorted order. We will be checking for this and you will receive no credit for a method that blindly checks the entire list when it isn't necessary. The code you were given already does exactly that. 5. Use the HW2Test.java file to test the correctness of your SequentialSearchST.java code. 6. Run the JUnitTiming.java file. It will call put, get, and delete multiple times, checking for how long the calls take. If these tests fail, it is almost certainly because your code is not taking advantage of the sorted order of the keys to stop its search early. 7. Modify the 3 methods, put, get, and delete in RSequentialSearchST.java so that the list is maintained in increasing order of the keys. When implementing put, get and delete, make sure to take advantage of the fact that the list is in order to avoid looking at all the items in the list. Also, whenever the list is modified, you will need to make sure it is still in sorted order after the modification. All of these functions must use recursion instead of loops. This means each one will need a private helper method that takes a node (the front of the list) as an additional argument. Your RSequentialSearchST.java file cannot contain any loops except in the keys() method method which you are not changing. You may not use/call the keys() method in your code. Note: You are modifying the implementation of the methods, but not their interface or contract. To the external world, the methods should behave exactly as before. Make sure you code takes advantage of the sorted order. We will be checking for this and you will receive no credit for a method that blindly checks the entire list when it isn't necessary. 8. Use the RHW2Test.java file to test the correctness of your RSequentialSearchST.java code. 9. Run the RJUnitTiming.java file. It will call put, get, and delete multiple times, checking for how long the calls take. If these tests fail, it is almost certainly because your code is not taking advantage of the sorted order of the keys to stop its search early. 10. IMPORTANT: You may not change or remove the line that says "package hw2" nor may you change any public method headers. Sumission: Submit both your SequentialSearchST.java file and your RSequentialSearchST.java file. Submit the following four screenshots: O A screenshot of what happens when your run HW2Test.java. A screenshot of what happens when your run JUnitTiming.java. A screenshot of what happens when your run RHW2Test.java. O A screenshot of what happens when your run RJUnitTiming.java Double check your submission. Download the files and make sure they are the ones you intend to submit! Do not skip this step. Every quarter I have students who have more than one version of the file on their computer and they submit the wrong one. Grading: O O The test functions for HW2Test.java add up to 100 as do the test functions for RHW2Test.java. If you pass all tests, your score should be 100 for each part. However, your code must pass the timing tests. The maximum possible score for SequentialSearchST will be reduced by 30 for each test from JUnitTiming that fails. This means that if one of the JUnitTming tests fails, your max possible score for SequentialSearchST would be 70 (even if all the tests in HW2Test.java pass). The same holds true for RSequentialSearchST and RJUnitTiming. Namely, your max possible score on_RSequentialSearchST will be reduced by 30 for each test from RJUnitTiming that fails. Your final score on HW2 will then be the average of your scores on the two parts (just add and divide by 2) minus 5 points for each of the four required screenshots that is missing. You will also not receive credit for any code in SequentialSearchST that uses recursion nor for any code in RSequentialSearchST that uses a loop.