Java Reference
In-Depth Information
to write it down, nor implement it as a computer program. Most languages for
describing algorithms (including English and “pseudocode”) provide some
way to perform repeated actions, known as iteration. Examples of iteration
in programming languages include the
while
and
for
loop constructs of
Java. Iteration allows for short descriptions, with the number of steps actually
performed controlled by the input.
5. It must terminate. In other words, it may not go into an infinite loop.
Programs: We often think of a computer program as an instance, or concrete
representation, of an algorithm in some programming language. In this topic,
nearly all of the algorithms are presented in terms of programs, or parts of pro-
grams. Naturally, there are many programs that are instances of the same alg-
orithm, because any modern computer programming language can be used to im-
plement the same collection of algorithms (although some programming languages
can make life easier for the programmer). To simplify presentation, I often use
the terms “algorithm” and “program” interchangeably, despite the fact that they are
really separate concepts. By definition, an algorithm must provide sufficient detail
that it can be converted into a program when needed.
The requirement that an algorithm must terminate means that not all computer
programs meet the technical definition of an algorithm. Your operating system is
one such program. However, you can think of the various tasks for an operating sys-
tem (each with associated inputs and outputs) as individual problems, each solved
by specific algorithms implemented by a part of the operating system program, and
each one of which terminates once its output is produced.
To summarize: A problem is a function or a mapping of inputs to outputs.
An algorithm is a recipe for solving a problem whose steps are concrete and un-
ambiguous. Algorithms must be correct, of finite length, and must terminate for all
inputs. A program is an instantiation of an algorithm in a programming language.
1.5
Further Reading
An early authoritative work on data structures and algorithms was the series of
topics The Art of Computer Programming by Donald E. Knuth, with Volumes 1
and 3 being most relevant to the study of data structures [Knu97, Knu98]. A mod-
ern encyclopedic approach to data structures and algorithms that should be easy
to understand once you have mastered this topic is Algorithms by Robert Sedge-
wick [Sed11]. For an excellent and highly readable (but more advanced) teaching
introduction to algorithms, their design, and their analysis, see Introduction to Al-
gorithms: A Creative Approach by Udi Manber [Man89]. For an advanced, en-
cyclopedic approach, see Introduction to Algorithms by Cormen, Leiserson, and
Rivest [CLRS09]. Steven S. Skiena's The Algorithm Design Manual [Ski10] pro-
