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

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 project
1
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.

---