Page 78 - Introduction to Programming with Java: A Problem Solving Approach

44 Chapter 2 Algorithms and Design
Trace setup:
• If there is input, provide a column heading labeled input. • Provide a column heading for each variable.
• Provideacolumnheadinglabeledoutput.
Trace the program by executing the algorithm one line at a time, and for each line, do this:
• Foraninputstatement,crossoffthenextinputvalueundertheinputcolumnheading.
• For an assignment statement, update a variable’s value by writing the new value under the
variable’s column heading. If there are already values under the column heading, insert the
new value below the bottom value and cross off the old value.
• For a print statement, write the printed value under the output column heading. If there are
already values under the output column heading, insert the new printed value below the bot- tom of the output column.
Figure 2.14 Short-form tracing procedure
Short-form tracing works well in a live interactive context, but it does not work as well in a static con- text like the pages of a printed book. That’s because in a book, the short-form tracing does not portray the dynamics of the updating process very well. With our simple Happy birthday algorithm, you may have been able to visualize the dynamics. But for more involved algorithms, a short-form trace listing on the page of a book just “blows through” the details it needs to highlight. Therefore, in this book, we’ll use a long-form tracing procedure that keeps bettAerptraackgofoeachPsteDp aFs theEproncehssaunnfolcds.er
Long-Form Tracing
With the long-form tracing procedure, there’s an added emphasis on keeping track of where you are in the algorithm. To implement that emphasis, (1) you need to have a separate row in the tracing table for each step that’s executed in the algorithm, and (2) for each row in the tracing table, you need to provide a line number that tells you the row’s associated line in the algorithm. For an example, see the long-form happy birthday trace in Figure 2.15.
Figure 2.15’s long-form trace looks somewhat like the previous short-form trace, with a few notable ex- ceptions. The input column has been moved above the main part of the tracing table. In its place is the line# column, which holds line numbers in the algorithm that correspond to rows in the tracing table. Notice the two 5, 6 line number sequences. That shows how the trace “unrolls” the loop and repeats the sequence of statements within the loop for each loop iteration.
Using a Trace To Find a Bug
It’s time for you to get your money’s worth from all this tracing talk. We’ll provide you with an algorithm and it’s up to you to determine whether it works properly. More specifically, trace the algorithm to deter-
Check each step.
mine whether each step produces reasonable output. If it produces faulty output, find
the algorithm’s bug and fix the algorithm.
Suppose that Park University’s Student Housing office wrote the algorithm shown in Figure 2.16. The
algorithm is supposed to read in the names of freshmen and assign each freshman to one of two dormitories. Freshmen with names that begin with A through M are assigned to Chestnut Hall and freshmen with names