California State University, Chico
Department of Computer Science
CSCI 311 Web-archive course
Instructor: Anne Keuneke Data Structures and Algorithms in Java
Assignment #2 Weight 100 points
GENERAL DESCRIPTION In this assignment we will develop a methodology
for evaluating the performance of programs and use it to compare
various implementations of a function Range (again). The focus
on lab 2 is objects and their manipulation. Documentation should
include a structure chart, a specification of the ADTs and program
documentation.
THE MODULES TO BE PROVIDED BY JAVA First thought: Look at the API for
java.lang.Double, java.lang.Float, java.lang.Integer. These are object
wrappers to take primitive data objects and make them objects
(so they can be passed by reference). What is the problem in this
for this lab? (see below) DO see java.lang.Thread and java.util.Vector
and java.util.ArrayList.
THE MODULES WHICH CAN BE REUSED Timer, ReportGenerator, Counter which were
implemented in Assignment can be reused for Assignment 2.
THE MODULES TO BE IMPLEMENTED Note: I have changed the DataGenerator
specs for the second lab. Included are formal descriptions of the ADTs
interfaces. Each ADT is a separately compiled module (class). Note
that these specifications are not complete ADT specifications; they
describe the ADTs in a ``stylized'' format, giving only suggested
declarations and operation parameter lists. The semantics of the
various operations have been specified in the lectures. A part of
your assignment is to complete the ADT specifications by describing
the Elements, the Structure and the Pre-conditions and Post-conditions
for each operation.
DESCRIPTION For Lab 1, in order to get random data, you simply
filled an array of real variables with uniformily distributed real
numbers (or integers) returned by the pre-defined Java class that
generates random numbers. In Lab 2 we will also work with Vectors (or ArrayList)
(both grow dynamically) and individual objects using concurrent Threads.
LAB2: GenerateVector( type, size) : Vector (or ArrayList);
{Returns a Vector of random elements}
LAB2: GenerateObjectSet ( Type, size) : ObjectType;
{Returns an Object of the type Type, which (recursively)
points to the next element in the set}
You can use the same technique (Technique 1:Lab 1) to initially generate the elements, but
for the Vector/ArrayList (filled with Objects) (Technique 2), you might need to use the Java provided
data type wrapper classes. Finally, for the array of objects (Technique 3), each object
has an Instance Variable (IV) which points to the next Object. Here we think of the
linkage of objects as an "abstract" linked list - each points to
the next element in the list.
Calculations to be performed:
Part I
Time the following (obviously the same number of elements, but the vector
should be dynamically allocated.)
Generation of an array of random values
Generation of a vector of Objects of random values
Generation of an array of Objects of random values
(Objects with IVs pointing to next)
(this is both time for generation of the list and its array)
Part II
For this lab, the focus is on alternative algorithms given the
different data structures that hold the data. Three new methods
should be provided and timed in the RangeFinder:
One which is passed a vector (any "range" algorithm you want)
One which is passed a single Object (others linked via IVs)
and uses the "obvious" range method
One which is passed an array of Objects and uses threads
and a synchronized method
(concurrency: this is why we want to know the entire array of objects)
DELIVERABLES
The deliverables include program listings (again, on line), documentation
(as specified above - both in code and charts) and (obviously) formatted
output.
Comment on sources of errors in your measurements and try to correct for them.
Also explain any unusual or unexpected results to the best of your ability.
Edited modules from Lab 1
ADT DataGenerator; A Random set generator module.
INSTANCE VARIABLE
GeneratedSet {Object being generated}
{Imported Operations}
ADT Random
{Exported Operations}
GenerateVector( type, size) : Vector;
{Returns a Vector of random elements}
GenerateObjectSet ( Type, size) : ObjectType;
{Returns an Array of Objects of the type Type,
each of which points to the next element in the set}
ALREADY DONE: GenerateArray( type, size) :array
{Returns an Array of random elements}
ADT RangeFinder; A module to determine the range of various sets of data.
INSTANCE VARIABLE
GeneratedSet {Array of numbers: Used in Lab 1 to find the Range }
GeneratedSetB {For Lab 2, this might be different data structure(s)}
RangeValue
{Exported Operations}
RangeVector( Vector)
RangeObjectLinked (ObjectType)
RangeObjectConcurrent (ArrayofObjectType)
ALREADY DONE:RangeArrayRecursion( array)
ALREADY DONE: RangeArraySimple (array)
Information which might change how you implement your ADTs
1) Wrapper classes: java.lang.Integer, etc., are final
so what?
2) Vectors hold objects
3) Look at how sloppy these "classes" are getting ...
** To have a better OO design, you should consider breaking up the
RangeFinder module into classes holding particular data structures
(arrays, Vectors, ArrayLists, linked-objects) and have each of these
classes define their own Range method. This would allow polymorphism
and would make it easier for your Timer class. (I.e., if each was its
own type of class, then you could call instance.Range() in Timer
since Java will know what class the instance belongs to.)
Since the creation of the structures (arrays, vectors, linked-objects)
also varies depending on the particular structure, each could have its own
operations for this as well.
Consider the following:
ADT VectorKeeper; A module to manipulate Vectors
(of random number objects)
{Imported Types}
Object, Vector ...
INSTANCE VARIABLE
GeneratedVector
RangeValue
{Exported Operations}
Create() // dynamically
Create(size) // given the expected vector length
Range() //* Java knows the arg is a Vector
since it is in this class
ADT ObjectLinkKeeper; A module to manipulate linked Objects
{Imported Types}
Object, Thread...
INSTANCE VARIABLE
GeneratedObjectArray // this could be generated by following the links
FirstObject
RangeValue //* should be the same for whichever structure!
might want to test this and blow up if it doesn't :-)
{Exported Operations}
Create(size) // creates the linked-list of objects (size n) and
// stores the first object in the IV FirstObject
CreateArray() //* uses FirstObject to generate an array
(to use for concurrency)
RangeObjectLinked() // uses FirstObject to start out
RangeObjectConcurrent() // uses the GeneratedObjectArray
OR
Range(Type) //* depending upon the Type of the object
passed (an Object or an Array) the
correct method for Range is used
Note: these classes Create() and Range() methods illustrate that
RangeFinder and DataGenerator were rather particular to a
specific data structure (arrays) and we may not want to "reuse" it.
The new objects will still all need to use random numbers, but then
different actions are taken to truly "generate" the data for the various
structures... and clearly the Range() methods will vary. Hopefully,
these two labs illustrate some important shifts in object-oriented
programming. The focus should be on objects, not on procedures.
The idea of polymorphism allows us to have many objects with the
same method types but all of the important information will be
located in the object and thus does not need to be passed around.
I hope you will excuse the "sloppy" use of these classes in lab 1;
I believe that by actually doing it in these two ways, one gets a
better grasp and appreciation of the differences and the beauty of
pure object-oriented techniques.
Finally, some hints on threads:
One purpose of this lab is to give you experience with concurrency.
However, this is not the best choice of labs since we are talking about
sets of size 1000 spawning threads. That is a lot of threads!
There are two alternatives you may use (you can use both of them) to make
this more reasonable (many of your systems will really balk at this
many threads)
1) break the sets of Objects into parts. For example,
for n = 100, break it into 10 parts. For each part,
do an obvious range to get a local minimum and maximum,
THEN, given these local values, let each of these subparts
spawn a thread to find the global minimum and maximum
2) change the priority of some threads (see Tips for labs)
Also, make sure to check out about threads and join ing
them to the main thread. Lab 2 info