Transcript COMP 121 Week 7

COMP 121
Week 7: Object-Oriented
Design and Efficiency of
Algorithms
Objectives
To learn about the software life cycle
 To learn how to discover new classes and
methods
 To understand the use of CRC cards for
class discovery
 To be able to identify inheritance,
aggregation, and dependency relationships
between classes

Objectives (continued)
To learn to use UML class diagrams to
describe class relationships
 To learn how to use object-oriented design
to build complex programs
 To learn how to gauge the efficiency of an
algorithm

The Software Life Cycle
Encompasses all activities from initial
analysis until obsolescence
 Formal process for software development

 Describes
phases of the development process
 Gives guidelines for how to carry out the phases

Development process
 Analysis
 Design
 Implementation
 Testing
 Deployment
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Analysis
Defines what the project is suppose to do
 Is not concerned with how the program will
accomplish tasks
 Output of the Analysis Phase:

 Requirements
Document
Describe what program will do once completed
 Create user manual that tells how user will operate
program
 Establish performance criteria

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Design

Plans the system implementation
 Discover
the structures that underlie problem
to be solved
 Decide what classes and methods you need
 Output of the Design Phase:
Description of classes and methods
 Diagrams showing the relationships among the
classes

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Implementation

Write and compile the code
 Code
implements classes and methods
discovered in the design phase

Output of the Implementation Phase:
 The
completed program
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Testing
Run tests to verify the program works
correctly
 Output of the Testing Phase:

 A report
of the tests and their results
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Deployment
Users install program
 Users use program for its intended
purpose

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
The Waterfall Model
Sequential process of analysis, design,
implementation, testing, and deployment
 When rigidly applied, waterfall model does
not work well

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
The Waterfall Model
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
The Spiral Model
Breaks development process down into
multiple phases
 Early phases focus on the construction of
prototypes
 Lessons learned from development of one
prototype can be applied to the next
iteration
 Problem: can lead to many iterations, and
process can take too long to complete

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
The Spiral Model
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Extreme Programming
Strives for simplicity
 Removes formal structure
 Focuses on best practices

 Realistic
planning
 Small releases
 Metaphor
 Simplicity
 Testing
 Refactoring
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Extreme Programming

Focuses on best practices (continued)
 Pair
programming
 Collective ownership
 Continuous integration
 40-hour week
 On-site customer
 Coding standards
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Test-Driven Development
Test-Driven Development

The specific steps in test-driven development are:
 Create
a new test case
 Write enough code to fail the test
 Run the tests and watch the new test fail
 Write the simplest code that will pass the new test
 Run the tests and watch all the tests pass
 Remove duplication
 Rerun the tests
Test-Driven Development Detail
Object-Oriented Design
1.
2.
3.
Discover classes
Determine responsibilities of each class
Describe relationships between the
classes
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Discovering Classes
A class represents some useful concept
 Concrete entities: bank accounts, ellipses,
products, etc.
 Abstract concepts: streams, windows, etc.
 Find classes by looking for nouns in the
task description
 Define the behavior for each class
 Find methods by looking for verbs in the
task description

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Discovering Classes

Keep the following points in mind:
 Class
represents set of objects with the same
behavior



Entities with multiple occurrences in problem
description are good candidates for objects
Find out what they have in common
Design classes to capture commonalities
 Represent
some entities as objects, others as
primitive types

Should we make a class Address or use a String?
 Not
all classes can be discovered in analysis phase
 Some classes may already exist
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
CRC Card
CRC Card
 Describes a class, its responsibilities, and
its collaborators
 Use an index card for each class
 Pick the class that should be responsible
for each method (verb)
 Write the responsibility onto the class card
 Indicate what other classes are needed to
fulfill responsibility (collaborators)

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
CRC Card
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Relationships Between Classes
Inheritance
 Aggregation
 Dependency

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Inheritance
Is-a relationship
 Relationship between a more general
class (superclass) and
a more specialized class (subclass)
 Every savings account is a bank account

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Inheritance
Every circle is an ellipse (with equal width
and height)
 It is sometimes abused

the class Tire be a subclass of a
class Circle?
 Should

The has-a relationship would be more appropriate
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Aggregation
Has-a relationship
 Objects of one class contain references to
objects of another class
 Use an instance variable

 A tire
has a circle as its boundary:
class Tire
{
. . .
private String rating;
private Circle boundary;
}
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Example

Every car has a tire (in fact, it has multiple
tires)
class Car extends Vehicle
{
. . .
private Tire[] tires;
}
UML Notation for Inheritance and
Aggregation
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Dependency
Uses relationship
 Example: Many applications depend on
the Scanner class to read input
 Aggregation is a stronger form of
Dependency
 BlueJ only shows “Uses” relationships

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
UML Relationship Symbols
Relationship
Symbol
Line Style Arrow Tip
Inheritance
Solid
Triangle
Interface Implementation
Dotted
Triangle
Aggregation
Solid
Diamond
Dependency
Dotted
Open
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Class Diagram in BlueJ
Advanced Topic: Attributes and
Methods in UML Diagrams
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Aggregation and Association
Association is a more general relationship
between classes
 Used early in the design phase
 A class is associated with another if you
can navigate from objects of one class to
objects of the other
 Given a Bank object, you can “navigate” to
Customer objects

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Aggregation and Association
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Five-Part Development Process
Gather requirements
 Use CRC cards to find classes,
responsibilities, and collaborators
 Use UML diagrams to record class
relationships
 Use javadoc to document method
behavior
 Implement your classes

Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Discussion Question

How does this development process apply to
your lab assignments?
 Gather
requirements
 Use CRC cards to find classes, responsibilities, and
collaborators
 Use UML diagrams to record class relationships
 Use javadoc to document method behavior
 Implement
your code
Requirements

The requirements are defined in the lab
write-up that is handed out
 If
they are unclear, you should get clarification
from the customer (me!)

From the requirements, begin thinking
about the classes, responsibilities, and
relationships
 It
may be helpful to do this BEFORE you look
at the code that was provided
CRC Cards

Discover classes
 Most, if not all, classes are already determined
 Examine the classes that are supplied, and make
sure you understand how each relates to the nouns in
the requirements

Discover responsibilities
 Methods are included in the classes
 Relate the method names to the verbs
in the
requirements

Describe relationships
 Some
inheritance and dependency relationships are
already established
 Consider whether there are other relationships
between the classes besides those already
established
UML (In BlueJ)
UML Diagrams

Examine the inheritance relationships
 Think
about why that relationship exists
 Consider whether there are other inheritance
relationships that need to be added

Examine the dependency relationships
 Think
about why that relationship exists (looking at
the code can help)
 Consider whether there are other dependency
relationships that need to be added

Determine whether each relationship is an aggregation
(collaborator is stored as an object reference) or a simple
dependency (collaborator is a method parameter or a return
value)
 Consider
whether there are multiplicities which may
indicate the use of an array or other data structure
Javadoc

Examine the javadoc that is included with
the lab
 Consider
how the methods relate to the
responsibilities on the CRC cards
 Consider whether there are other methods
that should be included
Implementation

Implement the code using test-driven
development
Summary






The life cycle of software encompasses all activities from
initial analysis until obsolescence
The waterfall model describes a sequential process of
analysis, design, implementation, testing, and
deployment
The spiral method describes an iterative process in
which design and implementation are repeated
Extreme Programming is a methodology that strives for
simplification and focuses on best practices
In object-oriented design, you discover classes,
determine the responsibilities of the classes, and
describe the relationships between classes
A CRC card describes a class, its responsibilities, and its
collaborating classes
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Summary (continued)





Inheritance (the is-a relationship) is sometimes
inappropriately used when the has-a relationship
would be more appropriate
Aggregation (the has-a relationship) denotes
that objects of one class contain references to
objects of another class
Dependency is another name for the “uses”
realtionship
UML uses different notations for inheritance,
interface implementation, aggregation, and
dependency
Use javadoc comments to document the
behavior of classes
Horstmann, C. (2008). Big Java (3rd ed.). New York: John Wiley & Sons.
Any Questions?
Efficiency of Algorithms
Difficult to get a precise measure of the
performance of an algorithm or program
 Can characterize an algorithm by how the
execution time or memory requirements
increase as a function of the number of
data items that the algorithm processes

 Big-O

notation
A simple way to determine the big-O of an
algorithm or program is to look at the loops
and to see whether the loops are nested
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Common Growth Rates
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Growth Rates
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
How n affects Big-O
What is the big-O of this algorithm?
for (int i=0; i<n; i++)
for (int j=0; j<n; j++)
System.out.println(i + “ “ + j);
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
What is the big-O of this algorithm?
for (int i=0; i<n; i++)
for (int j=0; j<2; j++)
System.out.println(i + “ “ + j);
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
What is the big-O of this algorithm?
for (int i=0; i<n; i++)
for (int j=n-1; j>=i; j--)
System.out.println(i + “ “ + j);
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
What is the big-O of this algorithm?
for (int i=1; i<n; i++)
for (int j=0; j<i; j++)
if (j%i == 0)
System.out.println(i + “ “ + j);
Koffman, E.B. & Wolfgang, P.A.T. (2003). Objects, Abstraction, Data Structures, and Design Using
Java Version 5.0. New York: John Wiley & Sons.
Efficiency of Sorts and Searches

Big O is commonly used to characterize
sort and search algorithms
 Linear
Search
 Binary Search
 Bubble Sort
 Selection Sort
 Insertion Sort
 Merge Sort
Any Questions?