Algorithm Design
2
C H A P T E R
2.1 HOW TO DESIGN A N ALGORITHM
Algorithm design is more akin to an art than a science. Supply 100
programmers with the identical specification and, in return, you will receive
100 different solutions. T h e process is largely subjective, and the
notion of good or bad can also be application specific (i.e., a program
considered a good solution in one environment might be unsuitable
in another.)
However, we are not completely on our own in this matter. There
are general guidelines that we can follow and a broad notion of
what is considered good programming practice. Throughout this text,
our discussions of individual algorithms provide specific insights
into the design process; the sections that follow serve as an introduction
to the topic.
Understand the Problem
T h e first step in algorithm design is to understand the problem. This
is called the requirements analysis phase. However obvious this
might appear now, all readers of this book will, at one time or another,
12
2.1 How to Design an Algorithm 13
a program that they think solves a particular problem-only to find
out later that their efforts were wasted because they solved the wrong
problem. Gather data, speak to users, carefully review any written
requirements. In short, try to ensure that you have all the information
you need before you start to design and code an application.
Data Structures
T h e next step is to design the data structures. This is a critical part
of the development process and the one most often overlooked
by even the most experienced programmers. A correctly designed data
structure will suggest the design of the definitive algorithm and
yield a simple, easily maintainable program. In contrast, choosing a
clumsy or inappropriate data structure will produce code that is unreadable
and difficult to maintain.
Subsequent chapters of this book will introduce some very sophis-
ticated data structures. However, you should already be familiar with the
more common data types provided with most languages (e.g., integers,
characters, arrays, etc.). A trivial example of an incorrect choice of
a data structure is using individual variables to process the test results
of a computer science class. It would be more appropriate to use
an array.
After they have been designed, we need to verify the appropriate-
ness of our data structures. One way to do this is to ask users to supply
a number of questions andlor updates that they would like your pro-
gram to support. You can then manually apply the questions against your
design and judge how well your data structures respond to these user
requirements. Modify your design as necessary.
Pseudo-Code
T h e next phase of the development process is to formulate or sketch
the algorithm in pseudo-code. Each pseudo-code statement de-
scribes tasks that the programmer will implement using one or more
host (real) language statements. T h e level of detail represented by each
pseudo-code statement can vary, and programmers develop individual
styles that reflect personal preference or need. T h e use of pseudo-code
14 2 Algorithm Design
while( more employee input
if( salaried )
calculate tax;
calculate fica;
else
determine hours ;
overtime hours;
get hourly rate;
listing 2.1 print check;
Pseudo-code
example.
allows programmers to design and analyze algorithms without becom-
ing entangled in syntactic detail. Listing 2.1 contains an example.
Analysis
T h e next phase in the development is analysis. We can divide this
phase into three steps. First, we must determine whether our solution
seems feasible with respect to memory requirements, performance
constraints, ease of use, etc. Second, we should review and validate
the pseudo-code description of our algorithm. Obviously, these are
both manual procedures at this point because we have not, as yet, written
any (compilable) code.
T h e third step is to perform an analysis of the complexity of the
algorithm. Complexity in this sense does not refer to the relative
difficulty of understanding the program; rather, it is a measure of the
amount of work performed by the executing function. This type of analysis
is especially useful when there are two or more solutions available and
we wish to select only one for implementation.
In determining complexity, it would appear useful to have the
actual execution times available for each function. Obviously, this
is not possible because we have not, as yet, performed any actual
coding. Moreover, the very point of this exercise is to eliminate
the need to develop, implement, and test more than one algorithm.
Furthermore, performance results can vary drastically when pro-
grams are compiled and executed on different processors, using differ-
2.1 How to Design an Algorithm 15
ent compilers. Therefore, the metrics that we develop for measuring com-
plexity should allow us to rate the algorithms independent of their
execution environment.
In summary, we want to analyze the complexity of an algorithm,
without writing any code, without executing any programs, and measure
the results independent of any execution environment. T h e question
then becomes, How do we do this?
In many cases, we can identify one or more basic operations as
critical to the performance of an algorithm. Once identified, we can analyze
(count) these operations to yield a relative eflcienency index or order of
execution magnitude. For example, consider sorting routines. One critical
operation for this class of algorithm is the comparison. That is, we could
state that the fewer the comparisons made, the more efficient the
algorithm. Thus, if we were presented with two or more different
sorting functions, we would usually choose to implement the one that
performed the fewest comparisons.
Now that we have suggested a method of evaluating performance,
we must also develop a consistent manner in which to present it. It would
seem obvious to state that the total amount of work performed by a
function is proportional to the amount of data that it must process. There-
fore, we will represent an algorithm’s complexity as a function of the
size of the input. For example, if n represents the total number
of data elements, a function that requires one critical operation per
input datum is an O(n) (pronounced order n ) algorithm; one that requires
nz operations is O(n2)(pronounced order n squared).
We can state formally that
f ( n ) = O(g(n)) #there exists a c > 0 and an a such that for all n 2 0,
f ( n ) 9 a + cg(n)
This reads as follows: T h e complexity of a functionf(n) is bounded
by the function g(n)-that is, the maximum number of basic opera-
tions executed byf(n) will be no more than g(n). T h e variable a
represents the cost of any housekeeping or startup chores, and c
is a constant multiplier representing the cost (in execution units) of
a basic operation.
In practice, we usually ignore the effects of a, c, and any non-
critical operations when comparing complexities: T h e overall impact of
the constant a tends to become insignificant as the size of the dataset
2 Algorithm Design
increases, and the cost of a critical operation (c) should be about the same
for algorithms of a similar class. That is not to say, however, that their
effect is always negligible. For some problem sizes, an O(n) func-
tion, with a sufficiently large c, can be outperformed by one that has
a complexity of O(n2).In addition, for some algorithms, startup
costs represented by the constant Q might require more than constant
time (e.g., initializing arrays).
Examples of some common complexities include the following:
O(1) represents a constant complexity (e.g., a program that displays
the current date and time).
O(n) is linear.
O(n2)is quadratic.
O(n3) is cubic.
O(2”) is exponential.
Using these relationships, we can state that an O(n)algorithm is more
efficient than one that is O(n2)(for sufficiently large datasets); O(1og n) is
faster than O(n log n), which, in turn, is faster than O(nZ).
T h e complexity of certain algorithms can vary not only with the
size of the input, but also with its composition. Consider again
algorithms that sort names. Some procedures will perform very effi-
ciently when presented with an input stream that is already sorted;
others will degrade miserably. Some operate more efficiently when
the data are random; a few do not. T o compensate for this phenomenon,
we provide two indices of complexity behavior: worst case and average
case. For sorting routines, average case behavior is the average complexity
index for all input streams; worst case is function specific and represents
a pathological performance degradation.
Additional Analysis Criteria
In addition to those just discussed, there are other criteria by which
we can analyze and compare algorithms. These include the
following:
Clarity Clarity concerns the relative ease by which program source
code can be understood by someone other than the original
developer. (We usually refer to this attribute as readability.) A
professional programmer writes programs that are clear and easy to
2.1 How to Design an Algorithm 17
understand. Generally speaking, if you have a choice of implemen-
tation constructs, you should opt for the one that is more readable.
When you must choose a less readable construct (e.g., when perfor-
mance is critical), comment your code clearly.
Maintainability T h e issue of maintainability focuses on how well a
program can accommodate change. As discussed previously, clarity is
a major consideration: You must understand code before you can
modify it. However, maintenance only begins with understanding.
T h e issue boils down to one of confidence: How confident are we
that a change we might apply to one section of a program will not
break some other part of the system? (This is sometimes called
a ripple effect.)
We must design and develop programs with maintenance in
mind. As a simple example, consider the following code
fragment:
int a[ 10 1;
while( i < 10 )
a[il = ...
while( j < 10 )
z = a[jl ...
It might not be clear to a maintenance programmer that the literal
value used in the second loop is related back to the size of a. Left
as is, we might inadvertently introduce a bug into the program if
we were to change a’s size.
Portability Portability can be defined simply: How easy is it for us
to move a given program from one platform to another? (The
term platform is used to describe an execution environment. Com-
ponents of a platform include processor, operating system, databases,
18 2 Algorithm Design
networks, etc.) Keep in mind that the two platforms (source and
destination) might have
Different hardware architectures
Different operating systems
Different system software.
Generally speaking, there are two levels of portability. Object
code portability occurs when we can move executable code from
one system to another. This is usually considered impractical un-
less the two platforms share so many common attributes that they
become almost indistinguishable from each other (e.g., the systems
share the same processor family).
Source code portability is the more practical alternative. We
achieve this level of portability whenever we can copy source
code to a new system, recompile it, and run it with no (or relatively
few) modifications.
These are the advantages of portable programs:
They are easier to move to new platforms
They are less subject to environment changes (i.e., upgrading
the operating system)
They are easier to extend and maintain.
More and more development organizations view portability
as a major factor in systems development. There are several reasons:
T h e increasing costs associated with software maintenance
T h e speed at which hardware improvements occur
Increased competition and decreasing prices for application
software.
Portability, however, is not without its costs. In general, porta-
ble programs are slower because we are less inclined to take
advantage of machine- or operating system-specific features. In
addition, portable programs usually take longer to develop: portability
does not come for free, you must ‘design it’ into the application.
Resource usage Generally speaking, all algorithms require some min-
imal amount of computing resources (e.g., memory, disk, network
access, etc.). T h e quantity and composition of these resources will
vary by algorithm and implementation. As a result, the costs
2.1 How to Design an Algorithm 19
associated with a given set of resources will certainly factor into
your choice of algorithm.
Implementation
After the design and analysis, it is finally time to implement the
algorithm. This should prove to be a fairly straightforward process if we
have followed all the previous suggestions. Specifically, if we wrote a
pseudo-code description of the algorithm, implementation will be little
more than a line-for-line translation.
Another important consideration at this phase might be the selec-
tion of an appropriate programming language. Languages lend themselves
to certain types of tasks and become difficult to use with others. If a
choice is available, select one that is best suited to the needs of the
application.
Testing
T h e last step in the development process is testing. T h e effort ex-
pended on this task will have a direct effect on the perceived quality of
the product. There are essentially two parts to the process. In the first,
we must devise a set of tests that attempt to break the function
or program. This is the creative part of system testing, and it requires
as much consideration and effort as any other task in the develop-
ment process. It begins simply, using a few known data values for
which we can manually compute a result. This establishes that
the program is at least functioning to the point where we can proceed
with more extensive tests.
T h e second and more difficult part of testing is debugging. That
is, we must determine what (if anything) is wrong with the program’s
execution. When we determine the problem, we then develop and
apply fixes to offending sections of the program. When all the
problems have been corrected, we then re-execute all of our tests.
This ensures that the fixes are, indeed, correct and that they have not
affected (i.e., broken) other sections of the program.
When attempting to fix a program error, it is important to distin-
guish between symptom and cause. As an example, consider a program
2 Algorithm Design
that displays employee salary information. T h e program might operate
as follows:
It prompts the user for the employee number.
It searches a database for the appropriate employee and tax
records.
It calculates withholding taxes and other payroll deductions.
It displays the information on the screen.
During your testing you notice that, when displayed, the net pay
field is always incorrect by $1 (alas, in the company’s favor). Would
it be reasonable to assume that the fix is simply to add $1 to its value
just before it gets displayed? No. More likely, this problem is just
a symptom of another problem-such as an error in the formulas for
calculating payroll deductions or incorrect values stored in the tax
tables-and you must delve deeper into the program to find the
real cause. /
Keep in mind that testing can never demonstrate the absence of
bugs-only their presence. Therefore, it is incumbent on the individual(s)
conducting the tests to exercise judgment, diligence, and creativity to
ensure the best possible results.
2.2 EXAMPLE 1: FIBONACCI NUMBERS
T o demonstrate some of the ideas presented in this chapter, let’s
discuss the design and implementation of a function that computes
Fibonacci numbers. T h e Fibonacci sequence is defined as
0, 1, 1, 2, 3, 5, 8, 13, . . .
It begins with F,, = 0 and F , = 1. We compute each subsequent term
as the sum of the previous two. For example,
F(3) = F(2) + F(1) = 1 + 1 = 2
F(6) = F(5) + F(4) = 5 + 3 = 8
Formally, the series can be defined as
F,, = 0
F1 = 1
F,, = F,)-l + F,,-2, for n 2 2
2.2 Example 1: Fibonacci Numbers 21
Our task is to design and implement a function that accepts
a non-negative integer argument n and returns the value F(n).
Understand the Problem
Although it is not a formal specification, the foregoing description
adequately describes the task at hand. T h e key points to keep in mind
are as follows:
T h e function’s one argument corresponds to the sequence number
of the desired Fibonacci number.
The argument, by definition, must be non-negative; therefore,
the function should do something reasonable if invoked with a nega-
tive value.
Data Structures
This algorithm does not require an extensive data structure; it will
use simple integer variables to compute each Fibonacci number.
Pseudo-Code
We can use the formal definition of the Fibonacci series as the starting
point for our development. Thus, the first version of our pseudo-code
might appear as follows:
fib( n 1
i f n = O
return( 0 1 ;
i f n = l
return( 1 1 ;
for i = 2 t o n
fib = fminl +
fmin2;
update fminl and fmin2;
return( fib 1;
Note that our description lacks some important details: the initial
22 2 Algorithm Design
values of variables, the increments for loop variables, and a test for a
valid argument.
After adding these statements, the algorithm becomes
fib( n )
i f n < O
return( - 1 ) ;
i f n = O
return( 0 1;
i f n = l
return( 1 ) ;
fmin2 = 0;
fminl = 1;
for i = 2 t o n
fib = fminl +
fmin2;
fmin2 = fminl;
fminl = fib;
return( fib 1;
Notice that we have established the convention of returning a - 1 to
indicate an erroneous argument. Also note how we initialize and
update the two variables, fminl and frnin2.
Analysis
If we ignore the trivial cases where n 5 1, we can compute the
function’s complexity as follows:
There are five housekeeping instructions executed before entering
the loop.
T h e loop-with its three instructions-is executed n - 1 times,
for a total of 3(n - 1) or, rounding that value, 3n.
T h e total number of instructions executed is 5 + 3n. However,
as mentioned earlier, we ignore the effects of the constants when analyzing
algorithms; thus, the complexity of fib ( ) is O(n).
2.2 Example 1: Fibonacci Numbers 23
i n t fib( i n t n 1
I
int i;
int fibn, fibl, fib2;
if( n < 0 )
return( - 1 1;
i f ( n == 0 )
return( 0 1;
i f ( n == 1 )
return( 1 1 ;
fibn = 0;
fib2 = 0; /* F(n-2) * /
fibl = 1; /* F ( n - 1 ) * /
for( i = 2; ;i <= n; i + +
fibq = fibl fib2; +
fib4 = fibl;
fibl = fibn;
1
return( fibn 1;
1
listing 2.2
Fibonacci numbers.
Implementation
T h e pseudo-code description of this function allows for a direct conver-
sion to C. We need only remember to adhere to C syntax, select
appropriate data types, and declare all variables. Listing 2.2 contains
the final C version of the algorithm.
Testing
Testing this function is a straightforward process. We want to verify
that the function computes accurate values and handles errors
24 2 Algorithm Design
#include < s t d i o . h>
#define MAX-TEST 10
int fib( i n t ) ;
i n t main( void )
c
int i;
f o r ( i = -1; i <= MAX-TEST; i++)
g r i n t f ( "\ti: %2d\tfib(%2d)
: %d\n", i,
i, f i b ( i ) ) ;
r e t u r n ( 0 );
listing 2.3
1
Fibonacci test
program.
correctly. One way to do this is to write another function that repeatedly
invokes fib( ) with known values. Listing 2.3 contains an example.
When compiled with the source for fib ( ) , the output of the
program is
i: -1 f i b ( - l ) : -1
i: 0 fib( 0 ) : 0
i: 1 fib( 1): 1
i: 2 fib( 2 ) : 1
i: 3 fib( 3 ) : 2
i: 4 fib( 4 ) : 3
i: 5 fib( 5 ) : 5
i: 6 fib( 6 ) : 8
i: 7 fib( 7 ) : 13
i: 8 fib( 8 ) : 2 1
i: 9 fib( 9 ) : 34
i: 1 0 f i b ( l 0 ) : 5 5
which we can manually inspect for errors.
2.3 Matric Addition 25
2.3 EXAMPLE 2 MATRIX ADDITION
For our next example, we will design and implement a function that
performs matrix addition. It must compute the sum of two matrices
(A +
B) and store the result in a third (C).
Understand the Problem
T h e two matrices must be of the same dimension. We compute their
sum by adding corresponding elements of A and B and storing the result
in C. For example, given the matrices
the function would compute C as
[1+8 2 + 7 3+6] [9 9 91
4+5 5 + 4 6 + 3 = 9 9 9
7+2 8 + 1 9+0 9 9 9
Data Structures
We will use two-dimensional arrays to store and process the matrices.
Each array entry will correspond to an element in the matrix. One
word of caution: Mathematicians often reference matrix elements as
Ell El2 Ell!
4 1 E22 .** E2n
... ... ... ...
Em1 Em2 - El##
**
In C, however, array subscripts begin at 0. Therefore, Ell will
correspond to array element ACOI 101; E I Zwill correspond to array
element A[Ol 111; and so on until E l , , which corresponds to
A[m- 11 [n- 1 1 .
26 2 Algorithm Design
Pseudo-Code
T o perform the addition of each corresponding matrix element, we
need a way to reference every index pair ( i , j )of the two arrays. We can
do this using a coding construct called nested loops. T h e outer loop
indexes over the rows, while the inner loop indexes over the
columns. A pseudo-code description of the algorithm is as follows:
mat,add( m, n ) /* add m X n matrices */
€or i = 0 to m-1
for j = 0 t o n-1
c[i, j l = a[i, j l + b[i, j l ;
Analysis
A discussion of complexity for this function is easier if we assume that
m = n. T h e outer loop is executed n times. With each iteration, the
inner loop is also executed n times. Thus, the total number of critical
operations (additions) performed by the algorithm is n times n. This
yields a complexity of O(n2).
Implementation
For the purpose of this example, we will assume that the three arrays
(A, B , C) are external to the function. Listing 2.4 contains the C
implementation of the function mat-add () .
Please note the following:
T h e arrays are declared external to the function (the first three
lines of the listing).
T h e two macros, NOJZOWS and NO-COLS, are application depen-
dent and must be defined.
T h e function assumes that the initial values of a [ 1 [ 1 and b [ 1 1
are established before a call is made to mat-add ( ) .
Also note the C syntax for subscripts in two-dimensional arrays.
Many other languages would write subscripts something like
a[i, j l o r a ( i , j )
2.3 Matric Addition 27
int a[ NO-ROWS 1 NO-COLS 1;
int b [ NOJZOWS I [ NO-COLS I;
int c [ NOJZOWS 1 NO-COLS 1;
void m a t , a d d ( i n t rows, i n t cols )
E
i n t i , j;
for( i = 0; i < NO-ROWS; i + + )
for( j = 0; j < NO-COLS; j + + )
c [ i l [ j l = a[ilCjl + b[il [ j l ;
1
Matrix addition.
T h e slightly different notation derives from the fact that in C, a two-
dimensional array is defined as a one-dimensional array, where each
element is another array. Its use is otherwise similar to that of other
languages.
Testing
T h e most direct way to test this function is to write a program that
generates several pairs of matrices, adds them, and then prints the results.
We will leave this as an exercise for the reader.
Programmers new to C should keep in mind that there are no
bounds checks on array references. In particular, because of the zero offset
on array indices, the reference
a [NO-ROWSI “0-COLSI
is out of bounds. As a result, part of your testing procedures should
involve the verification of all array references.
SUMMARY This chapter presented an overview of the software design process. We
will review and expand on the ideas presented in this chapter as we
continue with our discussions. For the sake of brevity, however, we will
28 2 Algorithm Design
no longer prehent algorithms in the expanded format used in this
chapter.
This chapter is incomplete because there is one part of the develop-
ment cycle that we have not discussed: documentation. Documentation
is usually the first thing a user sees when working with a new applica-
tion. As a result, a software product’s success can be dependent on the
quality of its documentation.
Documentation comes in many forms:
Program comments
Manual pages (a description of program usage)
User’s manual
Programmer’s manual
Administrator’s manual.
Throughout this book, we will continue to stress the need to provide
well-commented source code. It is beyond the scope of this text
to describe the other forms of documentation in detail. Moreover,
documentation requirements vary with the installation and the
application. Let it suffice to say that it is incumbent on every program-
mer to provide software that is well documented.
EXERCISES 1. Describe 00 notation.
2. Plot the curves for all the common complexities. Determine points
of intersection and compare behavior.
3. Using all the described steps, design and implement a program
that will count the number of characters, line., and words contained
in a text file. See if you can extend it to count unique words as well.
4.Write the complement of fib ( ) : a function that takes as its sole
argument a Fibonacci number and returns its ordinal position
in the series. Be sure to test for arguments that are not Fibonacci
numbers. How should your function process an argument of l ?
5. Write a program that tests the function mat,add( ) . Be creative.
Are there any boundary conditions?
