Categories: Computers & Internet

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

Related Post

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.




  • Khushal Sharma

    View Comments

    Recent Posts

    Heart Attack Causes and its Solution

    What is the Main Cause of a Heart Attack? What is its Solution? A heart attack is the blockage of… Read More

    4 months ago

    Understanding the Debt Ceiling: Its Impact, Importance, and Implications

    In the vast economic arena, one term that often takes center stage, inciting extensive debates and discussions, is the "debt… Read More

    9 months ago

    De-Dollarization: The New World Order of Currency and Its Global Impact

    De-Dollarization: The Changing Face of Global Finance The financial landscape is in a state of flux, with an intriguing economic… Read More

    10 months ago

    Unstoppable Bayern Munich: The Story Behind Their 11th Consecutive Bundesliga Title

    The curtains closed on a dramatic Bundesliga season with Bayern Munich standing tall once again, clinching their 11th straight title.… Read More

    10 months ago

    Celine Dion Cancels Concert Tour Due to Deteriorating Stiff-Person Syndrome

    The Unfolding Story of Celine Dion's Health In recent news that has left fans across the globe stunned, iconic singer… Read More

    10 months ago

    Navigating the Crossroads: LeBron James, Anthony Davis, and the LA Lakers’ Uncertain Future

    As the echoes of the recent NBA season start to fade, the attention of enthusiasts is firmly glued to one… Read More

    10 months ago