ExpertMedium3 marksStructured
AQA GCSE · Question 05 · Fundamentals of algorithms
Figure 4 shows an algorithm presented as a flowchart. Complete the trace table for the algorithm. You may not need to use all the rows in the table.
Figure 4 shows an algorithm presented as a flowchart. Complete the trace table for the algorithm. You may not need to use all the rows in the table.
How to approach this question
Follow the flowchart step-by-step, keeping track of the values of variables a, b, and c. Write down the values in the table each time they change.
1. **Start:** `a` is set to 0, `b` is set to 1.
2. **Loop 1:**
* `c ← a + b` → `c = 0 + 1 = 1`. (Record: a=0, b=1, c=1)
* `c > 4?` (1 > 4?) is No.
* `a ← b` → `a` becomes 1.
* `b ← c` → `b` becomes 1.
3. **Loop 2:**
* `c ← a + b` → `c = 1 + 1 = 2`. (Record: a=1, b=1, c=2)
* `c > 4?` (2 > 4?) is No.
* `a ← b` → `a` becomes 1.
* `b ← c` → `b` becomes 2.
4. **Loop 3:**
* `c ← a + b` → `c = 1 + 2 = 3`. (Record: a=1, b=2, c=3)
* `c > 4?` (3 > 4?) is No.
* `a ← b` → `a` becomes 2.
* `b ← c` → `b` becomes 3.
5. **Loop 4:**
* `c ← a + b` → `c = 2 + 3 = 5`. (Record: a=2, b=3, c=5)
* `c > 4?` (5 > 4?) is Yes.
6. **Stop:** The algorithm terminates.
Full Answer
This algorithm generates the Fibonacci sequence (1, 1, 2, 3, 5, ...) and stops when a number greater than 4 is generated. A trace table helps track the state of variables through each step of the algorithm.
- **Initialisation:** `a` = 0, `b` = 1.
- **Iteration 1:**
- `c` = `a` + `b` = 0 + 1 = 1.
- Is `c > 4`? No.
- `a` becomes `b` (so `a` = 1).
- `b` becomes `c` (so `b` = 1).
- *Table state: a=1, b=1, c=1* (The question implies recording the state when c is calculated)
- **Iteration 2:**
- `c` = `a` + `b` = 1 + 1 = 2.
- Is `c > 4`? No.
- `a` becomes `b` (so `a` = 1).
- `b` becomes `c` (so `b` = 2).
- *Table state: a=1, b=2, c=2*
- **Iteration 3:**
- `c` = `a` + `b` = 1 + 2 = 3.
- Is `c > 4`? No.
- `a` becomes `b` (so `a` = 2).
- `b` becomes `c` (so `b` = 3).
- *Table state: a=2, b=3, c=3*
- **Iteration 4:**
- `c` = `a` + `b` = 2 + 3 = 5.
- Is `c > 4`? Yes.
- The loop terminates.
- *Table state: a=2, b=3, c=5*
The trace table should reflect the values of a, b, and c at the point `c` is calculated in each loop iteration.
Common mistakes
✗ Updating `a` and `b` in the wrong order.\n✗ Recording the values in the table at the wrong point in the loop.\n✗ Making an error in the `c > 4` comparison.
Practice the full AQA GCSE Computer Science Paper 1 Python
31 questions · hints · full answers · grading
More questions from this exam
Q01.1Figure 1 shows an algorithm, represented using pseudo-code, which assigns a different value to fo...EasyQ01.2The variable `x` is assigned a value using the statement:
`x ← LEN(state)`
Using Figure 1, what ...EasyQ01.3What is the result of concatenating the contents of the variables `city` and `landmark` in Figure 1?EasyQ01.5The subroutine `POSITION` finds the first position of a character in a string.
For example, `POSI...EasyQ02.1Figure 2 shows an algorithm that uses integer division which has been represented using pseudo-co...Easy