D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

CHAPTER 1. INTRODUCTION
4
The reason that we are explicit in this requirement is simple—all our imple-
mentations are based on an imperative thinking style. If you are a functional
programmer you will need to apply various aspects from the functional paradigm
to produce efficient solutions with respect to your functional language whether
it be Haskell, F#, OCaml, etc.
Two of the languages that we have listed (C# and Java) target virtual
machines which provide various things like security sand boxing, and memory
management via garbage collection algorithms. It is trivial to port our imple-
mentations to these languages. When porting to C++ you must remember to
use pointers for certain things. For example, when we describe a linked list
node as having a reference to the next node, this description is in the context
of a managed environment. In C++ you should interpret the reference as a
pointer to the next node and so on. For programmers who have a fair amount
of experience with their respective language these subtleties will present no is-
sue, which is why we really do emphasise that the reader must be comfortable
with at least one imperative language in order to successfully port the pseudo-
implementations in this book.
It is essential that the user is familiar with primitive imperative language
constructs before reading this book otherwise you will just get lost. Some algo-
rithms presented in this book can be confusing to follow even for experienced
programmers!
1.2.3
Object oriented concepts
For the most part this book does not use features that are specific 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 §1.7) which makes extensive use
of the OO concepts listed above. As a final note it is also desirable that the
reader is familiar with interfaces as the C# target uses interfaces throughout
the sorting algorithms.
1.3
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

---

CHAPTER 1. INTRODUCTION
5
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 sufficiently 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 effect 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.

---

CHAPTER 1. INTRODUCTION
6
1.4
Tips for working through the examples
As with most books you get out what you put in and so we recommend that in
order to get the most out of this book you work through each algorithm with a
pen and paper to track things like variable names, recursive calls etc.
The best way to work through algorithms is to set up a table, and in that
table give each variable its own column and continuously update these columns.
This will help you keep track of and visualise the mutations that are occurring
throughout the algorithm. Often while working through algorithms in such
a way you can intuitively map relationships between data structures rather
than trying to work out a few values on paper and the rest in your head. We
suggest you put everything on paper irrespective of how trivial some variables
and calculations may be so that you always have a point of reference.
When dealing with recursive algorithm traces we recommend you do the
same as the above, but also have a table that records function calls and who
they return to. This approach is a far cleaner way than drawing out an elaborate
map of function calls with arrows to one another, which gets large quickly and
simply makes things more complex to follow. Track everything in a simple and
systematic way to make your time studying the implementations far easier.
1.5
Book outline
We have split this book into two parts: