This optional assignment will be worth up to 15 "bonus" points in the HW/Quiz/Programming pool of points if you choose to do it.
For this project you need to implement the "Median of Medians" style selection algorithm, but in a parameterized way so that it is a "Median of Median-Xs" algorithm, where "X" is guaranteed to be odd. Your selection algorithms must work correctly on any length input we provide and with any odd "X" we provide. It should, of course, implement the algorithm correctly. Since this should work on any comprable data, your method needs to work on any array of Comparable objects. We are not assuming unique elements in the lists for this project.
For simplicity of debugging and testing, we are using integers in the provided JUnit tests. However, if your code would not also work (for example) on Strings, your project will not be considered as correct.
You should download the
zip file of the starter project
for Eclipse and import it.
This project has three files:
• CMSC351PHW2.java
where you implement the median finding algorithm
• CorrectnessTests.java
which has an example test and where you need to add at least one more
rigorous test of your own
• CMSC351PHW2driver.java
which you
may not alter and you will use after you feel your project is complete
You can add helper methods to the CMSC351PHW2 class that you wish,
and you can use the Java class Random to generate random numbers
for generating your test cases.
Within your code, anywhere a comparison to a data value takes place, you must increment the counter called comps in the CMSC351PHW2 class. If there are data comparisons that are not counted, your project will lose points.
We have provided a JUnit test case that you should run to confirm that your code is correctly finding the median. When your program is working, you will run the CMSC351PHW2driver.java and copy and paste the results from that into a word processing document. You will also run the CorrectnessTests.java JUnit test and take a screenshot of the results and paste that into the same word processing documents. In that same document you will also put your name, and a one to two paragraph description of what you found to be the most challenging parts of this assignment. You are required to submit a PDF file printed from that word processing document, and named README.pdf. To create a PDF file from a word processing document, you can install the free CutePDF Writer virtual printer on a Windows machine, or print to PDF on a Mac.
You will submit a ZIP file containing your CMSC351PHW2.java and your CorrectnessTests.java and your README.pdf files to ELMS. Grading will be based on (a) your program actually finds the median value correctly for different sizes and "X" values, (b) the correctness of your comparison counting which will be determined by the teaching assistants reading your code, (c) your code properly following the Median-of-Medians approach, and (d) your written comments.
We're planning on doing any required program execution on the GLUE cluster using Java 1.7 so please do not use Java 1.8 features.