3GL Step-Form Algorithm - Exercise 3
   
Exercise 1 Trace Table:

Assume the book has 3 pages, the trace table looks like this:
 
Step next page count
Get book ? ?
Open book  ? ?
If there is no next page go to step 7 NO ?
Find next page NO ?
Increment count  NO 1
If there is no next page go to step 7 NO 1
Find next page NO 1
Increment count NO 2
If there is no next page go to step 7 NO 2
Find next page NO 2
Increment count NO 3
If there is no next page go to step 7 YES 3
Finish YES 3
 

The column headed next page looks odd. Why is the answer NO when there is a next page? Keep in mind that the question that is asked is "Is there NO next page", if there is no next page then the answer is YES, if there is a next page then the answer to NO next page is NO.

Exercise 2 Trace Table:

Here is the algorithm again:

Just as the algorithm was a combination of two algorithms, the trace table is a combination of two trace tables, the original vowel counter shown here, and the page counter shown above:
 
Vowel counter trace table - vowels per page
Step
curr
last
count
letter
letter is vowel
curr <= last
1,2,3
1
6
0
?
?
?
4
1
6
0
'A'
?
?
5
1
6
1
'A'
True
?
6
2
6
1
'A'
True
?
7
2
6
1
'A'
True
True
4
2
6
1
' '
True
True
5
2
6
1
' '
False
True
6
3
6
1
' '
False
True
7
3
6
1
' '
False
True
4
3
6
1
'p'
False
True
5
3
6
1
'p'
False
True
6
4
6
1
'p'
False
True
7
4
6
1
'p'
False
True
4
4
6
1
'a'
False
True
5
4
6
2
'a'
True
True
6
5
6
2
'a'
True
True
7
5
6
2
'a'
True
True
4
5
6
2
'g'
True
True
5
5
6
2
'g'
False
True
6
6
6
2
'g'
False
True
7
6
6
2
'g'
False
True
4
6
6
2
'e'
False
True
5
6
6
3
'e'
True
True
6
7
6
3
'e'
True
True
7
7
6
3
'e'
True
False
 

Since it is in the repetitions that a program does most of its work it follows that the trace table will contain lots of repetition. One way to simplify the trace table is to split it up on the basis of the loops that are in the table. The diagram here shows two loops, the paging loop and the vowel counting loop. The counting loop is contained within the paging loop. We can build three trace tables, one for each loop and one main table, or, we could build two tables, one main table containing the outer main paging loop and a separate table for the inner counting loop.
 
 
 
 
 

I've taken the two-tables option, a main table and a vowel_counter table and abbreviated the variable names:
 

Main trace table for counting vowels in a book
Step total next_page current last vowel_counter not_vowel
1 0 ? ? ? ? ?
2 0 ? ? ? ? ?
3 0 ? ? ? ? ?
4 0 ? ? ? ? ?
5 0 NO ? ? ? ?
6 - 14 The trace table for these rows will appear below
15 20 NO 301 300 20 YES
16 20 NO 301 300 0 YES
17 20 NO 301 300 0 YES
4 20 NO 301 300 0 YES
5 20 NO 301 300 0 YES
6 - 14 Note that the main table shows the current state of the variables in the vowel counter table
15 51 NO 422 421 31 NO
16 51 NO 422 421 0 NO
17 51 NO 422 421 0 NO
4* 51 YES 422 421 0 NO
18 51 YES 422 421 0 NO
 

This trace table sample shows that we have a book of two pages - not much of a book - that the first page contained 300 letters with twenty vowels, the second page contained 421 letters with 31 vowels. The last step 4 (shown with an asterisk) was the point at which the algorithm determined that there was no more pages. I haven't rebuilt the vowel-counting trace here since it won't differ substantially from the table above (Vowel counter trace table - vowels per page).

Although trace tables are a very useful tool for testing algorithms you have probably already realised that the tables can get quite large and cumbersome. There are other algorithm testing and proving techniques but they are outside the scope of this course.

How you build and use trace tables is largely a matter of choice and as you develop your program design skills you will refine your testing and checking skills.

Return to lesson

 

This publication is copyright David Beech and Learning Systems 1997-2002
and may not be reproduced by any means without the written permission of
David Beech.
9 Wyndella Street, Tasmania, Australia


db@codelearn.com