Computer Science 136 Data Structures and Advanced Programming Williams College Fall 2005

Short Answers

Complete the following problems from the book and turn them in as a text file lab4.txt at the start of lab.

Lab Program

Do the laboratory at the end of Chapter 5. Come to lab with a sketch of what you plan to do to implement the sorting procedure in MyVector.

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 structure.Vector<T>
  

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

• In step 2, you are to write a sort method. The text says you may use any sort that you like, but you should use either merge sort or quicksort.
• Since we are using generic Vectors, your sort method's signature will be slightly different from what you see in the text:

  public void sort(Comparator<T> c)
  

  Think about how you will modify the algorithm to use Comparators instead of base types or Comparables. Section 5.8 of the text discusses Comparators, but note that Java 5's Comparators are generic, so you should declare your classes that implement Comparator to take the specific type that it is to be used to compare. For example:

  public class CastleComparator 
         implements java.util.Comparator<Castle> {
  ...
  }
  

  Thus, the compare method you write will take parameters (in this case) of type Castle. This means you will not need the casts you see in the text examples.

• Be sure to test your vector 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 two or three "interesting" sort processes. 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 may choose from the data files I have provided in the "labs/comparators" directory in the cs136 area on cortland or in my shared area on FreeBSD. See the README file there for more information. You may also use some other data that you find interesting. If you have ideas about this, check with me before or during lab to make sure it's a reasonable thing to do.

When you're finished, create and submit a tar file lab4.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 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.