Computer Science 211
Data Structures

The lab is described at the end of Chapter 6 in Bailey.

Read Section 6.8 in the text to learn about Comparators. Come to our meeting with a brief description of the sort method that you will write, and ideas for some interesting data to use for the testing of your implementation.

Do the laboratory at the end of Chapter 6.

Please note the following clarifications, modifications, and explanations relating to the lab procedure outlined in the text:

• In step 1, you are asked to create an extension of structure.Vector called MyVector. Since we are using the generic version of the structure package, the class header for MyVector should look something like this:

  public class MyVector<T> extends structure5.Vector<T>
  

  Keep in mind that as an extension of structure5.Vector, methods of MyVector will have access to instance variables and methods declared as protected in the structure5.Vector implementation. Make good use of this fact!

  Important Note: The elementData array in structure5.Vector is declared as private rather than protected for type safety reasons. This means, unfortunately, that MyVector will not be able to access the array directly. Fortunately, Vector has methods that are almost as good as direct access to the array.

• In step 2, you are to write a sort method. The text says you may use any sort that you like, but to earn full credit you should use either merge sort or quicksort for your final version. (Use something simpler for testing if you wish and the use of a simpler sort in your final submission will result in only a small penalty.) The structure of the code will be very similar to what you have seen in our class and text examples, but you will need to modify it to use Comparators instead of base types or Comparables and to operate on the contents of your instance of MyVector.
• Be sure to test your sort method in MyVector thoroughly before going on to part 3 of the lab assignment.
• For part 3 of the lab procedure, write two applications. They should each work on a different data file and each should perform more than one "interesting" sort process. Both will use the same MyVector 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 5 unique Comparators in your submission.

  You may choose from the data files I have provided in the "labs/comparators" directory in the class shared area. See the README file there for more information. You may also use some other data that you find interesting.

Answer the thought questions at the end of the lab. Include your responses in the README file described below.

When you're finished, create a tar file lab3.tar that includes the following:

• Your well-documented source code for all Java files used, including MyVector.java, your classes that hold the data objects decide to work with, your Comparator classes, and your two applications.
• Any additional data files you choose to use, other than the ones provided.
• A README (plain text) file that describes what is in each Java file, describes the two applications you have chosen and what you are sorting and how for each example. Also include your answers to the two thought questions in the text in this README file.

Submit lab3.tar by emailing it to jteresco AT mtholyoke.edu as an attachment.

This lab assignment is graded out of 30 points. As in all labs, your grade includes 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 all of the classes you will submit. 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 grades are based on how well the different parts of your program meet the functionality requirements.