SUNY Geneseo Department of Computer Science
Csci 240, Spring 2007
Prof. Doug Baldwin
Due Tuesday, February 13
This exercise gives you a Java class that contains some bugs, and asks you to find and fix the bugs. The hope is that you will approach the algorithms in order to debug them in ways similar to how you would approach the algorithms in order to prove them correct. Even if you choose not to do this for debugging, you need to confirm your fixes by proving the corrected algorithms correct. The class you are given is an extension of the Java library's Vector class. This means that the class you are given is a also so-called "generic" class. While neither being an extension to Vector nor being generic are related to the bugs, you may find it helpful to know a little bit about both when reading the class.
The same ways of thinking about an algorithm that you use to prove that it is correct can be helpful in understand where a program is incorrect (i.e., where a bug is). For example, preconditions and postconditions essentially define what is required for an algorithm to be correct, and what the contract between the algorithm and its client is. Therefore, if in debugging a program you find that some method is called without its preconditions holding, you know that by definition there is a bug in the code that calls that method. Similarly, if you find that a method is called correctly (i.e., with all preconditions holding), but returns without establishing all its postconditions, then there is, again by definition, a bug somewhere in the method. These kinds of thinking can help you localize a bug within a program.
Furthermore, a correctness proof is to a large extent a step by step verification that an algorithm's steps lead to its postconditions. If you can trace through a program or method and see where its actual behavior departs from what a proof requires it to do, you have found a place where there is a bug. This idea is particularly applicable to recursive algorithms with inductive proofs: the inductive proof organizes thinking about the algorithm into specific parts -- a base case, an induction step, and induction hypothesis, etc. Each of these parts can be checked against the actual behavior of code -- does the code do what the proof expects in its base case? do recursive messages in the code actually solve smaller instances of the problem as the induction hypothesis requires? do the recursive messages return correct solutions to smaller problems, as expected by the induction step? does the code's recursive case build on these results in a manner that follows the proof?
For more information on preconditions and postconditions, see section 2.2 of our textbook, and the January 19 lecture. For more information on induction and its relation to recursion, see section 7.1 of the text, and the January 31, February 2, and February 5 lectures.
You are probably familiar with the idea that messages can have parameters, which are values that influence precisely what the message means. In Java and some other object oriented languages, it is also possible for classes to have parameters, which are types that influence precisely what the class represents. Such parameterized classes are called "generic classes" or "generics." The classic example of a generic class is one that represents a container for other objects, for example a list. One can easily imagine a class that defines what lists act like (e.g., they handle messages to insert a value into the list, to remove a value, etc.). However, one often wants to go further, and specialized a list class according to what type of data it can contain -- a list of integers vs a list of strings vs a list of orangutans, etc. These secondary types that define the things you can store in a list are classic examples of type parameters.
In Java, type parameters appear in angle brackets immediately after a class's name in its declaration. For example, a generic list class such as the one suggested above might have a declaration that starts
class List<E> {
...
}In this declaration, the name E represents a type. Think of the English translation of this declaration as being "the class that represents lists of Es." Such type names can be used anywhere (well, almost anywhere) a regular type name could be used. For example, if you wanted to ensure that a list of Es could only insert items of type E, and that only items of type E could be retrieved from it, the class declaration might continue thus:
class List<E> {
public void insert( E newItem ) {
...
}
public E retrieve() {
...
}
...
}When you create instances of generic classes, you indicate the actual types that type parameters will stand for in the instance's declaration. For example, to create two lists, one of strings and one of orangutans (assuming a Orangutan class already exists), you could write
List<String> myStrings = new List();
List<Orangutan> apes = new List();Notice that the constructor used to create instances does not have any type parameters, only the class name used to declare instances does.
A vector is basically a variable-length array, i.e., an object that contains other objects, which can be accessed by their position within the vector. Just as with arrays, positions are specified by integers, which range from 0 to one less than the length of the vector.
The Vector class is generic, with the type parameter specifying the type of objects that can be stored in a vector. Some of the most useful messages to objects of class Vector<E> are
int size()add( E x )x to the end of the vector. Note that this object must be an instance of whatever class the Vector was declared to hold (i.e., of the class represented by E in Vector<E>).add( int i, E x )x at position i in a vector.E elementAt( int i )i in a vector.For complete details of the Vector class, see the on-line documentation for the Java class library.
I have written a Java class definition that provides some extensions to the existing Vector class. You can find this class in the folder named "ExtendedVector" on the "OutBox" file server (the complete path is "/ComputerScience/baldwin/CSci240/ExtendedVector;" as with past folders from "OutBox," this one may well reach you read-only, but there are only 3 files in it and you can change your access to them, and to the folder itself, to "read and write").
My ExtendedVector class provides 3 major extensions to the existing Vector class: the ability to initialize a Vector from an ordinary array, the ability to count how many times a value appears in a Vector, and the ability to reverse a Vector. Comments in file "ExtendedVector.java" explain each of these in a little more detail. The class also provides a main method that exercises each of these abilities.
Unfortunately, as you will see if you try to run the main method, there are a number of bugs in my code. The algorithms for initializing a Vector, counting occurrences of a value in a Vector, and reversing a Vector each contain bug(s). All of these bugs are evident in the tests that main runs. Your job is to identify and fix these bugs.
After you have fixed the bugs, and the program runs its tests (and any additional ones you wish to add) correctly, further confirm that you have fixed everything by proving the algorithms for initializing a Vector, counting occurrences of a value in a Vector, and reversing a Vector correct.
I will grade this exercise in a face-to-face meeting with you. Make an appointment to meet with me at some time convenient for you, as long as that time is before the end of the due date above. Meetings only need to be 15 minutes long. You can make an appointment by signing up on the copy of my schedule on the bulletin board outside my office.
I would like to read and run your program during our meeting. To do this, you can either bring the program to my office on a laptop computer, or we can go to a lab during the meeting.
Please also bring written copies of your correctness proofs to the meeting.