95-771 Data Structures and Algorithms Fall '01

Homework 0

Programming in Java

Part I. The Problem Description

This homework is designed to familiarize the student with the Java programming language and with the compilation and use of Java packages.

The steps to completing homework 0 are as follows:

1. Study the IntArrayBag class that is found in the Main text in chapter three.
2. Download the Java source code for this class from Main's web page.
3. Compile the IntArrayBag.java file producing an IntArrayBag.class file.
4. Write a small driver program that tests some of the IntArrayBag methods.
5. Modify the IntArrayBag class so that it contains two additional methods. The method signatures for these two methods are:

public boolean equals(IntArrayBag b) /* worst case run time O(m*n) where m and n are the size of the bags.*/

public String toString()

6. Using Main's documentation as a guide, write javadoc documentation for the two new methods and include this documentation in the IntArrayBag.java file. Run javadoc on the new IntArrayBag class.
7. Modify the driver program so that it tests the two additional methods. The first method, equals(), is described on page 168 of the Main text and your method will be written to the specification described there.
8. The second method, toString(), will return a String object that represents the IntArrayBag. This will allow you to use an IntArrayBag object where a String object is expected.
9. Modify the driver program a second time so that it makes use of the toString() method. For example, if your driver program has created an IntArrayBag object called myBag, then the toSring() method will be automatically called when you write System.out.println(myBag); .
10. Submit the following ( 20 Points Each):

• A program listing of your final driver program.
• A printout of the DOS screen that demonstrates that your driver program works.
• A program listing of the modified IntArrayBag class.
• A listing of the javadoc documentation created after you modified the IntArrayBag class. After viewing the documentation in your web browser, select File/Print. This documentation will show the signature, preconditions and postconditions of your equals() and toString() methods.
• A paragraph that describes why your equals() method is O(mn) and a paragraph that describes why your toString() method is O(n). You may assume that the string concatenation operator is a constant time operation.

Part II Some notes on using Java Packages under Windows '95

Using packages with JDK 1.2.1 under Windows '95

Downloading and Compiling IntArrayBag.java

Below are the specific steps that I used to compile and test Michael Main's

IntArrayBag class on my PC.

The IntArrayBag code was taken from Michael Main's "Data Structures and

other objects using Java".

The IntArrayBag code may be downloaded from the web site:

http://www.cs.colorado.edu/~main/

The files IntArrayBag.java and IntArrayBag.class were placed under the

directory

C:\edu\colorado\collections>

The file IntArrayBag.java file was compiled with the command

C:\edu\colorado\collections>javac IntArrayBag.java

Within the IntArrayBag.java file, the first line reads:

package edu.colorado.collections;

Notice that the package name corresponds to the directory structure.

This file containing my driver code is located at

C:\heinz\90-723\usebag\BagDemonstration.java

It was compiled with the command

C:\heinz\90-723\usebag>javac -classpath C:\ BagDemonstration.java

The C:\ specifies where the search should begin for the file

C:\edu\colorado\collections\IntArrayBag.class

The resulting .class file (BagDemonstration.class) was run with the

command

C:\heinz\90-723\usebag>java -classpath C:\;. BagDemonstration

The dot is required so that java will look in the current directory

as well as the C:\ directory for classes.

My Driver Code before I added equals() and toString() to IntArrayBag.java

// Test a few methods in the IntArrayBag class

import edu.colorado.collections.IntArrayBag;

public class BagDemonstration {

public static void main(String[] args) {

IntArrayBag ages = new IntArrayBag();

ages.add(89);

ages.add(76);

ages.add(55);

ages.remove(76);

ages.add(55);

ages.add(89);

System.out.println(ages.countOccurrences(89));

System.out.println(ages.countOccurrences(55));

System.out.println(ages.countOccurrences(7));

}

}

/* Output

2

2

0

*/