Introduction of Data Structures and Algorithms – Object oriented concepts, Pseudo code

Object oriented concepts

For the most part this book does not use features that are speci¯c to any one
language. In particular, we never provide data structures or algorithms that
work on generic types|this is in order to make the samples as easy to follow
as possible. However, to appreciate the designs of our data structures you will
need to be familiar with the following object oriented (OO) concepts:

1. Inheritance
2. Encapsulation
3. Polymorphism

This is especially important if you are planning on looking at the C# target
that we have implemented (more on that in x1.7) which makes extensive use
of the OO concepts listed above. As a ¯nal note it is also desirable that the
reader is familiar with interfaces as the C# target uses interfaces throughout
the sorting algorithms.

Pseudocode

Throughout this book we use pseudocode to describe our solutions. For the
most part interpreting the pseudocode is trivial as it looks very much like a
more abstract C++, or C#, but there are a few things to point out:

1. Pre-conditions should always be enforced
2. Post-conditions represent the result of applying algorithm a to data struc-
ture d
3. The type of parameters is inferred
4. All primitive language constructs are explicitly begun and ended

If an algorithm has a return type it will often be presented in the post-
condition, but where the return type is su±ciently obvious it may be omitted
for the sake of brevity.
Most algorithms in this book require parameters, and because we assign no
explicit type to those parameters the type is inferred from the contexts in which
it is used, and the operations performed upon it. Additionally, the name of
the parameter usually acts as the biggest clue to its type. For instance n is a
pseudo-name for a number and so you can assume unless otherwise stated that
n translates to an integer that has the same number of bits as a WORD on a
32 bit machine, similarly l is a pseudo-name for a list where a list is a resizeable
array (e.g. a vector).
The last major point of reference is that we always explicitly end a language
construct. For instance if we wish to close the scope of a for loop we will
explicitly state end for rather than leaving the interpretation of when scopes
are closed to the reader. While implicit scope closure works well in simple code,
in complex cases it can lead to ambiguity.
The pseudocode style that we use within this book is rather straightforward.
All algorithms start with a simple algorithm signature, e.g.

1) algorithm AlgorithmName(arg1, arg2, …, argN)
2) …
n) end AlgorithmName
Immediately after the algorithm signature we list any Pre or Post condi-
tions.
1) algorithm AlgorithmName(n)
2) Pre: n is the value to compute the factorial of
3) n ¸ 0
4) Post: the factorial of n has been computed
5) // …
n) end AlgorithmName

The example above describes an algorithm by the name of AlgorithmName,
which takes a single numeric parameter n. The pre and post conditions follow
the algorithm signature; you should always enforce the pre-conditions of an
algorithm when porting them to your language of choice.
Normally what is listed as a pre-conidition is critical to the algorithms opera-
tion. This may cover things like the actual parameter not being null, or that the
collection passed in must contain at least n items. The post-condition mainly
describes the e®ect of the algorithms operation. An example of a post-condition
might be \The list has been sorted in ascending order”
Because everything we describe is language independent you will need to
make your own mind up on how to best handle pre-conditions. For example,
in the C# target we have implemented, we consider non-conformance to pre-
conditions to be exceptional cases. We provide a message in the exception to
tell the caller why the algorithm has failed to execute normally.