Computer Science 210
Data Structures

Fall 2017, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

For this project, 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 two or three on this project. Of course, collaboration with your partner(s) is unrestricted. You may discuss the assignment with your classmates and give and receive some help, but your submission must be your own work (or that of you and your teammates, if you choose to form a group).

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository bestof-project-yourgitname for this Programming Project. One member of the group should follow the link to set up the repository on GitHub, then that person should email the instructor with the other group members' GitHub usernames so they can be granted access. This will allow all members of the group to clone the repository and commit and push changes to the origin on GitHub.

Please answer lab questions in the README.md file in your group's GitHub repository.

Practice Program

Finding the "Best Of"

The remaining tasks will be graded as a programming assignment.

The first part of 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. Initially, the metric will be determined by the compareTo method of the Comparable objects we we place into the BestOf data structure.

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 will you use for your BestOf's internal data representation? Based on that data representation, what instance variables are needed? Do you plan to store the contents of your BestOf in order at all times or sort them as needed? Why or why not? Some of these answers are given or hinted at strongly in the text. Do not start coding until you are confident in your answers to these questions.

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 written, we will extend it a bit.

Complete the main method in class Syracuse so that it 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 wish to use an extra class to keep track of information for the Syracuse sequence generation (and that's a Good Idea), you might want to declare a non-public class inside of Syracuse.java that can be used only within that Java file (like the list nodes and iterator from SimpleLinkedList).

The intermediate values you will generate can get quite large, so you should store numbers in variables of type long and Long instead of int and Integer as you generate your sequences.

Applying to METAL Graph Data

Next, you will apply this nifty new data structure to the graph data from the METAL project you first saw earlier this semester. Recall that graph files are linked from http://tm.teresco.org/graphs/ and that you can see what this data looks like in map form by loading it into the METAL project's Highway Data Examiner, at /metal/hdx/.

Initially, you will work only with waypoint data and ignore the road segments. Start with your Waypoint class from the earlier project. Recall that a Waypoint represents the data for a single waypoint. It should include fields for the waypoint name and its latitude and longitude values, a constructor, accessors for the three components, and appropriate equals and toString methods. At that time you also wrote a WaypointLoader class that has a main method that takes the name of a .tmg file to be loaded as a command-line parameter, and reads all of the waypoints from that file into a Vector or ArrayList of Waypoint objects. You do not need this program, but you might borrow code from it as you complete the tasks below.

Expanding and Using BestOf

Now let's take your working BestOf structure, enhance it a bit, then use it to compute some information about this mapping data.

What you need to do:

1. Enhance your Waypoint implementation to implement the Comparable interface. There is no single obvious "natural" ordering here, so just have your compareTo 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 a Comparator class or 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 .tmg file name, and a number n, and reports the best n waypoints in the file using each of the 6 criteria from the previous item.

A point of emphasis in this program is on error checking: if your program expects a command-line parameter that is not provided, your program should not crash with an exception. It should print a meaningful error message.

Submitting

Your submission requires that all required deliverables are committed and pushed to the master for your repository's origin on GitHub. That's it! If you see everything you intend to submit when you visit your repository's page on GitHub, you're set.

Grading

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