Tracing Algorithms With Trace Tables

플레이하며 배우기

이 문제들을 풀어 에너지를 얻은 뒤 낚시하고 탐험하세요. 계정이 필요 없어요.

선생님을 위해: Tracing Algorithms With Trace Tables(Computer Science, CIE)을(를) 위한 바로 쓸 수 있는 수업 슬라이드, 복습 노트 — 수업에 사용하거나, 학생들이 실시간 게임으로 즐기는 인터랙티브 클래스 활동으로 진행하세요.

수업 노트

Purpose and Exam Context

Trace tables document a dry-run of an algorithm: you execute it by hand exactly as a computer would, without running it.
Required by CIE 0478 §7.7: complete a trace table showing variables, outputs, and user prompts at each step.
Common on Paper 2 (1h45, 75 marks); the grid is often pre-printed with column headings and blank rows.
Calculators are not allowed, so all arithmetic must be done and checked by hand.
Trace tables help you verify logic, spot errors, and state the final output — a key exam skill.

The Column Method – Six Rules

Rule 1: Draw the table before tracing: one column per variable (in declaration order), plus OUTPUT and PROMPT columns if needed.
For arrays, either give each element its own column (e.g., `Names[1]`, `Names[2]`) or use an index column plus an element column, matching the printed grid.
Rule 2: Write a new value only when a variable is assigned; leave cells blank otherwise. Never overwrite previous values — the trail earns marks.
Rule 3: Follow control flow, not page order: after `NEXT`, `ENDWHILE`, or `UNTIL`, jump back to the loop start; after `ENDIF`, continue after the block.
Rule 4: Test conditions at the exact point they are tested: `WHILE...DO` tests before the body (may run zero times), `REPEAT...UNTIL` tests after (runs at least once), `FOR...NEXT` tests before each pass.
Rule 5: Record every `OUTPUT` on the row it happens, exactly as the user sees it, including fixed text and spaces.
Rule 6: Re-read the last row: the final output is what the OUTPUT column contains, in order, and nothing else.

Tracing Loops and Conditions

WHILE...DO is a pre-condition loop: condition tested before the body, so the body may run zero times.
REPEAT...UNTIL is a post-condition loop: body always runs at least once; condition tested after.
FOR...NEXT tests before each pass; runs zero times if the start value is already past the end value.
Count passes before you start: `FOR 1 TO 10` runs 10 times, `FOR 0 TO 10` runs 11 times, `FOR 1 TO 10 STEP 2` runs 5 times.
Watch `≤` vs `<` at boundaries — a common source of off-by-one errors.
Read loop conditions as a whole, including `AND`/`OR`; a search loop may end for two reasons, and which one decides the output.

Totalling and Counting

Totalling adds each value to a running total that starts at 0.
Counting adds 1 to a counter each time a condition is met.
Initialise the total/counter before the loop — an uninitialised variable is a common error.
Example: `Total ← 0` then `Total ← Total + Amount[Index]` inside a loop.
In a trace, record the updated total on each row where it changes.

Tracing Arrays and Nested Loops

For arrays, give each element its own column or use an index column; write the element value when accessed.
Nested loops: the inner loop runs completely for each pass of the outer loop; e.g., 2 rows × 3 columns = 6 inner-body executions.
Reset inner variables (like `RowTotal`) at the start of each outer pass — forgetting this is a classic slip.
Column restarts at its start value each time the outer counter advances.
Trace the inner loop fully before moving to the next outer iteration.

Standard Algorithms: Linear Search and Bubble Sort

Linear search checks each item in turn from the start; stops as soon as a match is found (may end mid-list).
Use a found flag (e.g., `Found ← FALSE`) and an index; the loop condition often includes `AND Found = FALSE`.
If not found, the index reaches `n+1` and the loop ends; output `Not found`.
Bubble sort compares neighbouring pairs and swaps if out of order; each pass pushes the next largest value to the end.
After each pass, the number of comparisons can reduce by one; a pass with no swaps means the list is sorted.
In a trace, write the whole list after every swap and keep a Swapped flag in its own column.

Handling User Prompts and Validation

PROMPT column shows the text the user sees; the `INPUT` statement itself displays nothing.
For validation loops (e.g., `REPEAT...UNTIL Mark ≥ 0 AND Mark ≤ 100`), the prompt appears for every attempt, including the successful one.
Record the input value in the variable column on the same row as the prompt.
Example: inputs -5, 120, 64 → three prompt rows, final output `Accepted: 64`.

Systematic Checks to Catch Slips

Count loop passes before tracing to know how many rows to expect.
Read conditions as a whole, including `AND`/`OR`.
Watch `≤` vs `<` at boundaries.
After a swap, write both changed values on the same row.
If a variable never appears, check if it was ever assigned; if a column is full of identical values, check if it should be reset inside the loop.
If trace and expected result disagree, trust the trace and look for the algorithm's error — this is the skill tested in §7.8.

슬라이드

Step through every slide for this topic — plus flashcards and revision notes — with a free account.

가입 — 무료 로그인

연습 문제

무료 미리 보기 — 62개 중 8개 문제. 가입하면 전부 볼 수 있어요.

1.What is a trace table used for in computer science?
Easy
- ATo document a dry-run of an algorithm by hand
- BTo compile a program into machine code
- CTo store data permanently in a file
- DTo design the user interface of a program
2.A trace table must have one column for each variable used in the algorithm.
Easy
True or false?
3.When tracing a WHILE...DO loop, when is the loop condition tested?
Easy
- ABefore the loop body executes
- BAfter the loop body executes
- COnly at the end of the whole program
- DOnly when the loop is first reached
4.In a REPEAT...UNTIL loop, the body always executes at least once.
Easy
True or false?
5.What is the purpose of a 'PROMPT' column in a trace table?
Medium
- ATo record the text displayed to the user when input is requested
- BTo show the values of variables after each iteration
- CTo list the error messages generated by the algorithm
- DTo store the output of the algorithm
6.Which of the following are standard methods that can be traced using trace tables? (Select all that apply)
Medium
- ALinear search
- BBubble sort
- CTotalling
- DCompilation
- ECounting
7.When tracing a FOR...NEXT loop, if the start value is already past the end value, the loop body runs zero times.
Easy
True or false?
8.What is the first step in the column method for creating a trace table?
Easy
- ADraw the table before tracing
- BExecute the algorithm on a computer
- CWrite the output first
- DCount the number of iterations

더 많은 문제

9.In a trace table, you should write a new value for a variable only when it changes.
Easy
True or false?
10.When tracing a bubble sort, what does the 'Swapped' flag indicate?
Medium
- AWhether any swaps were made in the current pass
- BWhether the list is sorted in descending order
- CWhether the algorithm has started
- DWhether the algorithm has terminated
11.Which of the following are common errors to watch for when tracing loops? (Select all that apply)
Medium
- AForgetting to reset a variable inside the loop
- BUsing < instead of ≤ at the boundary
- CTesting the condition at the wrong point
- DWriting the output before the loop ends
- EUsing a variable without initialising it
12.In a trace table, after a swap in a bubble sort, you should write both changed values on the same row.
Medium
True or false?
13.What is the purpose of the OUTPUT column in a trace table?
Medium
- ATo record the values displayed to the user
- BTo store the final value of each variable
- CTo show the user prompts
- DTo list the variables in order
14.What is the purpose of a 'found' flag in a linear search algorithm?
Medium
- ATo indicate whether the search item has been found
- BTo count the number of comparisons made
- CTo store the position of the first element
- DTo mark the end of the array
15.In a trace table, the PROMPT column is used to record the values input by the user.
Easy
True or false?
16.When tracing nested loops, which of the following is the classic slip?
Medium
- AForgetting to reset the inner loop counter to its start value
- BWriting the outer loop counter in the inner loop
- CUsing the wrong variable name for the outer loop
- DNot drawing a table before tracing
17.In a trace table, when the trace and the expected result disagree, you should trust the expected result and ignore the trace.
Medium
True or false?
18.What is the purpose of a 'total' variable in a totalling algorithm?
Medium
- ATo store the running sum of values
- BTo count the number of items
- CTo store the maximum value
- DTo store the average value
19.Match each loop type to its condition-testing behaviour.
Medium
- WHILE...DO
- REPEAT...UNTIL
- FOR...NEXT
- Tests before each pass
- Tests after each pass
- Tests before each pass
20.Put the steps of the column method in the correct order: (1) Draw the table, (2) Follow control flow, (3) Test the condition, (4) Record OUTPUT, (5) Re-read the last row.
Medium
- Draw the table
- Follow control flow
- Test the condition
- Record OUTPUT
- Re-read the last row
21.Match each type of loop to when it tests its condition.
Easy
- WHILE...DO
- REPEAT...UNTIL
- FOR...NEXT
- Tests before each iteration
- Tests after each iteration
- Tests before each iteration
22.Put the steps of the column method for creating a trace table in the correct order.
Easy
- Draw the table with columns for each variable, OUTPUT and PROMPT
- Follow the control flow line by line
- Test each condition at the exact point it is tested
- Record every OUTPUT on the row it happens
- Re-read the last row to state the final output
23.In a trace table for a bubble sort, after a swap you should write both changed values:
Medium
- Aon the same row
- Bon separate rows
- Conly the larger value
- Donly the smaller value
24.Which of the following are common errors that a trace table can help you spot? (Select all that apply)
Medium
- AOff-by-one errors in loop boundaries
- BUsing = instead of == in pseudocode
- CForgetting to initialise a total before a loop
- DWriting a new value for a variable only when it changes
25.When tracing a WHILE...DO loop, the loop body may execute zero times.
Medium
True or false?
26.A trace table is being used to dry-run an algorithm that calculates the average of five test scores. The algorithm uses a variable Total and a variable Count. Count is initialised to 0 and Total is initialised to 0. Inside a loop, each score is added to Total and Count is incremented by 1. After the loop, Average is calculated as Total / Count. Which of the following is the most likely error that would be detected by examining the trace table?
Medium
- ATotal was not initialised to 0
- BCount was not initialised to 0
- CAverage was calculated before the loop
- DThe loop ran six times instead of five
27.A trace table is used to record the execution of an algorithm that searches an array of 10 names for a given target. The algorithm uses a WHILE loop with condition (Index ≤ 10) AND (Found = FALSE). Which of the following could be correctly concluded from the trace table? (Select all that apply)
Medium
- AIf the trace shows Index becoming 11, the target was not found.
- BIf the trace shows Found becoming TRUE, the target was found at the current Index.
- CIf the trace shows Found becoming TRUE, the loop stops immediately.
- DIf the trace shows Index becoming 10, the target was found at position 10.
- EIf the trace shows no changes to Found, the algorithm is broken.
28.In a trace table for a REPEAT...UNTIL loop, the condition is tested after the loop body, so the trace table should always show at least one row for the loop body.
Easy
True or false?
29.Match each algorithm standard method to the correct description.
Medium
- Linear search
- Bubble sort
- Totalling
- Checks each item in turn until a match is found
- Compares neighbouring pairs and swaps them if out of order
- Adds each value to a running total that starts at 0
30.Put the steps for tracing a bubble sort algorithm in the correct order.
Medium
- Compare the first pair of adjacent values.
- If they are out of order, swap them.
- Move to the next pair and repeat.
- After reaching the end, check if any swaps were made.
- If swaps were made, start another pass; otherwise stop.
31.During the trace, when the loop reaches Index = 3 and the current element is 7, what happens to Largest?
Medium
- ALargest becomes 7
- BLargest remains unchanged
- CLargest becomes 3
- DLargest becomes 0
32.The trace table should have a column for the variable Index.
Easy
True or false?
33.A trace table is used to trace the following algorithm. The algorithm is supposed to output the sum of all even numbers from 2 to 10 inclusive. However, the trace shows that the output is 20 instead of 30. Which of the following errors would produce this incorrect output?
Medium
- AThe loop condition was 'Number < 10' instead of 'Number ≤ 10'
- BThe loop condition was 'Number ≤ 8' instead of 'Number ≤ 10'
- CThe loop incremented Number by 4 instead of 2
- DThe loop added Number to Total before checking if it was even
34.In a trace table, when tracing an algorithm that uses a REPEAT...UNTIL loop for input validation, how many times will the PROMPT column show the prompt text if the user enters invalid values twice and then a valid value?
Medium
- AOnce
- BTwice
- CThree times
- DFour times
35.A trace table is being used to trace the following algorithm: Total ← 0 FOR Count ← 1 TO 4 Total ← Total + Count NEXT Count OUTPUT Total What is the value of Total after the third iteration of the loop?
Hard
- A6
- B10
- C3
- D9
36.Which of the following are correct steps in the column method for creating a trace table? (Select all that apply)
Medium
- ADraw the table with one column for each variable plus OUTPUT and PROMPT columns as needed.
- BWrite a new row for each change of value, never overwriting previous values.
- CFollow the control flow in the order the algorithm executes, not the order written on the page.
- DAlways test the loop condition before writing any values in the table.
37.In a trace table, when tracing a FOR...NEXT loop with STEP 2 from 1 TO 10, the loop body runs 5 times.
Medium
True or false?
38.Match each loop type to when it tests its condition.
Medium
- WHILE...DO
- REPEAT...UNTIL
- FOR...NEXT
- Tests before the body, may run zero times
- Tests after the body, runs at least once
- Tests before each pass, runs zero times if start is past end
39.If the name is found at position 3, the trace table will show Index = 3 and Found = TRUE on the same row.
Medium
True or false?
40.In a trace table, the column headed PROMPT records the text that the user sees when an INPUT statement is executed.
Easy
True or false?
41.Complete the sentence with the correct term.
Easy
In a trace table, each new assignment to a variable is written in a new ____.
42.What is the term for executing an algorithm by hand, exactly as a computer would, without running it on a computer?
Easy
43.What is the term for a loop that tests its condition before the body executes?
Easy
44.What is the term for adding 1 to a counter each time a condition is met?
Easy
45.Trace the following algorithm. What is the final value of Number? Number ← 47 WHILE Number > 9 DO Number ← Number - 9 ENDWHILE OUTPUT Number
Medium
46.Complete the sentence.
Easy
In a trace table, the column headed PROMPT records the ____ that the user sees.
47.The following algorithm is dry-run using a trace table. What is the final value of Count?
Medium
48.Fill in the blank.
Easy
The variable Largest should be initialised to the first element of the array, which is ____.
49.Trace the following algorithm and give the final value of Total.
Hard
50.What is the term for a variable that is used to record whether a condition has been met, such as Found in a linear search?
Easy
51.Trace the following algorithm. What is the final value of Number?
Easy
52.Dry-run the following algorithm. What is the final value of Total?
Medium
53.Explain why it is important to write a new row for each change of value in a trace table, rather than overwriting previous values.
Medium
54.Describe the difference between a pre-condition loop and a post-condition loop, and give one example of each.
Hard
55.State two common errors that can be identified by checking a trace table, and explain how each would appear in the table.
Medium
56.Explain how a trace table can be used to identify an error in an algorithm, and describe the process you would follow.
Hard
57.Describe how to trace a linear search algorithm using a trace table, including the columns you would use and how you would record the search.
Hard
58.Trace the following algorithm. What is the final value of Number? Number ← 47 WHILE Number > 9 DO Number ← Number - 9 ENDWHILE OUTPUT Number
Medium
- A1
- B2
- C4
- D3
59.The following algorithm is dry-run using a trace table. What is the final value of Count?
Medium
- A6
- B5
- C3
- D4
60.Trace the following algorithm and give the final value of Total.
Hard
- A20
- B17
- C18
- D19
61.Trace the following algorithm. What is the final value of Number?
Easy
- A3
- B1
- C4
- D2
62.Dry-run the following algorithm. What is the final value of Total?
Medium
- A13
- B12
- C15
- D14

복습 노트

## Tracing Algorithms With Trace Tables — Night-Before Notes ### What is a trace table? A trace table documents a **dry-run** of an algorithm: you execute it by hand, exactly as a computer would, and record every change in a table. In Paper 2, you'll often be given a ready-made grid with column headings and blank rows. ### The Column Method — 6 Rules 1. **Draw the table first.** One column per variable (in declaration order), then `OUTPUT`, and `PROMPT` if asked. For arrays, use a column per element or an index column plus element column — follow the printed grid. 2. **One row per change.** Write a new value only when assigned; leave cells blank if unchanged. **Never erase** previous values — the trail earns marks. 3. **Follow control flow, not page order.** After `NEXT`, `ENDWHILE`, or `UNTIL`, go back to loop start; after `ENDIF`, continue after the block; `CALL` jumps and returns. 4. **Test conditions at the exact point.** `WHILE...DO` tests before body (may run 0 times). `REPEAT...UNTIL` tests after body (runs at least once). `FOR...NEXT` tests before each pass. 5. **Record OUTPUT exactly as seen**, including fixed text and spaces: `OUTPUT "Total is ", Total` → `Total is 13`. 6. **Final answer** = the OUTPUT column in order, nothing else. ### Key Patterns - **Totalling**: `Total ← Total + value`, initialise `Total ← 0` before loop. - **Counting**: `Count ← Count + 1` when condition met, initialise to 0. - **Linear search**: Check each item until match or end. Stop early on match; if not found, index goes past end. - **Bubble sort**: Compare neighbours, swap if wrong order. Each pass pushes largest to end; stop when no swaps. - **Nested loops**: Inner loop runs fully for each outer pass. Reset inner variables (e.g., `RowTotal`) at the start of each outer iteration. - **Validation**: `REPEAT...UNTIL` ensures at least one prompt; prompt appears for every attempt. ### Common Slips to Avoid - Stopping at the last tested value before a false condition (e.g., in `WHILE Number > 9`, stop at 2, not 11). - Forgetting to initialise totals/counters. - Off-by-one errors: check `<=` vs `<`. - Losing resets in nested loops. - Writing both swapped values on separate rows. ### Quick Checks - Count loop passes: `FOR 1 TO 10` → 10 times; `0 TO 10` → 11; `STEP 2` from 1 to 10 → 5. - Read loop conditions with AND/OR as a whole. - If trace disagrees with expected, trust the trace — that's error identification. ### Worked Example (Pre-condition loop) ``` Number ← 47 WHILE Number > 9 DO Number ← Number - 9 ENDWHILE OUTPUT Number ``` | Number | OUTPUT | |--------|--------| | 47 | | | 38 | | | 29 | | | 20 | | | 11 | | | 2 | 2 | Output: `2`

Trace table: A table used to document a dry-run of an algorithm, showing variable values, outputs, and prompts at each step.
Dry-run: Executing an algorithm by hand, exactly as a computer would, without running it.
Variable: A named storage location that holds a value which can change during execution.
Output: Data displayed to the user by an OUTPUT statement.
Prompt: Text displayed to the user to request input, typically via an OUTPUT statement before INPUT.
Control flow: The order in which statements are executed, determined by loops, conditionals, and procedure calls.
Pre-condition loop: A loop that tests its condition before executing the body, e.g., WHILE...DO; may run zero times.
Post-condition loop: A loop that tests its condition after executing the body, e.g., REPEAT...UNTIL; always runs at least once.
FOR...NEXT loop: A loop that iterates a fixed number of times, using a counter variable; tests before each pass.
Totalling: Adding each value to a running total that starts at 0.
Counting: Adding 1 to a counter each time a condition is met.
Linear search: A method that checks each item in turn from the start until a match is found or the end is reached.
Bubble sort: A sorting algorithm that compares neighbouring pairs and swaps them if they are in the wrong order; each pass pushes the next largest value to the end.
Nested loops: Loops inside other loops; the inner loop runs completely for each pass of the outer loop.
Off-by-one error: A mistake where a loop runs one too many or one too few times, often due to using < instead of <= or vice versa.
Initialisation: Setting a variable to a starting value before it is used in a loop or calculation.

플래시카드

What is a dry-run of an algorithm?

Executing the algorithm by hand, exactly as the computer would, without running it on a computer.

What are the three types of columns typically found in a trace table?

One column per variable, plus columns for OUTPUT and, if asked, PROMPT (user prompts).

When writing a trace table, when should you write a new value in a variable's column?

Only when the algorithm assigns a new value to that variable. Leave the cell blank if the variable did not change on that step.

Why should you never erase or overwrite previous values in a trace table?

The trail of values is what earns marks and helps you find your own slips. It also shows the sequence of changes.

When tracing an algorithm, how do you decide the order in which to execute statements?

Follow the control flow, not the page order. After NEXT, ENDWHILE, or UNTIL, go back to the top of the loop; after ENDIF, continue with the next statement after the block; a CALL jumps into the procedure and returns to the line after the call.

In a WHILE...DO loop, when is the condition tested?

Before the body runs. Therefore, the body may run zero times if the condition is initially false.

In a REPEAT...UNTIL loop, when is the condition tested?

After the body has run. Therefore, the body always runs at least once.

In a FOR...NEXT loop, when is the condition tested?

Before each pass. The loop runs zero times if the start value is already past the end value.

How should you record OUTPUT statements in a trace table?

Record every OUTPUT on the row where it happens, writing exactly what the user would see, including fixed text and spaces.

What is the final answer to 'What is the output of this algorithm?'?

The contents of the OUTPUT column, in order, and nothing else.

In the trace of a WHILE loop, where should you write the value of the variable being tested?

Write the value in the table BEFORE the condition is tested. A common slip is to stop at the last value that passes the test, but you must also record the value that fails the test.

What is totalling in an algorithm?

Adding each value to a running total that starts at 0. The total variable must be initialised before the loop.

What is counting in an algorithm?

Adding 1 to a counter each time a condition is met. The counter must be initialised before the loop.

What is a common error in totalling or counting algorithms?

Not initialising the total or counter before the loop.

Describe the linear search algorithm.

Checks each item in turn from the start and stops as soon as it finds a match. If the item is not found, it continues until the end of the list.

In a linear search with a found flag, what condition ends the loop?

Either the item is found (Found = TRUE) or the index exceeds the last index (e.g., Index > 5). The trace must show which condition ended the loop.

In a bubble sort, what does each pass do?

Compares neighbouring pairs and swaps them if they are in the wrong order. Each pass pushes the next largest value to the end, so one fewer comparison is needed each pass.

When does a bubble sort stop?

When a pass makes no swaps, meaning the list is sorted.

In a trace table for a bubble sort, how should you record swaps?

Write the whole list after every swap, and keep the Swapped flag in its own column.

In nested loops, how many times does the inner loop run?

The inner loop runs completely for each single pass of the outer loop. So if the outer loop runs R times and the inner loop runs C times, the inner body runs R × C times.

What is a common slip when tracing nested loops?

Forgetting to reset the inner loop counter (or RowTotal) to its start value each time the outer loop advances.

In a trace table, how do you record user prompts?

In a PROMPT column, showing the text the user actually sees. The INPUT statement itself displays nothing.

In a REPEAT...UNTIL validation loop, how many times does the prompt appear?

Once for every attempt, including the successful one, because the loop is post-condition.

How many times does a FOR loop from 1 TO 10 run?

10 times.

How many times does a FOR loop from 0 TO 10 run?

11 times.

How many times does a FOR loop with STEP 2 from 1 TO 10 run?

5 times (1, 3, 5, 7, 9).

What should you watch for at the boundary of a loop condition?

Whether the condition uses ≤ or <, as this is where marks are lost most often.

When tracing a swap, how should you record the changed values?

Write both changed values on the same row, not one row apart.

If a variable never appears in your trace table, what should you check?

Whether it was ever assigned. If a column is full of identical values, check whether it should have been reset inside the loop.

If your trace result disagrees with the expected output, what should you do?

Trust the trace and look for the algorithm's error. This is the skill tested in section 7.8: identify errors in given algorithms and suggest corrections.

Unlock all 62 questions, flashcards & more

무료 계정을 만들어 이 주제의 모든 문제, 슬라이드, 플래시카드, 복습 노트를 확인하세요.

가입 — 무료 로그인

기출 문제

이 주제의 기출 문제 연습이 곧 나와요.

곧 출시