Algorithm Tracing practice questions.

Which set of columns makes a trace table of a loop useful to the person checking the algorithm?

• One single column holding the whole state of the program written out at each step.
• One column for each variable that changes, plus the condition being tested.
• One column for every line number that the algorithm contains.
• One column for the input and one for the final output only.

Answer: One column for each variable that changes, plus the condition being tested.

The purpose of the table is to show where a value first becomes wrong, which needs the changing variables side by side and the condition that decides whether the loop runs again. Recording only the input and the output turns the trace back into a guess.

A search over an array of 5 elements, indexed from 0, is traced. The index column of the trace table reads 0, 1, 2, 3, 4, 5, and in the last row index 5 is used to read an element. What has the trace revealed?

• The array was declared with too few elements for the data it holds.
• The loop condition is being tested after the body instead of before it.
• The counter was initialised to 1 rather than to 0.
• The loop runs one pass too many and reads past the last element.

Answer: The loop runs one pass too many and reads past the last element.

With indices running from 0 to 4 the only legal reads stop at 4, so a read at 5 shows that the terminating condition is one step too generous. This off-by-one error is exactly what a trace table exposes, because the faulty index appears in a row of its own.

A hand trace of a sorting algorithm gives the expected result for the data [3, 1, 2], yet the algorithm still fails on real data. What is the most likely cause?

• The chosen test data never produces the case in which the fault appears.
• A trace table cannot be used to check a sorting algorithm at all.
• The algorithm was traced entirely correctly, but the expected result used for the comparison was wrong.
• Hand tracing always gives a different result from running the code.

Answer: The chosen test data never produces the case in which the fault appears.

A trace proves the algorithm only for the values traced, so data that never reaches the faulty branch, such as duplicates or an already sorted array, hides the defect. Choosing data that touches the boundary cases is what makes tracing a test rather than a demonstration.

While tracing, a candidate finds that the variable holding a running total is never given a value before the loop begins. What should be reported?

• That the loop condition is the wrong way round and has to be reversed.
• That the running total ought to be held in an array instead.
• That the output statement has been placed inside the loop body by mistake instead of after it.
• That the total is uninitialised, so the result of the algorithm is undefined.

Answer: That the total is uninitialised, so the result of the algorithm is undefined.

A running total has to start from a known value, normally zero, or the first addition works on whatever the variable happens to contain. A trace exposes this at once, because the first row of the table has no value to write down.

A candidate wants to check a search algorithm by tracing it. Which choice of data reveals the most faults for the least work?

• Three arrays of different lengths, all containing the target
• One case with the target first, one with it last, one with it absent
• Three separate cases in which the target sits somewhere in the middle
• One very long array, because it exercises more of the loop

Answer: One case with the target first, one with it last, one with it absent

Faults in a search cluster at the two ends and in the case where the loop must finish without success, so those three cases between them exercise the boundaries and the exit condition. A middle case is the one situation almost every incorrect version handles correctly, which is why it proves the least.

A trace table is being built for an algorithm containing one loop nested inside another. How many rows of values should it contain?

• One for each variable that the two loops change
• One for each statement that appears inside either loop
• One for each pass of the inner loop, plus a starting row
• One for each pass of the outer loop only, plus a starting row

Answer: One for each pass of the inner loop, plus a starting row

The inner loop is where the values actually change most often, so a row per outer pass would hide everything the inner loop did. Recording a row per statement produces a table far longer than the algorithm and no easier to read.