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

APPENDIX A. ALGORITHM WALKTHROUGH
89
Figure A.2: Call chain for Fibonacci algorithm
Figure A.3: Return chain for Fibonacci algorithm

---

APPENDIX A. ALGORITHM WALKTHROUGH
90
the caller and continue execution of that method. Execution in the caller is
contiued at the next statement, or expression after the recursive call was made.
In the Fibonacci algorithms’ recursive case we make two recursive calls.
When the first recursive call (Fibonacci(n − 1)) returns to the caller we then
execute the the second recursive call (Fibonacci(n − 2)). After both recursive
calls have returned to their caller, the caller can then subesequently return to
its caller and so on.
Recursive algorithms are much easier to demonstrate diagrammatically as
Figure A.2 demonstrates. When you come across a recursive algorithm draw
method call diagrams to understand how the algorithm works at a high level.
A.3
Summary
Understanding algorithms can be hard at times, particularly from an implemen-
tation perspective. In order to understand an algorithm try and work through
it using trace tables. In cases where the algorithm is also recursive sketch the
recursive calls out so you can visualise the call/return chain.
In the vast majority of cases implementing an algorithm is simple provided
that you know how the algorithm works. Mastering how an algorithm works
from a high level is key for devising a well designed solution to the problem in
hand.

---

Appendix B
Translation Walkthrough
The conversion from pseudo to an actual imperative language is usually very
straight forward, to clarify an example is provided. In this example we will
convert the algorithm in §9.1 to the C# language.
1) public static bool IsPrime(int number)
2) {
3)
if (number < 2)
4)
{
5)
return false;
6)
}
7)
int innerLoopBound = (int)Math.Floor(Math.Sqrt(number));
8)
for (int i = 1; i < number; i++)
9)
{
10)
for(int j = 1; j <= innerLoopBound; j++)
11)
{
12)
if (i ∗ j == number)
13)
{
14)
return false;
15)
}
16)
}
17)
}
18)
return true;
19) }
For the most part the conversion is a straight forward process, however you
may have to inject various calls to other utility algorithms to ascertain the
correct result.
A consideration to take note of is that many algorithms have fairly strict
preconditions, of which there may be several - in these scenarios you will need
to inject the correct code to handle such situations to preserve the correctness of
the algorithm. Most of the preconditions can be suitably handled by throwing
the correct exception.
91

---

APPENDIX B. TRANSLATION WALKTHROUGH
92
B.1
Summary
As you can see from the example used in this chapter we have tried to make the
translation of our pseudo code algorithms to mainstream imperative languages
as simple as possible.
Whenever you encounter a keyword within our pseudo code examples that
you are unfamiliar with just browse to Appendix E which descirbes each key-
word.

---

Appendix C
Recursive Vs. Iterative
Solutions
One of the most succinct properties of modern programming languages like
C++, C#, and Java (as well as many others) is that these languages allow
you to define methods that reference themselves, such methods are said to be
recursive. One of the biggest advantages recursive methods bring to the table is
that they usually result in more readable, and compact solutions to problems.
A recursive method then is one that is defined in terms of itself. Generally
a recursive algorithms has two main properties:
1.
One or more base cases; and
2.
A recursive case
For now we will briefly cover these two aspects of recursive algorithms. With
each recursive call we should be making progress to our base case otherwise we
are going to run into trouble. The trouble we speak of manifests itself typically
as a stack overflow, we will describe why later.
Now that we have briefly described what a recursive algorithm is and why
you might want to use such an approach for your algorithms we will now talk
about iterative solutions. An iterative solution uses no recursion whatsoever.
An iterative solution relies only on the use of loops (e.g. for, while, do-while,
etc). The down side to iterative algorithms is that they tend not to be as clear
as to their recursive counterparts with respect to their operation. The major
advantage of iterative solutions is speed. Most production software you will
find uses little or no recursive algorithms whatsoever. The latter property can
sometimes be a companies prerequisite to checking in code, e.g. upon checking
in a static analysis tool may verify that the code the developer is checking in
contains no recursive algorithms. Normally it is systems level code that has this
zero tolerance policy for recursive algorithms.
Using recursion should always be reserved for fast algorithms, you should
avoid it for the following algorithm run time deficiencies:
1.