Computer Science 211
Data Structures

First, carefully read the lab description in the text and this handout. You will have questions, so be sure to leave plenty of time to discuss this assignment with me and the TAs.

Next, develop a sketch of the BestOf class. What does it extend and/or implement? What instance variables are needed? Do you plan to store its contents in order? Why or why not?

No later than Monday, November 2, please either see me to go over your sketch of this class or email it to me for comment and discussion (for 3 points).

• Your BestOf's main method should run a simple test case for your structure. You may use the one described at the top of p. 276 or devise your own test cases.
• Answer thought questions 1 and 2.
• Question 3 asks you to generate Syracuse Sequences for all value of n up to 10,000. We will extend this question as follows.
  1. Find the top 25 intermediate values encountered at any point in the sequences. At the end it should report the 25 values, and for each, print out the value, the n that generated it, and the position in the sequence for n where the large value occurred.
  2. Find the top 25 longest sequences. At the end it should report the length of the 25 longest sequences and the n that generated each.

  You should maintain two BestOfs for this program, one responsible for each above the parts above.

  Write this program as a main method to a class Syracuse in a file Syracuse.java. Should you need to use an extra class to keep track of information for the Syracuse sequence generation, you can declare a non-public class inside of Syracuse.java that can be used only within that Java file. See the MazeRunner program for examples of these non-public classes.

  The intermediate values you will generate can get quite large, so to be safe, use values of type long and Long instead of int and Integer as you generate your sequences.

When you are finished, please submit the following by email to jteresco AT mtholyoke.edu:

• Your source code for BestOf.java and Syracuse.java.
• A README file that contains your answers to thought questions 1 and 2. (Your answer to the expanded version of thought question 3 will be generated automatically when I run the main method in your Syracuse class.)

This lab assignment is graded out of 30 points. As in all labs, you will be graded on design, documentation, style, and correctness. Be sure to document your program with appropriate comments (use Javadoc!), including your name and a general description at the top of the file, a description of each method with pre and postconditions where appropriate. Also use comments and descriptive variable names to clarify sections of the code which may not be clear to someone trying to understand it.

The program design grade will be based on the design choices you make in the implementation of the BestOf class. The program style grade will be based on code formatting and approriate use of Java naming conventions. The program documentation grade is, of course, based on the comments you provide (including Javadoc and pre and postconditions as appropriate). The program correctness grade is based on how well your program meets the functionality requirements.