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:
- Study the IntArrayBag
class that is found in Chapter Three of Main’s text.
- 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.
- Compile the IntArrayBag.java
file producing an IntArrayBag.class file.
- Write a small driver program that tests some of the IntArrayBag methods. This file must import the edu.colorado.collections package.
- 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()
- 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.
- The worst case run time for equals() must be O(n2) 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.
- 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.
- 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.
- 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.
- 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().
- 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
*/