Computer Science 501
Data Structures and Algorithm Analysis

Fall 2014, The College of Saint Rose

Home     Syllabus     Schedule     Style Guide

For this lab, you will be implementing an interesting ordered structure and using it in a number of contexts.

You may work alone or in a group of 2 or 3 on this lab. Only one submission per group is needed.

Getting Set Up

To get your BlueJ environment set up for this week's lab assignment, start BlueJ and choose "New Project" from the "Project" menu. Navigate to your folder for this course and choose the name "Lab9" (no spaces) for the project.

Create a document where you will record your answers to the lecture assignment and lab questions. If you use plain text, call it "lab9.txt". If it's a Word document, you can call it whatever you'd like, but when you submit, be sure you convert it to a PDF document "lab9.pdf" before you submit it.

Lecture Assignment Questions

We will usually discuss these questions at the start of class on the lab due date, so no credit can be earned for late submissions of lecture assignment questions.

Practice Program

Programming Assignment

Your programming assignment is to complete the laboratory in Section 11.4 of Bailey - computing the "Best Of" a collection of values by some metric (the compareTo method of Comparable objects).

First, carefully read the lab description in the text. Before you start coding, think carefully about the BestOf class. What does it extend and/or implement? What instance variables are needed? Do you plan to store the contents of your BestOf in order? Why or why not?

Your BestOf's main method should run one or more simple test cases for your structure. You may use the one described at the top of p. 276 or devise your own test cases.

Rather than answering thought question 3 as is, we will expand it a bit.

Write a program as a main method to a class Syracuse in a file Syracuse.java that generates the Syracuse sequences for all starting values from 1 up to n, given as a command-line parameter. Your program should track and report the following:

1. The top k (a second command-line parameter) intermediate values encountered at any point in the sequences. At the end it should report the k 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 k longest sequences. At the end it should report the length of the k longest sequences and the n that generated each.

You should maintain two BestOfs for this program, one responsible for each above the parts above. 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.

Expanding and Using BestOf

Now that you have a working BestOf structure, let's use it to compute some things about the mapping data we saw from an earlier lab. You wrote a program that included a Waypoint class that held information from the .gra files linked from /chm/graphs.html.

What you need to do:

1. Enhance your Waypoint implementation to implement the Comparable interface. There is no "natural" ordering here, so just have your compare method order Waypoints in alphabetical order by waypoint name.
2. Enhance your BestOf implementation as indicated in thought question 4 to use a Comparator to compare objects for inclusion in the structure.
3. Write Comparator classes that compare Waypoint objects in the following ways: increasing latitude (northernmost), decreasing latitude (southernmost), increasing longitude (easternmost), decreasing longitude (westernmost), alphabetical order by waypoint name, order by length of waypoint name.
4. Write a program WaypointBest that has a main method that takes 2 command-line parameters: a .gra file name, and a number n, and reports the best n waypoints in the file using each of the 6 Comparators from the previous item.

Note: for this section, all except the BestOf enhancement will be graded as a practice program.

Submitting

Before 6:00 PM, Tuesday, November 11, 2014, submit your lab for grading. There are two things you need to do to complete the submission: (i) Copy your file with the answers to the lecture assignment and lab questions into your project directory. Be sure to use the correct file name. If you prepared your answers in Word, export to a PDF file and submit that. (ii) Upload a copy of your lab (a .7z or .zip file containing your project directory) using Submission Box under assignment "Lab9".

Grading

This assignment is worth 80 points, which are distributed as follows: