Dsa - Barnette and Tonga - 6

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:
Part 1: Provides discussion and pseudo-implementations of common and uncom-

mon data structures; and
Part 2: Provides algorithms of varying purposes from sorting to string operations.
The reader doesn’t have to read the book sequentially from beginning to
end: chapters can be read independently from one another. We suggest that
in part 1 you read each chapter in its entirety, but in part 2 you can get away
with just reading the section of a chapter that describes the algorithm you are
interested in.
Each of the chapters on data structures present initially the algorithms con-
cerned with:
1. Insertion
2. Deletion
3. Searching
The previous list represents what we believe in the vast majority of cases to
be the most important for each respective data structure.
For all readers we recommend that before looking at any algorithm you
quickly look at Appendix E which contains a table listing the various symbols
used within our algorithms and their meaning. One keyword that we would like
to point out here is yield. You can think of yield in the same light as return.
The return keyword causes the method to exit and returns control to the caller,
whereas yield returns each value to the caller. With yield control only returns
to the caller when all values to return to the caller have been exhausted.
CHAPTER 1. INTRODUCTION 7
1.6 Testing
All the data structures and algorithms have been tested using a minimised test
driven development style on paper to flesh out the pseudocode algorithm. We
then transcribe these tests into unit tests satisfying them one by one. When
all the test cases have been progressively satisfied we consider that algorithm
suitably tested.
For the most part algorithms have fairly obvious cases which need to be
satisfied. Some however have many areas which can prove to be more complex
to satisfy. With such algorithms we will point out the test cases which are tricky
and the corresponding portions of pseudocode within the algorithm that satisfy
that respective case.
As you become more familiar with the actual problem you will be able to
intuitively identify areas which may cause problems for your algorithms imple-
mentation. This in some cases will yield an overwhelming list of concerns which
will hinder your ability to design an algorithm greatly. When you are bom-
barded with such a vast amount of concerns look at the overall problem again
and sub-divide the problem into smaller problems. Solving the smaller problems
and then composing them is a far easier task than clouding your mind with too
many little details.
The only type of testing that we use in the implementation of all that is
provided in this book are unit tests. Because unit tests contribute such a core
piece of creating somewhat more stable software we invite the reader to view
Appendix D which describes testing in more depth.
1.7 Where can I get the code?

This book doesn’t provide any code specifically aligned with it, however we do
actively maintain an open source project1 that houses a C# implementation of
all the pseudocode listed. The project is named Data Structures and Algorithms
(DSA) and can be found at http://codeplex.com/dsa.
1.8 Final messages

We have just a few final messages to the reader that we hope you digest before
you embark on reading this book:
1. Understand how the algorithm works first in an abstract sense; and

2. Always work through the algorithms on paper to understand how they
achieve their outcome
If you always follow these key points, you will get the most out of this book.
1 All readers are encouraged to provide suggestions, feature requests, and bugs so we can
further improve our implementations.

Dsa - Barnette and Tonga - 6

Uploaded by

Copyright:

Available Formats

Dsa - Barnette and Tonga - 6

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Dsa - Barnette and Tonga - 6

Uploaded by

Copyright:

Available Formats

CHAPTER 1.

3. The type of parameters is inferred

The example above describes an algorithm by the name of AlgorithmName,

1.4 Tips for working through the examples

1.5 Book outline

Part 1: Provides discussion and pseudo-implementations of common and uncom-

1.7 Where can I get the code?

1.8 Final messages

1. Understand how the algorithm works first in an abstract sense; and

further improve our implementations.

You might also like