DATA STRUCTURES AND
ALGORITHMS
Introduction to Software
Design
Outline of Part I
The software challenge and the software life cycle
Activities of each phase of the software life cycle
Using top-down design and object-oriented design
Managing complexity:
Data abstraction
Procedural abstraction
Information hiding
Abstract data types:
Role in modeling
Implementing them with classes and interfaces
Chapter 1: Introduction to Software Design 2
The Software Challenge
Software is ...
Used for a long time
Updated and maintained
By people who did not write it
Initial specification may be incomplete
Specification clarified through extensive interaction
between user(s) and system analyst(s)
Requirements specification needed at the beginning
of any software project
Designers and users should both approve it!
Chapter 1: Introduction to Software Design 3
Things Change!
Users’ needs and expectations change
Use reveals limitations and flaws
Desire for increased convenience, functionality
Desire for increased performance
Environment changes
Hardware, OS, software packages (“software rot”)
Need to interact with clients, parent org., etc.
Law and regulations change
Ways of doing business
Style, “cool” factor
Chapter 1: Introduction to Software Design 4
The Software Life Cycle
Software goes through stages as it moves from initial
concept to finished product
The sequence of stages is called a life cycle
Must design and document software:
In an organized way for:
Understanding and ...
Maintenance (change) after the initial release
The maintainer is not necessarily the author!
... and even authors forget
... and no one can keep all details in mind at once
Chapter 1: Introduction to Software Design 5
Software Life Cycle Models:
The Waterfall Model
Simplest way to organizing activities in stages
Activities are:
Performed in sequence
Result of one flows (falls) into the next
The Waterfall Model is simple ... but unworkable
Fundamental flaw: Assumption that each stage can
and must be completed before the next one occurs
Example: User may need to see finished product to
express true requirements!
Chapter 1: Introduction to Software Design 6
Waterfall Model
Chapter 1: Introduction to Software Design 7
Waterfall Model (2)
Chapter 1: Introduction to Software Design 8
Other Software Life Cycle Models
Common theme among models: stages or cycles
Unified Model:
Cycles are called phases and iterations
Activities are called workflows
The four phases of the Unified Model:
Inception (Başlama)
Elaboration (Olgunlaşma)
Construction (Gerçekleştirme)
Transition (Geçiş)
Chapter 1: Introduction to Software Design 9
Other Software Life Cycle
Models (2)
Chapter 1: Introduction to Software Design 10
Software Life Cycle Activities
Activities essential for successful development:
Requirements specification
Architectural, component, & detailed designs
Implementation
Unit, integration, and acceptance testing
Installation and maintenance
Chapter 1: Introduction to Software Design 11
Software Life Cycle Activities Defined
Chapter 1: Introduction to Software Design 12
Software Life Cycle Activities (more)
Requirements Specification
System analyst works with users to clarify the
detailed system requirements
Questions include format of input data, desired
form of any output screens, and data validation
Analysis
Make sure you completely understand the problem
before starting the design or program a solution
Evaluate different approaches to the design
Chapter 1: Introduction to Software Design 13
Software Life Cycle Activities
(continued)
Design
Top-down: break system into smaller
subsystems
Object-oriented: identify objects and their
interactions
UML diagrams: tool to show interactions
between:
Classes (inside the system)
Classes and external entities
Chapter 1: Introduction to Software Design 14
Example of Top-Down: Stepwise Refinement
Chapter 1: Introduction to Software Design 15
Example of Object-Oriented:
Sequence Diagram
Chapter 1: Introduction to Software Design 16
Outline of Part I
The software challenge and the software life cycle
Activities of each phase of the software life cycle
Using top-down design and object-oriented design
Managing complexity:
Data abstraction
Procedural abstraction
Information hiding
Abstract data types:
Role in modeling
Implementing them with classes and interfaces
Chapter 1: Introduction to Software Design 17
Using Abstraction to Manage Complexity
An abstraction is a model of a physical entity or
activity
Models include relevant facts and details
Models exclude matters irrelevant to system/task
Abstraction helps programmers:
Complex issues handled in manageable pieces
Procedural abstraction: distinguishes ...
What to achieve (by a procedure) ...
From how to achieve it (implementation)
Data abstraction: distinguishes ...
Data objects for a problem and their operations ...
From their representation in memory
Chapter 1: Introduction to Software Design 18
Unified Modeling Language
Unified Modeling Language (UML) is a standard diagram notation for
describing a class
Field
signatures:
type and name
Method signatures:
name, argument Field Class
types, result type Class values name
name
Chapter 1: Introduction to Software Design 19
Modeling
Modeling is a way of thinking about the problems using models
organized around the real world ideas.
A modeling method comprises a language and also a procedure for
using the language to construct models.
modeling is the only way to visualize your design and check it against
requirements before your crew starts to code.
Refernces
http://www.omg.org/gettingstarted/what_is_uml.htm
http://www.inconcept.com/JCM/April1998/halpin.html
Introduction
What is UML?
• Is a language. It is not simply a notation for drawing
diagrams, but a complete language for capturing
knowledge(semantics) about a subject and expressing
knowledge(syntax) regarding the subject for the purpose
of communication.
• Applies to modeling and systems. Modeling involves a
focus on understanding a subject (system) and capturing
and being able to communicated in this knowledge.
• It is the result of unifying the information systems and
technology industry’s best engineering practices
(principals, techniques, methods and tools).
Refernces
www.sqae.com/UML.ppt
Unified Modeling Language (UML)
used for both database and software modeling
version 1.1 was adopted in November 1997 by the Object Management
Group (OMG) as a standard language for object-oriented analysis and
design
Initially based on a combination of the Booch, OMT (Object Modeling
Technique) and OOSE (Object-Oriented Software Engineering)
methods, UML was refined and extended by a consortium of several
companies, and is undergoing minor revisions by the OMG Revision
Task Force.
Ivar Jacobson is known as the father of Use Cases.
Refernces
http://www.inconcept.com/JCM/April1998/halpin.html
Use case diagrams
Use Case Diagrams
Use Case Diagrams describe the functionality of a system and
users of the system. These diagrams contain the following
elements:
• Actors, which represent users of a system, including human
users and other systems.
• Use Cases, which represent functionality or services provided
by a system to users.
High Level Use Case Diagram
Manage Resources
Resource Manager
Manage Projects
Project Manager
System Admin
System
Administrator
Managing Resources Use Case Diagram
Add Skill
Remove
Skill Find Skill
Update
Skill
Resource Manager Add
Resource
Find
Remove Resource
Resource
Update
Resource Unassign
Assign
Skill from Skill from
Resource Resource
Class Diagrams
Class Diagrams describe the static structure of a system, or how it is
structured rather than how it behaves. These diagrams contain the
following elements.
• Classes, which represent entities with common characteristics or
features. These features include attributes, operations and
associations.
• Associations, which represent relationships that relate two or more
other classes where the relationships have common characteristics or
features. These attributes and operations.
High-Level Resource Class Diagram
Skill
Resource-Skill
Resources
Salaried Hourly
Detailed Resource Class Diagram
Skill
Name: String
Desc: String
Create(): Skill
setName(): (Name:String)
getName(): String
setDesc(): (Desc:String)
getDesc(): String
destroy()
Resource Skill
Resource
Salaried Hourly
Sequence Diagrams
Sequence Diagrams describe interactions among classes. These
interactions are modeled as exchange of messages. These
diagrams focus on classes and the messages they exchange to
accomplish some desired behavior. Sequence diagrams are a
type of interaction diagrams. Sequence diagrams contain the
following elements:
• Class roles, which represent roles that objects may play
within the interaction.
• Lifelines, which represent the existence of an object over a
period of time.
• Activations, which represent the time during which an object
is performing an operation.
• Messages, which represent communication between objects.
Sequence Diagram
Activity Diagrams
Activity diagrams describe the activities of a class. These
diagrams are similar to statechart diagrams and use similar
conventions, but activity diagrams describe the behavior of a
class in response to internal processing rather than external
events as in statechart diagram.
• Swimlanes, which represent responsibilities of one or more
objects for actions within an overall activity; that is, they divide
the activity states into groups and assign these groups to
objects that must perform the activities.
• Action States, which represent atomic, or noninterruptible,
actions of entities or steps in the execution of an algorithm.
• Action flows, which represent relationships between the
different action states of an entity.
Activity Diagram
Abstract Data Types, and
Pre- and Post-conditions
A major goal of software engineering: write
reusable code
Abstract data type (ADT): data + methods
Names, parameters, return types of methods
No indication of how achieved (procedural
abstraction)
No representation (data abstraction)
A class may implement an ADT
Must provide bodies for all methods of the ADT
Chapter 1: Introduction to Software Design 33
Abstract Data Types, and
Pre- and Postconditions (2)
Chapter 1: Introduction to Software Design 34
Abstract Data Types, and Pre-
and Postconditions (continued)
An ADT is a contract between
The interface designer and ...
The coder of a class that implements the interface
Precondition: any assumption/constraint on
the method data before the method begins
execution
Postcondition: describes result of executing
the method
Chapter 1: Introduction to Software Design 35
Requirements Analysis:
Use Cases, and Sequence Diagrams
Analysis first step: study input and output requirements:
Make sure they are understood and make sense
Use case:
User actions and system responses for a sub-problem
In the order that they are likely to occur
Sequence diagram:
Shows objects involved across the horizontal axis
Shows time along the vertical axis
See next slide for an example; shows:
User, PDApplication, PhoneDirectory, BufferedReader,
PDUserInterface object + a number of method calls
Chapter 1: Introduction to Software Design 36
Sequence Diagram
Chapter 1: Introduction to Software Design 37
Design of Array-Based Phone
Directory (2)
Chapter 1: Introduction to Software Design 38
Outline of Part II
Categories of program errors
Throwing an exception:
What it means
How to do it
Why you should catch exceptions
A variety of testing strategies
How to write testing methods
Program verification: assertions and loop
invariants
Chapter 1: Introduction to Software Design 39
Program Defects and “Bugs”
An efficient program is worthless if it breaks or
produces a wrong answer
Defects often appear in software after it is
delivered
Testing cannot prove the absence of defects
It can be difficult to test a software product
completely in the environment in which it is
used
Debugging: removing defects
Chapter 1: Introduction to Software Design 40
Major Categories of Defects
Syntax and other in-advance errors
Run-time errors and exceptions
Logic Errors
Chapter 1: Introduction to Software Design 41
Syntax Errors
Syntax errors: grammatical mistakes in a
program
The compiler detects syntax errors
You must correct them to compile successfully
Some common syntax errors include:
Omitting or misplacing braces, parentheses, etc.
Misplaced end-of-comment
Typographical errors (in names, etc.)
Misplaced keywords
Chapter 1: Introduction to Software Design 42
Semantic Errors
Semantic errors: may obey grammar, but
violate other rules of the language
The compiler detects semantic errors
You must correct them to compile successfully
Some common semantic errors include:
Performing an incorrect operation on a primitive type
value
Invoking a member function not defined
Not declaring a variable before using it
Providing multiple declarations of a variable
Failure to include a library headder
Chapter 1: Introduction to Software Design 43
Run-time Errors or Exceptions
Run-time errors
Occur during program execution (run-time!)
Occur when the C++ run-time library detects an
operation that it knows to be incorrect
Cause program to halt execution
Examples of run-time errors include
Division by zero
Array index out of bounds
Null pointer reference
Chapter 1: Introduction to Software Design 44
Logic Errors
A logic error is programmer mistake in
the design of a class or method, or
the implementation of an algorithm
Most logic errors
Are not syntax or semantic errors: get by the
compiler
Do not cause run-time errors
Thus they are difficult to find
Sometimes found through testing
Sometimes found by users
Chapter 1: Introduction to Software Design 45
Avoiding Logic Errors
Work from a precise specification
Strive for clarity and simplicity
Consider “corner” / extreme cases
Have reviews / walk-throughs: other eyes
Use library/published algorithms where
possible
Think through pre/post conditions, invariants
Be organized and careful in general
Chapter 1: Introduction to Software Design 46
Ways to Indicate an Error
Return a special value
Use a bool return value to indicate success
or failure.
Set a global variable.
Print an error message.
Print an error message and exit the program.
Put an input or output stream in a fail state.
Throw an exception
Chapter 1: Introduction to Software Design 47
Outline of Part II
Categories of program errors
Throwing an exception:
What it means
How to do it
Why you should catch exceptions
A variety of testing strategies
How to write testing methods
Program verification: assertions and loop
invariants
Chapter 1: Introduction to Software Design 48
Throwing and Exception
Using special return values to indicate
errors can lead to complicated logic.
The error detection/recovery logic is
intermixed with the normal processing.
Using exceptions allows separation of
the error detection/recovery logic from
the normal processing logic.
Chapter 1: Introduction to Software Design 49
The throw statement
FORM:
throw expression;
EXAMPLES:
throw "The value of index is out of range";
throw std::out_of_range("The value of index is out of range");
MEANING:
The normal processing of execution is interrupted, control is transferred to the
nearest exception handler. An exception handler is like a function, the rules for
matching an exception handler are the same as for matching an overloaded
function. If the current function body contains no matching exception handler,
control is returned to the calling function, and a search is made from the point of
call. This process is repeated until a corresponding exception handler is found or
until the main function is reached. If no exception handler is found, then the
program terminates.
Chapter 1: Introduction to Software Design 50
Example using a throw
/** Gets the value in the element of array x with subscript
index.
@param index The subscript of the element to be retrieved
@return The value stored at x[index]
@throws A std::out_of_range exception if index is not in
range.
*/
int get_element_of_x(int index) {
if (index < 0 || index >= X_SIZE) {
throw std::out_of_range(
"In get_element_of_x, "
"the value of index is out of range");
}
return x[index];
} Chapter 1: Introduction to Software Design 51
Uncaught exceptions
If there is no exception handler, the program
execution is aborted.
The message depends on the compiler and operating
system.
The g++ compiler issues the message
Aborted
The Microsoft .NET C++ compiler issues the message
This application has requested the Runtime to
terminate it in an unusual way.
Please contact the application's support team
for more information.
Chapter 1: Introduction to Software Design 52
Catching and Handling
Exceptions
A try block encloses functions that may
throw an exception.
One or more catch blocks (exception
handlers) follow the try block.
try {
val = get_element_of_x(10);
}
catch (std::out_of_range& ex) {
std::cerr << "Out_of_range exception\n";
std::cerr << ex.what() << std::endl;
std::abort();
}
Chapter 1: Introduction to Software Design 53
Standard Exceptions
Standard Exception Reason Thrown Thrown by
bad_alloc Memory not available. The new operator.
bad_cast Attempt to cast a reference that is not of The dynamic_cast operator.
the target type.
bad_typeid Attempt to obtain the typeid of a null The typeid operator.
pointer or the default typeid object.
domain_error Function not defined for the input Not thrown by the C++ standard
value. library.
invalid_argument Invalid function argument. The bitset constructor.
length_error Attempt to create a string or vector that The string and vector classes.
is larger than the maximum allowed size.
out_of_range Index that is larger than size() The at operator in the string,
vector, and deque class.
ios_base::failure An error flag is being set that matches Input/output stream objects after an
one set by an earlier call to the erroneous input/output operaton.
exceptions function.
Chapter 1: Introduction to Software Design 54
Using Exceptions
By calling the exceptions function we can tell
the input/output stream to throw an
exception in some error cases, but not
others.
The statement:
cin.exceptions(ios_base::failbit);
will cause the istream cin to throw an
exception when it reads an incorrectly
formatted input.
Chapter 1: Introduction to Software Design 55
The function read_int
int read_int(const string& prompt) {
cin.exceptions(ios_base::failbit);
int num = 0;
while (true) { // Loop until valid input
try{
cout << prompt;
cin >> num;
return num;
} catch (ios_base::failure & ex) {
cout << "Bad numeric string -- try again\n";
cin.clear();
}
}
}
Chapter 1: Introduction to Software Design 56
Catching all Exceptions
try {
age = read_int("Enter your age ");
} catch (std::ios_base::failure &f) {
cerr << "Invalid number format input\n";
age = DEFAULT_AGE;
} catch (std::exception& ex) {
cerr << "Fatal error occurred in read_int;
cerr << ex.what() << '\n';
abort();
} catch (...) {
cerr << "Undefined exception occurred\n";
abort();
}
Chapter 1: Introduction to Software Design 57
Outline of Part II
Categories of program errors
Throwing an exception:
What it means
How to do it
Why you should catch exceptions
A variety of testing strategies
How to write testing methods
Program verification: assertions and loop
invariants
Chapter 1: Introduction to Software Design 58
Testing Programs
A program with
No syntax/semantic errors, and
No run-time errors,
May still contain logic errors
“Best” case is logic error that always
executes
Otherwise, hard to find!
Worst case is logic error in code rarely run
Goal of testing: Test every part of the code,
on “good” and “bad”/”hard” cases
Chapter 1: Introduction to Software Design 59
Structured Walkthroughs
Most logic errors:
Come from the design phase
Result from an incorrect algorithm
Logic errors sometimes come from typos that
do not cause syntax, semantic, or run-time
errors
if (0 <= x <= 10) { ... }
One way to test: hand-trace algorithm
before implementing!
Thus: Structured Walkthroughs
Chapter 1: Introduction to Software Design 60
Structured Walkthroughs (2)
The Designer:
Explains the algorithm to other team members
Simulate its execution with them looking on
The Team:
Verifies that it works
Verifies that it handles all cases
Walkthroughs are helpful, but do not replace testing!
Chapter 1: Introduction to Software Design 61
Testing Defined
Testing:
Exercising a program under controlled conditions
Verifying the results
Purpose: detect program defects after
All syntax/semantic errors removed
Program compiles
No amount of testing can guarantee the
absence of defects in sufficiently complex
programs
Chapter 1: Introduction to Software Design 62
Levels of Testing
Unit testing: checking the smallest testable
piece
A method or class
Integration testing:
The interactions among units
System testing: testing the program in
context
Acceptance testing: system testing intended
to show that the program meets its functional
requirements
Chapter 1: Introduction to Software Design 63
Some Types of Testing
Black-box testing:
Tests item based only on its interfaces and
functional requirements
Assumes no knowledge of internals
White-box testing:
Tests with knowledge of internal structure
Chapter 1: Introduction to Software Design 64
Preparing to Test
Develop test plan early, in the design phase
How to test the software
When to do the tests
Who will do the testing
What test data to use
Early test plan allows testing during design &
coding
Good programmer practices defensive
programming
Includes code to detect unexpected or invalid data
Chapter 1: Introduction to Software Design 65
Testing Tips for Program
Systems
Program systems contain collections of
classes, each with several methods
A method specification should document
Carefully document:
Each method parameter
Each class attribute (instance and static variable)
As you write the code!
Chapter 1: Introduction to Software Design 66
Testing Tips for Program
Systems (2)
Trace execution by displaying method name as you
enter a method:
#define TRACING
...
int compute_weight (...) {
#ifdef TRACING
cerr << "Entering compute_weight\n";
#endif
. . .
}
Chapter 1: Introduction to Software Design 67
Testing Tips for Program
Systems (3)
Display values of all input parameters on entry:
int compute_weight (float volume,
float density) {
#ifdef TRACING
cerr << "Entering computeWeight";
cerr << "volume = " << volume;
cerr << "density = " << density << '\n';
#endif
...
}
Chapter 1: Introduction to Software Design 68
Testing Tips for Program
Systems (4)
Display values of any class data members
(instance and static) accessed by the method
Display values of all method outputs at
point of return from a method
Plan for testing as you write each module,
Not after the fact!
Chapter 1: Introduction to Software Design 69
Developing Test Data
Specify test data during analysis and design
For each level of testing: unit, integration, and system
Black-box testing: unit inputs ⇒ outputs
Check all expected inputs
Check unanticipated data
White-box testing: exercise all code paths
Different tests to make each if test (etc.) true and false
Called coverage
Chapter 1: Introduction to Software Design 70
Developing Test Data (2)
Helpful to do both black- and white-box
testing
Black-box tests can be developed early
since they have to do with the unit
specification
White-box tests are developed with detailed
design or implementation: need code
structure
Chapter 1: Introduction to Software Design 71
Testing Boundary Conditions
Exercise all paths for
Hand-tracing in a structured walkthrough
Performing white-box testing
Must check special cases:
boundary conditions
Examples:
Loop executes 0 times, 1 time, all the way to the end
Item not found
Chapter 1: Introduction to Software Design 72
Who does the testing?
Normally testing is done by
The programmer
Team members who did not code the module
Final users of the product
Programmers often blind to their own oversights
Companies may have quality assurance groups
Extreme programming: programmers paired
One writes the code
The other writes the tests
Chapter 1: Introduction to Software Design 73
Stubs for Testing
Hard to test a method or class that interacts
with other methods or classes
A stub stands in for a method not yet
available
The stub:
Has the same header as the method it replaces
Body only displays a message that it was called
Sometimes you need to synthesize a
reasonable facsimile of a result, for the caller
to continue
Chapter 1: Introduction to Software Design 74
Drivers
A driver program:
Declares necessary instances and
variables
Provides values for method inputs
Calls the method
Displays values of method outputs
Chapter 1: Introduction to Software Design 75
Using a Testing Framework
Testing framework: software that
facilitates:
Writing test cases
Organizing the test cases into test
suites
Running the test suites
Reporting the results
Chapter 1: Introduction to Software Design 76
Integration Testing
Larger components: collection of classes
Done with smaller collection, then larger
ones
Drive with use cases: scenarios with
Sample user inputs
Expected outputs
Can be challenging to automate
Chapter 1: Introduction to Software Design 77
Outline of Part II
Categories of program errors
Throwing an exception:
What it means
How to do it
Why you should catch exceptions
A variety of testing strategies
How to write testing methods
Program verification: assertions and loop
invariants
Chapter 1: Introduction to Software Design 78
Reasoning about Programs:
Assertions and Loop Invariants
Assertions:
Logical statements about program state
Claimed to be true
At a particular point in the program
Written as a comment, OR use assert statement
Preconditions and postconditions are
assertions
Loop invariants are also assertions
Chapter 1: Introduction to Software Design 79
Reasoning about Programs:
Loop Invariants
A loop invariant:
Helps prove that a loop meets it specification
Is true before loop begins
Is true at the beginning of each iteration
Is true just after loop exit
Example: Sorting an array of n elements
Sorted(i): Array elements j, for 0 ≤ j < i, are sorted
Beginning: Sorted(0) is (trivially) true
Middle: We insure initial portion sorted as we
increase i
End: Sorted(n): All elements 0 ≤ j < n are sorted
Chapter 1: Introduction to Software Design 80
