1




COLLEGE OF ENGINEERING AND APPLIED SCIENCES
DEPARTMENT OF COMPUTER SCIENCE
CSI403 Design and Analysis of Algorithms

Homework 2 Created by Qi Wang
Click here for the recording.
Table of Contents
Part I: General project information ……………………………………………………………………………………… 02
Part II: Project grading rubric……………………………………………………………………………………………….. 02
Part III: Examples on how to complete a project from start to finish …………………………………… 03
Part IV: A. How to test a software design?.................................................................................05
B. Project description ……………………………………………………………………………………………….06


2

Part I: General Project Information
1. In this homework/programming assignment, you will practice the topics that are discussed in module II.
You should study the relevant materials before completing the homework.
2. All work is individual unless it is notified otherwise.
3. Absolutely NO hard copies or e-mail submissions or late work will be accepted.
4. Documents to be submitted as a zipped file:
• UML class diagram(s) – created with Violet UML or StarUML
• Java source file(s) with Javadoc style inline comments – (Java classes created with eclipse.)
• Supporting files if any (For example, files containing testing data.)

Students are required to submit a design, all error-free source files with Javadoc style inline comments,
and supporting files. Lack of any of the required items will result in a really low credit or no credit.
5. Two attempts will be allowed on Blackboard. Only the last attempt will be graded.
6. Work will be rejected with no credit if
a. The work is late.
b. The work is not submitted properly (wrong files, not in required format, etc.). For example,
i. The submitted file can’t be opened.
ii. The submitted work is empty or wrong work.
iii. Other issues.
c. The work is a copy or partial copy of others' work (such as work from another person or the
Internet).
7. Your TA will grade, and then post the feedback and the grade on Blackboard if you have
submitted it properly and on time. If you have any questions regarding the feedback or the grade,
please reach out to the TA first. You may also contact the instructor for this matter.

Part II: Project grading rubric

Components Max points
UML Design (See an example in part II.) Max. 15 points
Javadoc Style Inline comments (See an example in part II.) Max. 15 points
The rest of the project Max. 70 points

All projects will be evaluated based upon the following software development activities.
Analysis:
• Does the software meet the exact specification / customer requirements?
• Does the software solve the exact problem?
Design:
• Is the design efficient?
Code:
• Are there errors?
3

• Are code conventions followed?
• Does the software use the minimum computer resource (computer memory and processing
time)?
• Is the software reusable?
• Are comments completely written in Javadoc style?
a. Class comments must be included in Javadoc style before a class header.
b. Method comments must be included in Javadoc style before a method header.
c. More inline comments must be included in either single line format or block format
inside each method body.
d. All comments must be completed in correct style such as tags, indentation etc.
Debug/Testing:
• Are there bugs in the software?
Documentation:
• Complete all documentations that are required.

Part III: Examples on how to complete a project from start to finish
To complete a project, the following steps of a software development cycle should be followed. These steps
are not pure linear but overlapped.
Analysis-design-code-test/debug-documentation.
1) Read project description to understand all specifications(Analysis).
2) Create a design (an algorithm for method or a UML class diagram for a class) (Design)
3) Create Java programs that are translations of the design. (Code/Implementation)
4) Test and debug, and (test/debug)
5) Complete all required documentation. (Documentation)

The following shows a sample design. The corresponding source codes with inline Javadoc style comments are
included on next page. How to test/debug a software is included on the following pages.




4



import java.util.Random;

/**
* Representing a dog with a name.
* @author Qi Wang
* @version 1.0
*/
public class Dog{
/**
* The name of this dog
*/
private String name;


/**
* Constructs a newly created Dog object that represents a dog with an empty name.
*/
public Dog(){
this("");
}
/**
* Constructs a newly created Dog object with a name.
* @param name The name of this dog
*/
public Dog(String name){
this.name = name;
}

/**
* Returns the name of this dog.
* @return The name of this dog
*/
public String getName(){
return this.name;
}

/**
* Changes the name of this dog.
* @param name The name of this dog
*/
public void setName(String name){
this.name = name;
}

/**
* Returns a string representation of this dog. The returned string contains the type of
* this dog and the name of this dog.
* @return A string representation of this dog
*/
public String toString(){
return this.getClass().getSimpleName() + ": " + this.name;
}


/**
* Indicates if this dog is "equal to" some other object. If the other object is a dog,
* this dog is equal to the other dog if they have the same names. If the other object is
* not a dog, this dog is not equal to the other object.
* @param obj A reference to some other object
* @return A boolean value specifying if this dog is equal to some other object
*/
public boolean equals(Object obj){
//The specific object isn’t a dog.
if(!(obj instanceof Dog)){
return false;
TAB
TAB
TAB
open {
open {
TAB
Class comments must be written in Javadoc format before
the class header. A description of the class, author
information and version information are required.
More inline comments can be included in
single line or block comments format in a
method.
Comments for fields are required.
Method comments must be written in Javadoc format
before the method header. the first word must be a
capitalized verb in the third person. Use punctuation
marks properly.
A description of the method, comments on
parameters if any, and comments on the return type
if a y are required.
A Javadoc comment for a formal parameter consists of
three parts:
- parameter tag,
- a name of the formal parameter in the design ,
(The name must be consistent in the comments and the
header.)
- and a phrase explaining what this parameter specifies.
A Javadoc comment for return type consists of two parts:
- return tag,
- and a phrase explaining what this returned value specifies

5

}

//The specific object is a dog.
Dog other = (Dog)obj;
return this.name.equalsIgnoreCase(other.name);
}
}

Part IV:
A. How to test a software design?
There can be many classes in a software design.
1. First, create a UML class diagram containing the designs of all classes and the class relationships (For example,
is-a, dependency or aggregation).
2. Next, test each class separately.
Convert each class in the diagram into a Java program. When implementing a class, a driver is needed to test
each method included in the class design. In the driver program,
i. Use the constructors to create instances of the class(If a class is abstract, the members of the class will
be tested in its subclasses.). For example, the following creates Dog objects.
Create a default Dog object.
Dog firstDog = new Dog();
Create a Dog object with a specific name.
Die secondDog = new Dog(“Sky”);

ii. Use object references to invoke the instance methods. If an instance method is a value-returning
method, call this method where the returned value can be used. For example, method getName can
be called to return a copy of firstDog’s name.
String firstDogName;
…
firstDogName = firstDog.getName();

You may print the value stored in firstDogName to verify.

iii. If a method is a void method, invoke the method that simply performs a task. Use other method to
verify the method had performed the task properly. For example, setName is a void method and
changes the name of this dog. After this statement, the secondDog’s name is changed to “Blue”.
secondDog.setName(“Blue”);

getName can be used to verify that setName had performed the task.

iv. Repeat until all methods are tested.

• And then, test the entire design by creating a driver program and a helper class of the driver program.
i. Create a helper class. In the helper class, at minimum three static methods should be included.
public class Helper{

//method 1
public static void start(){
This void method is decomposed.
It creates an empty priority list.
It calls the create method with a reference to the list passed to the method.
And then, it calls the display method with a reference to the list passed to the method.
}

//method 2
public static returnTypeOrVoid create(a reference to a list) {
6

This method creates objects using data stored in a testing data file and store them into
the list.
}

//method 3
public static returnTypeOrVoid display(a reference to a list) {
This method displays the list of objects.
}
}

ii. Create a driver program. In main of the driver program, call method start to start the entire testing
process.

public class Driver{
public static void main(String[] args){
Helper.start();
}
}

Notice that the driver and its helper class are for testing purpose only. They should not be included in the design
diagram. But you will need to submit their source codes.

B: Project description
Design a generic ADT Priority Queue which is implemented with a generic ADT Heap, and use it store comparable
objects of any type. For example, a priority queue can be used to store a set of employees, students or bank accounts.

Employee and its comparators: (Note: these classes are needed for testing the generic ADT Priority Queue and the
generic ADT Heap that will be discussed later.)
An ADT Priority Queue can be used to store comparable objects of any type according to their priority. By default, the
priority is determined by objects’ natural ordering. Default priority can be overridden by a Comparator provided when a
queue is constructed.
Let’s use Employee as an example. Assume that each employee object contains two unique values:
• name: a full name in a format as in “John Smith”.
• pay rate: a numeric value indicating the annual income of an employee.
Assume we store a list of employees using an ADT priority queue according to their names or their pay rates. Therefore,
we need to create two comparators.
• A name comparator: compares/sorts employees by their names.
• A pay rate comparator: compares/sorts employees by their pay rates.
To organize employees in a priority queue, we first create an empty priority queue with a reference to a comparator
passed into the constructor as the ordering for the queue (more accurately for the heap that is used to implement the
queue. We will discuss heap later.). And then, insert the employees into the queue according to their priority defined in
the comparator.
name pay rate name pay rate
James Butt 30000.00 Leota Dilliard 10000.00
Josephine Darakjy 4500.00 Sage Wieser 32000.00
Art Venere 12000.00 Kris Marrier 30030.00
Lenna Paprock 500.00 Minna Amigon 3000.00
Donette Foller 30005.00 Abel Maclead 1000.00
7

Simona Morasca 30060.00 Mitsue Tollner 90000.00
Kiley Caldarera 2000.00 Graciela Ruta 100.00

Note: These data can be used in the testing phase for this project. Save them into a plain text file.
If the comparator compares employee names, the name in the root of a heap is greater than the names of its children. If
the comparator compares employee pay rates, the pay rate in the root of a heap is greater than the pay rates of its
children.
To use Employee to test this project, we need to design three classes.
• Employee
• A name comparator for employee, a class implementing the interface java.util.Comparator.
• A pay rate comparator for employee, a class implementing the interface java.util.Comparator.

Let’s discuss how to design a generic ADT priority queue and implement it with a generic ADT Heap so that objects of
any types can be stored in a priority queue.

ADT Heap and ADT Priority Queue:
Note: It is required to complete the entire design in the UML standards. The following shows a draft of the ADT Priority
Queue and ADT Heap Design excluding exceptions.






















A generic ADT Priority queue can be designed and implemented with a generic ADT heap, another abstract data type. In
this project, you are required to design a generic ADT heap that uses an array list, as the data structure, to store a list of
8

objects, such as a list of employees. It is not allowed to use any other Java ADTs/JFC Collection types in the java library.
A generic ADT Priority Queue contains a reference to a generic ADT Heap.

A generic ADT Heap should contain the following operations. When designing a method, you should consider all possible
exceptions.
• insert: inserts an item into a heap.
• delete: retrieves and removes the item in the root of a heap.
• heapify: rebuild a heap if the root is not a leaf and the root’s priority/key is less than the larger of the keys of the
root’s children.
• isEmpty: determines if a heap is empty.
• sort: sorts the items in a heap using the Heap Sort algorithm.
• more

When implementing the generic ADT Heap, two attributes should be included.
• an array list must be used as data structure.
 It is not allowed to use any other Java ADTs/JFC Collection types in the java library.
• A reference to a comparator specifying the ordering used for organizing a list of objects in a heap.

A generic ADT Priority Queue contains a reference to a generic ADT Heap and execute most of the following operations
in the heap. When designing a method, you should consider all possible exceptions.
• insert: inserts an item into a heap. This method should invoke insert of the heap.
• delete: retrieves and removes the item in the root of a heap. This method should invoke delete of the heap.
• isEmpty: determines if the heap is empty. This method should invoke isEmpty of the heap.
• sort: sorts the items in the heap using the Heap Sort algorithm. This method should invoke sort of the heap.
• more

Test:
To test the entire project, write a driver with a helper class that creates an empty priority queue, inserts a list of
employees, sorts the queue, deletes from the queue, and displays the queue. The following provides you with some
ideas.
• Create a helper class. In the helper class, at minimum three static methods should be created.
public class Helper{

public static void start(){
Create an empty priority queue and save its reference.
Pass the reference to create method.
Pass the reference to display method.
Sort the queue.
Display the queue again.
Delete from the queue.
Display the queue again.
}

public static returnTypeOrVoid create(a reference to a queue) {
Make employee objects from the testing data in a file.
Insert the employee objects into the queue.
}

9

public static returnTypeOrVoid display(a reference to a queue) {
Displays objects in the queue.
}
}

• Create a driver program. In main of the driver program, call method start to start the entire testing process.

public class Driver{
public static void main(String[] args){
Helper.start();
}
}
Make sure that all methods are tested. You may add ore program statements in the method start.

Notice that the driver and its helper class are for testing purpose only. They should not be included in the design
diagram. But you need to submit their source codes.

Have Fun!

欢迎咨询51作业君