95-771 Data Structures and Algorithms for Information Processing Summer 2004

Homework 1 Part A Due: Sept. 20, 2004

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 1 are as follows:

1. Study the IntArrayBag class that is found in Chapter Three of Main’s text.
2. Download the Java source code for this class from Main's web page. Place the source code in a directory consistent with the package “edu.colorado.collections”. See below for help with directories and packages.
3. Compile the IntArrayBag.java file producing an IntArrayBag.class file.
4. Write a small driver program that tests some of the IntArrayBag methods. This file must import the edu.colorado.collections package.
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)

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.java file.
7. The worst case run time for equals() must be O(n²) because your algorithm will execute less than c * (n + n-1 + n-2 + … + 1) constant time operations in the worst case. You will not use the countOccurrences() method in this code. Nor will you use arrayCopy or the clone method. All of these methods take time proportional to n. Note that since equals() is a member of the class it has access to any private members of the class. In other words, equals() has access to the private data of the implied object and the passed object.
8. The second method, toString(), will return a String object that represents the IntArrayBag. This will allow you to use an IntArrayBag object whenever a String object is expected. It should run in time proportional to the number of elements in the bag.
9. Download and install Michael Main’s EasyReader.java and FormatWriter.java classes. These are described in Appendix B of our text and will need to be placed in the directory edu/colorado/io. See below for help with directories and packages.
10. Modify the driver program 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);. Your driver will demonstrate this capability.
11. Modify the driver program in step 4 so that the EasyReader class is used to read integers from the keyboard. Your driver will build two different bags with those integers and then print them out using toString(). Your driver will compare the two bags with equals().
12. We are not using blackboard for submissions. Submit the following in a large envelope. (20 Points Each)

• A program listing of your final driver program. It will show calls on equals(), toString() and will use the edu.Colorado.io.EasyReader class.
• A printout of several DOS screens that demonstrate that your driver program works.
• A printout program listing of the modified IntArrayBag.java file.
• A listing of the javadoc documentation created after you modified the IntArrayBag. 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) where m and n are the sizes of the two bags 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

Using packages with the JDK on DOS and Windows

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 java file with the path

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

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, appears below.

// 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

*/