Computer Science 210
Data Structures

Fall 2018, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

You may work alone or in a group of size 2 or 3 on this assignment. However, in order to make sure you learn the material and are well-prepared for the exams, you should work through non-coding problems on your own before discussing them with your partner, should you choose to work with someone. Also, be sure every programming task is a team effort. In particular, the "you do these and I'll do these" approach is sure to leave you unprepared for the exams.

All GitHub repositories must be created with all group members having write access and all group member names specified in the README.md file by 4:00 PM, Monday, October 22, 2018. This applies to those who choose to work alone as well!

There is a significant amount of work to be done here, and you are sure to have questions. It will be difficult if not impossible to complete the assignment if you wait until the last minute. A slow and steady approach will be much more effective.

Getting Set Up

You will receive an email with the link to follow to set up your GitHub repository for this problem set (ps4-yourgitname). 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 the questions later in this assignment in the README.md file in your repository. Use Markdown to format neatly. Extensive formatting is not necessary.

More Recursion

Your first task is to write one more recursive method along the lines of those you wrote for Lab 5. This one will compute the sum of k consecutive values of an array, starting at a given index. We'll call this a "subarray sum".

The method stub for subArraySum and a comment describing in more detail what it should do can be found in SubArraySum.

Command-line Parameters

We can provide information to a Java application through the args parameter to its main method. As you can see from the main method signature we have been using all semester, it is an array of Strings. These String values come from what the program's user types after its name on the command line when running the program. Different Java IDEs provide different mechanisms for specifying these Strings, known as command-line parameters. In BlueJ, these are specified in a dialog box that we have been ignoring each time we run a Java application - the one that comes up after you choose main from the right-click menu to run your application. To specify the command-line parameters, we specify them as an array of String with the same syntax as a statically initialized array in Java. For example, we could specify an array of 3 String values:

  { "Java", "is", "fun" }

The Java run-time system will construct and initialize an array with these values, and we can access "Java" as args[0], "is" as args[1], and "fun" as args[2] in our program's main method.

Note: you can convert a String whose contents can be interpreted as an integer value to an int by passing it to the Integer.parseInt method.

Sorting with Comparables

The programming for this part of the problem set will be graded as a programming project. Pay attention to style and documentation!

In your starter repository, you will find an iterative implementation of selection sort. Like the recursive version in the SortingComparisons example, it operates on an array of objects which implement the Comparable interface (which you used in lab last week).

Its method header looks like this:

    public static <T extends Comparable> void sort(T[] array)

This complicated syntax is Java's way of introducing a type parameter T, much like the type parameters we have seen in generic classes, but differing in two ways: (i) the type parameter is specified only for the method, not the entire class, so it is meaningful only within the implementation of this method, and (ii) the type parameter has a restriction that it can only match types that can be treated as Comparable objects. It is this second difference that allows us to assume, within the sort method, that a compareTo method exists for objects of type T. This further allows us to write a single general-purpose sort method that works on any kind of objects that are Comparable.

Temporarily remove the implements Comparable<Ratio> from the class header of your Ratio class. Your Ratio class will still compile, but now SelectionSort should not.

Sorting with Comparators

The programming for this part of the problem set will also be graded as a programming project. Pay attention to style and documentation!

Now suppose we want to sort these same kinds of objects, but by different criteria. Perhaps we want to sort Integers in descending order. Perhaps we want to sort Ratio objects by their numerators, ignoring denominators.

We could accomplish this by changing our Comparable objects' compareTo methods. However, this then means we have imposed a new kind of ordering on those objects. Furthermore, we cannot modify the compareTo methods of builtin classes like Integer.

For many types of data, a compareTo method can be used to define its "natural" ordering. But not all data types have an obvious natural ordering, and even for those that do, we might not always want to use that ordering to guide a sort process. There could be many perfectly reasonable criteria on which we might wish to sort a particular kind of data.

Java provides another interface that allows us to define any number of orderings for objects of a given type: the Comparator interface.

Unlike the Comparable, the Comparator interface is typically implemented by a separate class from the one it is designed to compare.

Study and try out the RatioNumeratorComparator in your starter repository. It is able to compare Ratio objects based only on their numerators.

We can use Comparators to implement an even more general-purpose sorting method than the one given in SelectionSort. If we pass an additional parameter to a sort method that provides a Comparator that works with the type of objects in the array, we can use that Comparator's compare method any time we need to compare two items during the sort procedure.

The method header should look like this:

  public static <T> void sort(T[] array, Comparator<T> c)

Note that if T is a class that implements Comparable, then the NaturalComparator can be used.

Using your Comparator-based sort

Write two applications (three if you are working in a group of three). They should each work on a different data file and each should perform more than one "interesting" sort process. Both/all three will use the same Comparator-based sort method in the SelectionSort class, but each application will call its own class for encapsulating the data objects you are working with, and a number of Comparators to sort the data in different ways. You should have a total of at least five (seven, if working in a group of three) unique Comparators in your submission.

You may choose from the data files I have provided in the starter repository. (see the EXAMPLES-README.txt file there for more information) or you may use some other data that you find interesting. Please include all data files that you use in your submission.

Whatever types of data you choose to use, you will need to implement a custom class that holds the details of each type of data, Comparators that can compare instances of that class by different criteria, and an Java application that uses those Comparators to sort an array that holds instances of your custom class in multiple ways. The examples directory includes a data file movies.dat, whose entries are used to create instances of the provided MovieInfo class, three classes that implement Comparator and compare MovieInfo objects by different criteria, and an application MovieInfoSorter that uses an array with the Comparators to sort the data in multiple ways. Please do not start implementing your own code for custom classes and comparators until you fully understand the ones provided!

Submitting

Your submission requires that your answers to the questions are in README.md and that all required code and other file 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 100 points, which are distributed as follows: