95-771Data Structures and Algorithms for Information Processing Fall 2007

Homework1 Part A Due: Sept. 12, 2007

Topics:Bags, Introductory run time analysis, Documentation using JavaDoc

Part I. The ProblemDescription

This homework is designed tofamiliarize the student with the Java programming language and with thecompilation and use of Java packages.

The steps to completinghomework 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:

publicboolean equals(IntArrayBag b)

publicString 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 onusing Java Packages

Using packages with the JDK on DOSand Windows

Downloading and CompilingIntArrayBag.java

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

IntArrayBag class on my PC.

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

other objects using Java".

The IntArrayBag code may bedownloaded from the web site:

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

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

directory

C:\edu\colorado\collections

The file IntArrayBag.java file wascompiled with the command

C:\edu\colorado\collections>javacIntArrayBag.java

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

package edu.colorado.collections;

Notice that the package namecorresponds to the directory structure.

This file containing my driver codeis 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 searchshould 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 javawill look in the current directory

as well as the C:\ directory forclasses.

My Driver Code, before I addedequals() and toString() to IntArrayBag.java, appears below.

// Test a few methods in theIntArrayBag class

import edu.colorado.collections.IntArrayBag;

public class BagDemonstration {

public static void main(String[]args) {

IntArrayBag ages = newIntArrayBag();

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

*/