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
87
Figure A.1: Visualising the data structure we are operating on
value
word
lef t
right
Table A.1: A column for each variable we wish to track
The IsPalindrome algorithm uses the following list of variables in some form
throughout its execution:
1.
value
2.
word
3.
lef t
4.
right
Having identified the values of the variables we need to keep track of we
simply create a column for each in a table as shown in Table A.1.
Now, using the IsPalindrome algorithm execute each statement updating
the variable values in the table appropriately. Table A.2 shows the final table
values for each variable used in IsPalindrome respectively.
While this approach may look a little bloated in print, on paper it is much
more compact. Where we have the strings in the table you should annotate
these strings with array indexes to aid the algorithm walkthrough.
There is one other point that we should clarify at this time - whether to
include variables that change only a few times, or not at all in the trace table.
In Table A.2 we have included both the value, and word variables because it
was convenient to do so. You may find that you want to promote these values
to a larger diagram (like that in Figure A.1) and only use the trace table for
variables whose values change during the algorithm. We recommend that you
promote the core data structure being operated on to a larger diagram outside
of the table so that you can interrogate it more easily.
value
word
lef t
right
“Never odd or even”
“NEVERODDOREVEN”
0
13
1
12
2
11
3
10
4
9
5
8
6
7
7
6
Table A.2: Algorithm trace for IsPalindrome

---

APPENDIX A. ALGORITHM WALKTHROUGH
88
We cannot stress enough how important such traces are when designing
your algorithm. You can use these trace tables to verify algorithm correctness.
At the cost of a simple table, and quick sketch of the data structure you are
operating on you can devise correct algorithms quicker. Visualising the problem
domain and keeping track of changing data makes problems a lot easier to solve.
Moreover you always have a point of reference which you can look back on.
A.2
Recursive Algorithms
For the most part working through recursive algorithms is as simple as walking
through an iterative algorithm. One of the things that we need to keep track
of though is which method call returns to who. Most recursive algorithms are
much simple to follow when you draw out the recursive calls rather than using
a table based approach. In this section we will use a recursive implementation
of an algorithm that computes a number from the Fiboncacci sequence.
1) algorithm Fibonacci(n)
2)
Pre: n is the number in the fibonacci sequence to compute
3)
Post: the fibonacci sequence number n has been computed
4)
if n < 1
5)
return 0
6)
else if n < 2
7)
return 1
8)
end if
9)
return Fibonacci(n − 1) + Fibonacci(n − 2)
10) end Fibonacci
Before we jump into showing you a diagrammtic representation of the algo-
rithm calls for the Fibonacci algorithm we will briefly talk about the cases of
the algorithm. The algorithm has three cases in total:
1.
n < 1
2.
n < 2
3.
n ≥ 2
The first two items in the preceeding list are the base cases of the algorithm.
Until we hit one of our base cases in our recursive method call tree we won’t
return anything. The third item from the list is our recursive case.
With each call to the recursive case we etch ever closer to one of our base
cases. Figure A.2 shows a diagrammtic representation of the recursive call chain.
In Figure A.2 the order in which the methods are called are labelled. Figure
A.3 shows the call chain annotated with the return values of each method call
as well as the order in which methods return to their callers. In Figure A.3 the
return values are represented as annotations to the red arrows.
It is important to note that each recursive call only ever returns to its caller
upon hitting one of the two base cases. When you do eventually hit a base case
that branch of recursive calls ceases. Upon hitting a base case you go back to

---